Tutte seminar - Jacques Verstraete

On the structure of binary matroids

Abstract:

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:

²², ²²², ²²²², ²²²²², …

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:

²³, ²³⁴, 2³⁴⁵, 2³⁴⁵⁶, …

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