Tutte seminar - Jacques Verstraete

Friday, August 1, 2008 3:30 pm - 4:30 pm EDT (GMT -04:00)

On the structure of binary matroids

Speaker: Jacques Verstraete
Affiliation: University of California, San Diego
Room: Mathematics & Computer Building (MC) 5158

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:

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.