## Seminars and Colloquia by Series

Thursday, April 4, 2013 - 12:05 , Location: Skiles 005 , Dhruv Mubayi , University of Illinois at Chicago , Organizer: Robin Thomas
Since the foundational results of Thomason and Chung-Graham-Wilson on quasirandom graphs over 20 years ago, there has been a lot of effort by many researchers to extend the theory to hypergraphs. I will present some of this history, and then describe our recent results that provide such a generalization and unify much of the previous work. One key new aspect in the theory is a systematic study of hypergraph eigenvalues first introduced by Friedman and Wigderson. This is joint work with John Lenz.
Thursday, March 28, 2013 - 12:05 , Location: Skiles 005 , Peter Whalen , Georgia Tech , Organizer: Robin Thomas
We show that any internally 4-connected non-planar bipartite graph contains a subdivision of K3,3 in which each subdivided path contains an even number of vertices. In addition to being natural, this result has broader applications in matching theory: for example, finding such a subdivision of K3,3 is the first step in an algorithm for determining whether or not a bipartite graph is Pfaffian. This is joint work with Robin Thomas.
Tuesday, March 26, 2013 - 12:05 , Location: Skiles 005 , Bernard Lidicky , University of Illinois at Urbana-Champaign , Organizer: Robin Thomas
A recent lower bound on the number of edges in a k-critical n-vertex graph by Kostochka and Yancey yields a half-page proof of the celebrated Grotzsch Theorem that every planar triangle-free graph is 3-colorable. We use the same bound to give short proofs of other known theorems on 3-coloring of planar graphs, among whose is the Grunbaum-Aksenov Theorem that every planar with at most three triangles is 3-colorable. We also prove the new result that every graph obtained from a triangle-free planar graph by adding a vertex of degree at most four is 3-colorable. Joint work with O. Borodin, A. Kostochka and M. Yancey.
Thursday, March 14, 2013 - 12:05 , Location: Skiles 005 , Vojtech Tuma , Charles University , Organizer: Robin Thomas
We present a dynamic data structure representing a graph G, which allows addition and removal of edges from G and can determine the number of appearances of a graph of a bounded size as an induced subgraph of G. The queries are answered in constant time. When the data structure is used to represent graphs from a class with bounded expansion (which includes planar graphs and more generally all proper classes closed on topological minors, as well as many other natural classes of graphs with bounded average degree), the amortized time complexity of updates is polylogarithmic. This data structure is motivated by improving time complexity of graph coloring algorithms and of random graph generation.
Thursday, February 21, 2013 - 12:05 , Location: Skiles 005 , Zdenek Dvorak , Charles University and Georgia Tech , Organizer: Robin Thomas
Every subcubic triangle-free graph on n vertices contains an independent set of size at least 5n/14 (Staton'79). We strengthen this result by showing that all such graphs have fractional chromatic number at most 14/5, thus confirming a conjecture by Heckman and Thomas. (Joint work with J.-S. Sereni and J. Volec)
Tuesday, February 19, 2013 - 12:05 , Location: Skiles 005 , Debmalya Panigrahi , Duke University , Organizer: Prasad Tetali
The online matching problem has received significant attention in recent years because of its connections to allocation problems in internet advertising, crowd sourcing, etc. In these real-world applications, the typical goal is not to maximize the number of allocations; rather it is to maximize the number of “successful” allocations, where success of an allocation is governed by a stochastic event that comes after the allocation. These applications motivate us to introduce stochastic rewards in the online matching problem. In this talk, I will formally define this problem, point out its connections to previously studied allocation problems, give a deterministic algorithm that is close to optimal in its competitive ratio,  and describe some directions of future research in this line of work. (Based on joint work with Aranyak Mehta.)
Thursday, February 14, 2013 - 12:05 , Location: Skiles 005 , Paul Wollan , University of Rome and Georgia Tech , Organizer: Robin Thomas
The Weak Structure Theorem of Robertson and Seymour is the cornerstone of many of the algorithmic applications of graph minors techniques. The theorem states that any graph which has both large tree-width and excludes a fixed size clique minor contains a large, nearly planar subgraph. In this talk, we will discuss a new proof of this result which is significantly simpler than the original proof of Robertson and Seymour. As a testament to the simplicity of the proof, one can extract explicit constants to the bounds given in the theorem. We will assume no previous knowledge about graph minors or tree-width. This is joint work with Ken Kawarabayashi and Robin Thomas
Thursday, February 7, 2013 - 12:05 , Location: Skiles 005 , Chun-Hung Liu , Math, GT , Organizer: Robin Thomas
A (5,2)-configuration in a graph G is a function which maps the vertices of G into 2-element subsets of {1,2,3,4,5} in such a way that for every vertex u, the union of the 2-element subsets assigned to u and all its neighbors is {1,2,3,4,5}. This notion is motivated by a problem in robotics. Fujita, Yamashita and Kameda showed that every 3-regular graph has a (5,2)-configuration. In this talk, we will prove that except for four graphs, every graph of minimum degree at least two which does not contain K_{1,6} as an induced subgraph has a (5,2)-configuration. This is joint work with Waseem Abbas, Magnus Egerstedt, Robin Thomas, and Peter Whalen.
Tuesday, January 8, 2013 - 12:05 , Location: Skiles 005 , Luke Postle , Emory University , Organizer: Robin Thomas
We will discuss how linear isoperimetric bounds in graph coloring lead to new and interesting results. To that end, we say a family of graphs embedded in surfaces is hyperbolic if for every graph in the family the number of vertices inside an open disk is linear in the number of vertices on the boundary of that disk. Similarly we say that a family is strongly hyperbolic if the same holds for every annulus. The concept of hyperbolicity unifies and simplifies a number of known results about coloring graphs on surfaces while resolving some open conjectures. For instance: we have shown that the number of 6-list-critical graphs embeddable on a fixed surface is finite, resolving a conjecture of Thomassen from 1997; that there exists a linear time algorithm for deciding 5-choosability on a fixed surface; that locally planar graphs with distant precolored vertices are 5-choosable (which was conjectured for planar graphs by Albertson in 1999 and recently resolved by Dvorak, Lidicky, Mohar and Postle); that for every fixed surface, the number of 5-list-colorings of a 5-choosable graph is exponential in the number of vertices. We may also adapt the theory to 3-coloring graphs of girth at least five on surface to show that: the number of 4-list-critical graphs of girth at least five on a fixed surface is finite; there exists a linear time algorithm for deciding 3-choosability of graph of girth at least five on a fixed surface; locally planar graphs of girth at least five whose cycles of size four are far apart are 3-choosable (proved for the plane by Dvorak and related to the recently settled Havel's conjecture for triangle-free graphs in the plane). This is joint work with Robin Thomas.
Tuesday, November 20, 2012 - 12:05 , Location: Skiles 005 , Jie Ma , UCLA , Organizer: Robin Thomas
Fifty years ago Erdos asked to determine the minimum number of $k$-cliques in a graph on $n$ vertices with independence number less than $l$ (we will refer this as $(k,l)$-problem). He conjectured that this minimum is achieved by the disjoint union of $l-1$ complete graphs of size $\frac{n}{l-1}$. This conjecture was disproved by Nikiforov who showed that Erdos' conjecture can be true only for finite many pairs of $(k,l)$. For $(4,3)$-problem, Nikiforov further conjectured that the balanced blow-up of a $5$-cycle achieves the minimum number of $4$-cliques. We first sharpen Nikiforov's result and show that Erdos' conjecture is false whenever $k\ge 4$ or $k=3, l\ge 2074$. After introducing tools (including Flag Algebra) used in our proofs, we state our main theorems, which characterize the precise structure of extremal examples for $(3,4)$-problem and $(4,3)$-problem, confirming Erdos' conjecture for $(k,l)=(3,4)$ and Nikiforov's conjecture for $(k,l)=(4,3)$. We then focus on $(4,3)$-problem and sketch the proof how we use stability arguments to get the extremal graphs, the balanced blow-ups of $5$-cycle. Joint work with Shagnik Das, Hao Huang, Humberto Naves and Benny Sudakov.