Seminars and Colloquia by Series

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


Let C(G) denote the set of lengths of cycles in a graph G. In this talk I shall present the recent proofs of two conjectures of P. Erdos on cycles in sparse graphs. In particular, we show that if G is a graph of average degree d containing no cycle of length less than g, then as d -> \infty then |C(G)| = \Omega(d^{\lfloor (g - 1)/2 \rfloor}). The proof is then adapted to give partial results on three further conjectures of Erdos on cycles in graphs with large chromatic number. Specifically, Erd\H{o}s conjectured that a triangle-free graph of chromatic number k contains cycles of at least k^{2 - o(1)} different lengths as k \rightarrow \infty. We define the {\em independence ratio} of a graph G by \iota(G) := \sup_{X \subset V(G)} \frac{|X|}{\alpha(X)}, where \alpha(X) is the independence number of the subgraph of G induced by X. We show that if G is a triangle free graph and \iota(G) \geq k, then |C(G)| = \Omega(k^2 \log k). This result is sharp in view of Kim's probabilistic construction of triangle-free graphs with small independence number. A number of salient open problems will be presented in conclusion. This work is in part joint with B. Sudakov. Abstract
Friday, November 5, 2010 - 15:05 , Location: Skiles 255 , Andrzej Rucinski , A. Mickiewicz University and Emory University , Organizer: Xingxing Yu
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.
Friday, October 29, 2010 - 15:05 , Location: Skiles 255 , Todd Cochrane , Math, Kansas State University , Organizer: Prasad Tetali
\ell-sequences are periodic binary sequences {a_i} that arise from Feedback with Carry Shift Registers and in many other ways. A decimation of {a_i} is a sequence of the form {a_{di}}. Goresky and Klapper conjectured that for any prime p>13 and any \ell-sequence based on p, every pair of allowable decimations of {a_i} is cyclically distinct. If true this would yield large families of binary sequences with ideal arithmetic cross correlations. The conjecture is essentially equivalent to the statement that if p>13 then the mapping x \to Ax^d on \mathbb Z/(p) with (d,p-1)=1, p \nmid A, permutes the even residues only if it is the identity mapping. We will report on the progress towards resolving this conjecture, focussing on our joint work with Bourgain, Paulhus and Pinner.
Thursday, October 28, 2010 - 14:00 , Location: Skiles 269 , Peter L.Erdos , Alfred Renyi Inst. of Mathematics, Budapest , Organizer: William T. Trotter
In this talk we will report a short and transparent solution for the covering cost of white--grey trees which play a crucial role in the algorithm of Bergeron et al. to compute the rearrangement distance between two multi-chromosomal genomes in linear time (Theor. Comput. Sci., 410:5300-5316, 2009). In the process it introduces a new center notion for trees, which seems to be interesting on its own.
Wednesday, October 20, 2010 - 15:05 , Location: Skiles 269 , Jacob Fox , Math, MIT , Organizer: Prasad Tetali
Let H be a fixed graph with h vertices. The graph removal lemma states that every graph on n vertices with o(n^h) copies of H can be made H-free by removing o(n^2) edges. We give a new proof which avoids Szemeredi’s regularity lemma and gives a better bound. This approach also works to give improved bounds for the directed and multicolored analogues of the graph removal lemma. This answers questions of Alon and Gowers.
Thursday, October 14, 2010 - 11:05 , Location: Skiles 114 , Kevin Milans , University of South Carolina , Organizer: Xingxing Yu
A rooted tree is _k-ary_ if all non-leaves have k children; it is_complete_ if all leaves have the same distance from the root.  Let T bethe complete ternary tree of depth n.  If each edge in T is labeled 0 or1, then the labels along the edges of a path from the root to a leafform a "path label" in {0,1}^n.  Let f(n) be the maximum, over all{0,1}-edge-labeled complete ternary trees T with depth n, of the minimumnumber of distinct path labels on a complete binary subtree of depth nin T.The problem of bounding f(n) arose in studying a problem incomputability theory, where it was hoped that f(n)/2^n tends to 0 as ngrows.  This is true; we show that f(n)/2^n  is O(2^{-c \sqrt(n)}) forsome positive constant c.  From below, we show that f(n) >= (1.548)^nfor sufficiently large n.  This is joint work with Rod Downey, NoamGreenberg, and Carl Jockusch.