Sách Dense H-free graphs are almost (χ(H) − 1)-partite

Abstract
By using the Szemer´edi Regularity Lemma [10], Alon and Sudakov [1] recently
extended the classical Andr´asfai-Erd˝os-S´os theorem [2] to cover general graphs. We
prove, without using the Regularity Lemma, that the following stronger statement
is true.
Given any (r+1)-partite graph H whose smallest part has t vertices, there exists
a constant C such that for any given ε > 0 and sufficiently large n the following is
true. Whenever G is an n-vertex graph with minimum degree
δ(G) >
either G contains H, or we can delete f (n, H) 6 Cn
t edges from G to obtain an
r-partite graph. Further, we are able to determine the correct order of magnitude
of f (n, H) in terms of the Zarankiewicz extremal function.