## 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
k^{2-o(1)} different lengths. In this talk we prove this conjecture
in a stronger form, showing that every such G contains cycles of
ck^{2}log 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.