Seminars and Colloquia by Series

The minimum number of nonnegative edges in hypergraphs

Series
Graph Theory Seminar
Time
Wednesday, November 13, 2013 - 16:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Hao HuangInstitute for Advanced Study and DIMACS
An r-unform n-vertex hypergraph H is said to have the Manickam-Miklos-Singhi (MMS) property if for every assignment of weights to its vertices with nonnegative sum, the number of edges whose total weight is nonnegative is at least the minimum degree of H. In this talk I will show that for n>10r^3, every r-uniform n-vertex hypergraph with equal codegrees has the MMS property, and the bound on n is essentially tight up to a constant factor. An immediate corollary of this result is the vector space Manickam-Miklos-Singhi conjecture which states that for n>=4k and any weighting on the 1-dimensional subspaces of F_q^n with nonnegative sum, the number of nonnegative k-dimensional subspaces is at least ${n-1 \brack k-1}_q$. I will also discuss two additional generalizations, which can be regarded as analogues of the Erdos-Ko-Rado theorem on k-intersecting families. This is joint work with Benny Sudakov.

Independent sets in triangle-free planar graphs

Series
Graph Theory Seminar
Time
Tuesday, September 24, 2013 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Zdenek DvorakCharles University
By the 4-color theorem, every planar graph on n vertices has an independent set of size at least n/4. Finding a simple proof of this fact is a long-standing open problem. Furthermore, no polynomial-time algorithm to decide whether a planar graph has an independent set of size at least (n+1)/4 is known. We study the analogous problem for triangle-free planar graphs. By Grotzsch' theorem, each such graph on n vertices has an independent set of size at least n/3, and this can be easily improved to a tight bound of (n+1)/3. We show that for every k, a triangle-free planar graph of sufficiently large tree-width has an independent set of size at least (n+k)/3, thus giving a polynomial-time algorithm to decide the existence of such a set. Furthermore, we show that there exists a constant c < 3 such that every planar graph of girth at least five has an independent set of size at least n/c.Joint work with Matthias Mnich.

Well-quasi-ordering of directed graphs

Series
Graph Theory Seminar
Time
Thursday, September 19, 2013 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Paul WollanSchool of Mathematics, Georgia Tech and University of Rome, Italy
While Robertson and Seymour showed that graphs are well-quasi-ordered under the minor relation, it is well known that directed graphs are not. We will present an exact characterization of the minor-closed sets of directed graphs which are well-quasi-ordered. This is joint work with M. Chudnovsky, S. Oum, I. Muzi, and P. Seymour.

Towards the directed cycle double cover conjecture

Series
Graph Theory Seminar
Time
Tuesday, September 10, 2013 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Martin LoeblCharles University
We prove the dcdc conjecture in a class of lean fork graphs, argue that this class is substantial and show a path towards the complete solution. Joint work with Andrea Jimenez.

Quasirandomness of permutations

Series
Graph Theory Seminar
Time
Thursday, April 18, 2013 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Daniel KralUniversity of Warwick
A systematic study of large combinatorial objects has recently led to discovering many connections between discrete mathematics and analysis. In this talk, we apply analytic methods to permutations. In particular, we associate every sequence of permutations with a measure on a unit square and show the following: if the density of every 4-element subpermutation in a permutation p is 1/4!+o(1), then the density of every k-element subpermutation is 1/k!+o(1). This answers a question of Graham whether quasirandomness of a permutation is captured by densities of its 4-element subpermutations. The result is based on a joint work with Oleg Pikhurko.

Quasirandom Hypergraphs

Series
Graph Theory Seminar
Time
Thursday, April 4, 2013 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Dhruv MubayiUniversity of Illinois at Chicago
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.

Even K3,3's in Bipartite Graphs

Series
Graph Theory Seminar
Time
Thursday, March 28, 2013 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Peter WhalenGeorgia Tech
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.

Short proofs of coloring theorems on planar graphs

Series
Graph Theory Seminar
Time
Tuesday, March 26, 2013 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Bernard LidickyUniversity of Illinois at Urbana-Champaign
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.

A dynamic data structure for counting subgraphs in sparse graphs

Series
Graph Theory Seminar
Time
Thursday, March 14, 2013 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Vojtech TumaCharles University
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.

Subcubic triangle-free graphs have fractional chromatic number at most 14/5

Series
Graph Theory Seminar
Time
Thursday, February 21, 2013 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Zdenek DvorakCharles University and Georgia Tech
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)

Pages