Dense $H$-free graphs are almost $(\chi(H)-1)$-partite

Dense $H$-free graphs are almost $(\chi(H)-1)$-partite

Tue, 24/11/2009
14:30 		Peter Allen (Warwick) Combinatorial Theory Seminar Add to calendar L3
Dense $ H $-free graphs are almost $ (\chi(H)-1) $-partite
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ásfai, Erdös and Sós 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édi 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.