Georgia Institute of Technology College of Sciences

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.

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.

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

\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.