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.