Seminars and Colloquia by Series

Online Matching with Stochastic Rewards

Series
Graph Theory Seminar
Time
Tuesday, February 19, 2013 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Debmalya PanigrahiDuke University
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.)

Explicit Bounds for the Weak Structure Theorem

Series
Graph Theory Seminar
Time
Thursday, February 14, 2013 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Paul WollanUniversity of Rome and Georgia Tech
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

(5,2)-configurations in K_{1,6}-free graphs

Series
Graph Theory Seminar
Time
Thursday, February 7, 2013 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Chun-Hung LiuMath, GT
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.

Linear isoperimetric bounds for graph coloring

Series
Graph Theory Seminar
Time
Tuesday, January 8, 2013 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Luke PostleEmory University
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.

A problem of Erdos on the minimum number of k-cliques

Series
Graph Theory Seminar
Time
Tuesday, November 20, 2012 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jie MaUCLA
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.

Divisors on graphs and connected flags

Series
Graph Theory Seminar
Time
Thursday, November 15, 2012 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Farbod ShokriehMath, GT
Associated to every finite graph G there is a canonical ideal which encodes the linear equivalences of divisors on G. In the study of this ideal the concept of "connected flags" arise naturally. The focus of this talk will be the study of combinatorial properties of these connected flags. This is a joint work with Fatemeh Mohammadi. (This talk is related to the talk I gave on October 12th in the Combinatorics seminar, but I will not assume anything from the previous talk.)

Colin de Verdiere-type invariants for signed graphs and odd-K_4- and odd-K^2_3-free signed graphs

Series
Graph Theory Seminar
Time
Thursday, November 8, 2012 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Hein van der HolstGeorgia State University
A signed graph is a pair $(G,\Sigma)$ where $G$ is an undirected graph (in which parallel edges are permitted, but loops are not) and $\Sigma \subseteq E(G)$. The edges in $\Sigma$ are called odd and the other edges are called even. A cycle of $G$ is called odd if it has an odd number of odd edges. If $U\subseteq V(G)$, then re-signing $(G,\Sigma)$ on $U$ gives the signed graph $(G,\Sigma\Delta \delta(U))$. A signed graph is a minor of $(G,\Sigma)$ if it comes from $(G,\Sigma)$ by a series of re-signing, deletions of edges and isolated vertices, and contractions of even edges. If $(G,\Sigma)$ is a signed graph with $n$ vertices, $S(G,\Sigma)$ is the set of all symmetric $n\times n$ matrices $A=[a_{i,j}]$ with $a_{i,j} > 0$ if $i$ and $j$ are connected by only odd edges, $a_{i,j} < 0$ if $i$ and $j$ are connected by only even edges, $a_{i,j}\in \mathbb{R}$ if $i$ and $j$ are connected by both even and odd edges, $a_{i,j}=0$ if $i$ and $j$ are not connected by any edges, and $a_{i,i} \in \mathbb{R}$ for all vertices $i$. The stable inertia set, $I_s(G,\Sigma)$, of a signed graph $(G,\Sigma)$ is the set of all pairs $(p,q)$ such that there exists a matrix $A\in S(G,\Sigma)$ that has the Strong Arnold Hypothesis, and $p$ positive and $q$ negative eigenvalues. The stable inertia set of a signed graph forms a generalization of $\mu(G)$, $\nu(G)$ (introduced by Colin de Verdi\`ere), and $\xi(G)$ (introduced by Barioli, Fallat, and Hogben). A specialization of $I_s(G,\Sigma)$ is $\nu(G,\Sigma)$, which is defined as the maximum of the nullities of positive definite matrices $A\in S(G,\Sigma)$ that have the Strong Arnold Hypothesis. This invariant is closed under taking minors, and characterizes signed graphs with no odd cycles as those signed graphs $(G,\Sigma)$ with $\nu(G,\Sigma)\leq 1$, and signed graphs with no odd-$K_4$- and no odd-$K^2_3$-minor as those signed graphs $(G,\Sigma)$ with $\nu(G,\Sigma)\leq 2$. In this talk we will discuss $I_s(G,\Sigma)$, $\nu(G,\Sigma)$ and these characterizations. Joint work with Marina Arav, Frank Hall, and Zhongshan Li.

Tree-width and Dimension - Part 2

Series
Graph Theory Seminar
Time
Thursday, October 25, 2012 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
William T. TrotterMath, GT
Over the past 40 years, researchers have made many connections between the dimension of posets and the issue of planarity for graphs and diagrams, but there appears to be little work connecting dimension to structural graph theory. This situation has changed dramatically in the last several months. At the Robin Thomas birthday conference, Gwenael Joret, made the following striking conjecture, which has now been turned into a theorem: The dimension of a poset is bounded in terms of its height and the tree-width of its cover graph. In this talk, I will present the proof of this result. The general contours of the argument should be accessible to graph theorists and combinatorists (faculty and students) without deep knowledge of either dimension or tree-width. The proof of the theorem was accomplished by a team of six researchers: Gwenael Joret, Piotr Micek, Kevin Milans, Tom Trotter, Bartosz Walczak and Ruidong Wang.

A new bound for the 2/3 Conjecture

Series
Graph Theory Seminar
Time
Thursday, April 26, 2012 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Peter WhalenMath, GT
We show that any n-vertex complete graph with edges colored with three colors contains a set of at most four vertices such that the number of the neighbors of these vertices in one of the colors is at least 2n/3. The previous best value proved by Erdos et al in 1989 is 22. It is conjectured that three vertices suffice. This is joint work with Daniel Kral, Chun-Hung Liu, Jean-Sebastien Sereni, and Zelealem Yilma.

The structure of graphs excluding a fixed immersion

Series
Graph Theory Seminar
Time
Thursday, April 19, 2012 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Paul WollanISyE, GT and The Sapienza University of Rome
A graph $G$ contains a graph $H$ as an immersion if there exist distinct vertices $\pi(v) \in V(G)$ for every vertex $v \in V(H)$ and paths $P(e)$ in $G$ for every $e \in E(H)$ such that the path $P(uv)$ connects the vertices $\pi(u)$ and $\pi(v)$ in $G$ and furthermore the paths $\{P(e):e \in E(H)\}$ are pairwise edge disjoint. Thus, graph immersion can be thought of as a generalization of subdivision containment where the paths linking the pairs of branch vertices are required to be pairwise edge disjoint instead of pairwise internally vertex disjoint. We will present a simple structure theorem for graphs excluding a fixed $K_t$ as an immersion. The structure theorem gives rise to a model of tree-decompositions based on edge cuts instead of vertex cuts. We call these decompositions tree-cut decompositions, and give an appropriate definition for the width of such a decomposition. We will present a ``grid" theorem for graph immersions with respect to the tree-cut width. This is joint work with Paul Seymour.

Pages