Combinatorics Seminar
When: Sunday, January 4, 10am
Where: Schreiber 309
Speaker: Benny Sudakov, ETH Zurich
Title: Cycles in triangle-free graphs of large chromatic number
Abstract:
More than twenty years ago Erdős conjectured that a triangle-free
graph G of chromatic number k contains cycles of at least
k2-o(1) different lengths. In this talk we prove this conjecture
in a stronger form, showing that every such G contains cycles of
ck2log k consecutive lengths, which is tight. Our approach can
be
also used to give new bounds on the number of different cycle
lengths for other monotone classes of k-chromatic graphs, i.e.,
clique-free graphs and graphs without odd cycles.
Joint work with A. Kostochka and J. Verstraete.