Seminar series
Date
Tue, 24 Nov 2009
Time
14:30 -
15:30
Location
L3
Speaker
Peter Allen
Organisation
Warwick
Zarankiewicz showed that no $K_{r+1}$-free graph with minimum degree exceeding $(r-1)n/r$ can exist. This was generalised by Erdös and Stone, who showed that $K_{r+1}$ may be replaced by any graph $H$ with chromatic number $r+1$ at the cost of a $o(n)$ term added to the minimum degree.
Andr\'asfai, Erdös and S\'os proved a stability result for Zarankiewicz' theorem: $K_{r+1}$-free graphs with minimum degree exceeding $(3r-4)n/(3r-1)$ are forced to be $r$-partite. Recently, Alon and Sudakov used the Szemer\'edi Regularity Lemma to obtain a corresponding stability result for the Erdös-Stone theorem; however this result was not best possible. I will describe a simpler proof (avoiding the Regularity Lemma) of a stronger result which is conjectured to be best possible.
Andr\'asfai, Erdös and S\'os proved a stability result for Zarankiewicz' theorem: $K_{r+1}$-free graphs with minimum degree exceeding $(3r-4)n/(3r-1)$ are forced to be $r$-partite. Recently, Alon and Sudakov used the Szemer\'edi Regularity Lemma to obtain a corresponding stability result for the Erdös-Stone theorem; however this result was not best possible. I will describe a simpler proof (avoiding the Regularity Lemma) of a stronger result which is conjectured to be best possible.