## Seminars and Colloquia by Series

Friday, February 11, 2011 - 15:05 , Location: Skiles 006 , Kevin Costello , School of Mathematics, Georgia Tech , Organizer: Xingxing Yu
We consider the question of coloring the first n integers with two colors in such a way as to avoid copies of a given arithmetic configuration (such as 3 term arithmetic progressions, or solutions to x+y=z+w). We know from results of Van der Waerden and others that avoiding such configurations completely is a hopeless task if n is sufficiently large, so instead we look at the question of finding colorings with comparatively few monochromatic copies of the configuration. At the very least, can we do significantly better than just closing our eyes and coloring randomly? I will discuss some partial answers, experimental results, and conjectured answers to these questions for certain configurations based on joint work with Steven Butler and Ron Graham.
Friday, February 4, 2011 - 15:05 , Location: Skiles 006 , Paul Wollan , Sapienza University of Rome , Organizer: Xingxing Yu
The graph minor structure theorem of Robertson and Seymour gives anapproximate characterization of which graphs do not contain some fixedgraph H as a minor.  The theorem has found numerous applications,including Robertson and Seymour's proof of the polynomial timealgorithm for the disjoint paths problem as well as the proof ofWagner's conjecture that graphs are well quasi-ordered under the minorrelation.  Unfortunately, the proof of the structure theorem isextremely long and technical.  We will discuss a new proof whichgreatly simplifies the argument and makes the result more widelyaccessible.  This is joint work with Ken-ichi Kawarabayashi.
Friday, January 28, 2011 - 15:05 , Location: Skiles 006 , Luke Postle , School of Math. Georgia Tech. , Organizer: Xingxing Yu
We extend the theory of infinite matroids recently developed by Bruhn et al to a well-known classical result in finite matroids while using the theory of connectivity for infinitematroids of Bruhn and Wollan. We prove that every infinite connected matroid M determines a graph-theoretic decomposition tree whose vertices correspond to minors of M that are3-connected, circuits, or cocircuits, and whose edges correspond to 2-separations of M. Tutte and many other authors proved such a decomposition for finite graphs; Cunningham andEdmonds proved this for finite matroids and showed that this decomposition is unique if circuits and cocircuits are also allowed. We do the same for infinite matroids. The knownproofs of these results, which use rank and induction arguments, do not extend to infinite matroids. Our proof avoids such arguments, thus giving a more first principles proof ofthe finite result. Furthermore, we overcome a number of complications arising from the infinite nature of the problem, ranging from the very existence of 2-sums to proving the treeis actually graph-theoretic.
Friday, January 21, 2011 - 15:05 , Location: Skiles 006 , Jie Ma , School of Math. Georgia Tech. , Organizer: Xingxing Yu
Judicious partitioning problems on graphs and hypergraphs ask for partitions that optimize several quantities simultaneously. In this talk we first review the history of such problems. We will then focus on a conjecture of Bollobas and Thomason  that the vertices of any r-uniform hypergraphs with m edges can be partitioned into r sets so that each set meets at least rm/(2r-1) edges. We will show that for r=3 and  m large we can get an even better bound than what the conjecture suggests.
Wednesday, December 15, 2010 - 10:05 , Location: Skiles 255 , David Galvin , Mathematics, University of Notre Dame , Organizer: Prasad Tetali
The matching sequence of a graph is the sequence whose $k$th term counts the number of matchings of size $k$. The independent set (or stable set) sequence does the same for independent sets. Except in very special cases, the terms of these sequences cannot be calculated explicitly, and one must be content to ask questions about global behavior. Examples of such questions include: is the sequence unimodal? is it log-concave? where are the roots of its generating function? For the matching sequence, these questions are answered fairly completely by a theorem of Heilmann and Lieb. For the independent set sequence, the situation is less clear. There are some positive results, one startling negative result, and a number of basic open questions. In this talk I will review the known results, and describe some recent progress on the questions.
Friday, November 12, 2010 - 14:05 , Location: Skiles 255 , Jacques Verstraete , University of California, San Diego , Organizer: Prasad Tetali

A  perfect matching in a $k$-uniform hypergraph $H=(V,E)$ on $n$ vertices is a set of$n/k$ disjoint edges of $H$, whilea fractional perfect matching in $H$ is a function $w:E --> [0,1]$ such that for each $v\in V$ we have $\sum_{e\ni v} w(e) = 1.$ Given $n \ge 3$ and $3\le k\le n$, let $m$ be the smallest integer suchthat whenever the minimum vertex degree in $H$ satisfies $\delta(H)\ge m$ then $H$ contains  aperfect matching, and let $m^*$ be defined analogously with respect to  fractional perfectmatchings. Clearly, $m^*\le m$.We prove that for large $n$, $m\sim m^*$, and suggest an approach  to determine $m^*$, andconsequently $m$, utilizing the Farkas Lemma. This is a joint work with Vojta Rodl.