Combinatorics Seminar

When: Sunday, October 13, 10am Where: Schreiber 309 Speaker: Benny Sudakov, ETH Zurich and UCLA Title: Cycle packing

Abstract:

An old problem of Erdos and Gallai asks: how many cycles and edges are needed to partition the edge set of every graph on n vertices? They observed that one can easily get an O(n log n) upper bound by removing every time the edges of the longest cycle. In the 60's, Erdos and Gallai conjectured that the edge set of every graph on n vertices can be partitioned into O(n) cycles and edges. We make the first progress on this conjecture, showing that O(n loglog n) cycles and edges suffice. We also prove the Erdos-Gallai conjecture for random graphs and for graphs with linear minimum degree.

Joint work with D. Conlon and J. Fox.