Seminars and Colloquia by Series

Monday, April 28, 2014 - 15:05 , Location: Skiles 005 , Zdenek Dvorak , Charles University , Organizer: Robin Thomas
Grötzsch's theorem implies that every planar triangle-free graph is 3-colorable. It is natural to ask whether this can be improved. We prove that every planar triangle-free graph on n vertices has fractional chromatic number at most 3-1/(n+1/3), while Jones constructed planar triangle-free n-vertex graphs with fractional chromatic number 3-3/(n+1). We also investigate additional conditions under that triangle-free planar graphs have fractional chromatic number smaller than 3-epsilon for some fixed epsilon > 0.(joint work with J.-S. Sereni and J. Volec)
Thursday, April 17, 2014 - 12:05 , Location: Skiles 005 , Liana Yepremyan , McGill University (Montreal) and Georgia Tech , Organizer: Robin Thomas
Generalized triangle T_r is an r-graph with edges {1,2,…,r}, {1,2,…,r-1, r+1} and {r,r+1, r+2, …,2r-2}.  The family \Sigma_r consists of all r-graphs with three edges D_1, D_2, D_3 such that |D_1\cap D_2|=r-1  and D_1\triangle D_2\subset D_3. In 1989 it was conjectured by Frankl and Furedi that ex(n,T_r) =  ex(n,\Sigma_r) for large enough n, where ex(n,F) is the Tur\'{a}n function.  The conjecture was proven  to be true for r=3, 4 by Frankl, Furedi and Pikhurko respectively.  We settle the conjecture for r=5,6 and show that extremal graphs are blow-ups of the unique (11, 5, 4)  and (12, 6, 5) Steiner systems. The proof is based on a technique for deriving exact results for the Tur\'{a}n function from “local  stability" results, which has other applications. This is joint work with Sergey Norin.
Thursday, April 3, 2014 - 12:05 , Location: Skiles 005 , Kevin Costello , University of California, Riverside, CA , Organizer: Prasad Tetali
Suppose that each node of a rooted tree has a message that it wants to pass up the tree to the root. How can we design a protocol that guarantees all messages (eventually) reach there without being interfered with by other messages, if the nodes themselves do not know the underlying structure of the tree, or even whether their previous messages were successfully transmitted or not? I will describe (near optimal) answers to several variations of this problem, based on joint work with Marek Chrobak (UCR), Laszek Gasieniec (Liverpool) and Dariusz Kowalski (Liverpool).
Tuesday, March 25, 2014 - 12:05 , Location: Skiles 005 , Martin Loebl , Charles University , Organizer: Robin Thomas
(Alon-Tarsi Conjecture): For even n, the number of even nxn Latin squares differs from the number of odd nxn Latin squares.  (Stones-Wanless, Kotlar Conjecture): For all n, the number of even nxn Latin squares with the identity permutation as first row and first column differs from the number of odd nxn Latin squares of this type. (Aharoni-Berger Conjecture): Let M and N be two matroids on the same vertex set, and let A1,...,An be sets of size n + 1 belonging to both M and N. Then there exists a set belonging to both M and N and meeting all Ai. We prove equivalence of the first two conjectures and a special case of the third one and use these results to show that Alon-Tarsi Conjecture implies Rota's bases conjecture for odd n and any system of n non-singular real valued matrices where one of them is non-negative and the remaining have non-negative inverses.Joint work with Ron Aharoni. 
Thursday, March 13, 2014 - 12:00 , Location: Skiles 005 , Andrea Jimenez , University of Sao Paulo and Math, GT , Organizer: Robin Thomas
In this talk, we discuss our recent progress on the famous directed cycle double cover conjecture of Jaeger. This conjecture asserts that every 2-connected graph admits a collection of cycles such that each edge is in exactly two cycles of the collection. In addition, it must be possible to prescribe an orientation to each cycle so that each edge is traversed in both ways. We plan to define the class of weakly robust trigraphs and prove that a connectivity augmentation conjecture for this class implies general directed cycle double cover conjecture. This is joint work with Martin Loebl.
Thursday, March 6, 2014 - 12:05 , Location: Skiles 005 , Spencer Backman , Math, GT , Organizer: Robin Thomas
This talk is a sequel to the speaker's previous lecture given in the January 31st Combinatorics Seminar, but attendance at the first talk is not assumed. We begin by carefully reviewing our generalized cycle-cocyle reversal system for partial graph orientations. A self contained description of Baker and Norin's Riemann-Roch formula for graphs is given using their original chip-firing language. We then explain how to reinterpret and reprove this theorem using partial graph orientations. In passing, the Baker-Norin rank of a partial orientation is shown to be one less than the minimum number of directed paths which need to be reversed in the generalized cycle-cocycle reversal system to produce an acyclic partial orientation. We conclude with an overview of how these results extend to the continuous setting of metric graphs (abstract tropical curves).
Thursday, February 27, 2014 - 12:05 , Location: Skiles 005 , Paul Wollan , University of Rome "La Sapienza" , Organizer: Robin Thomas
Consider a graph G and a specified subset A of vertices. An A-path is a path with both ends in A and no internal vertex in A. Gallai showed that there exists a min-max formula for the maximum number of pairwise disjoint A-paths. More recent work has extended this result, considering disjoint A-paths which satisfy various additional properties. We consider the following model. We are given a list of {(s_i, t_i): 0< i < k} of pairs of vertices in A, consider the question of whether there exist many pairwise disjoint A-paths P_1,..., P_t such that for all j, the ends of P_j are equal to s_i and t_i for some value i. This generalizes the disjoint paths problem and is NP-hard if k is not fixed. Thus, we cannot hope for an exact min-max theorem. We further restrict the question, and ask if there either exist t pairwise disjoint such A-paths or alternatively, a bounded set of f(t) vertices intersecting all such paths. In general, there exist examples where no such function f(t) exists; we present an exact characterization of when such a function exists. This is joint work with Daniel Marx.
Wednesday, November 13, 2013 - 16:05 , Location: Skiles 005 , Hao Huang , Institute for Advanced Study and DIMACS , Organizer: Robin Thomas
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. 
Tuesday, September 24, 2013 - 12:05 , Location: Skiles 005 , Zdenek Dvorak , Charles University , Organizer: Robin Thomas
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.
Thursday, September 19, 2013 - 12:05 , Location: Skiles 005 , Paul Wollan , School of Mathematics, Georgia Tech and University of Rome, Italy , Organizer: Robin Thomas
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.