Friday, August 1, 2008
3:30 pm, MC 5158

Jacques Verstraete
University of California, San Diego

On the structure of binary matroids

An old conjecture Erdős states that every graph of minimum degree three has a cycle of length a power of two. While this might appear more a puzzle than a serious problem, the real question is to determined properties of the structure of the set of cycle lengths in a graph of prescribed minimum degree. We give the first almost constant bound on the minimum degree of a graph with no cycle of length in an infinite increasing sequence of even numbers growing no faster than the tower sequence:

22

222

2222

22222

…

Surprisingly, this result is almost best possible, in that there is an $n$-vertex graph of average degree about $\log n$ with no cycle of length in the sequence

23

234

2345

23456

…

We end with some conjectures which suggested analogous results for odd cycles.