On the structure of Dense graphs with bounded clique number

Source abstract

Abstract We study structural properties of graphs with bounded clique number and high minimum degree. In particular, we show that there exists a function L = L ( r,ɛ ) such that every K r -free graph G on n vertices with minimum degree at least ((2 r –5)/(2 r –3)+ ɛ ) n is homomorphic to a K r -free graph on at most L vertices. It is known that the required minimum degree condition is approximately best possible for this result. For r = 3 this result was obtained by Łuczak (2006) and, more recently, Goddard and Lyle (2011) deduced the general case from Łuczak’s result. Łuczak’s proof was based on an application of Szemerédi’s regularity lemma and, as a consequence, it only gave rise to a tower-type bound on L (3, ɛ ). The proof presented here replaces the application of the regularity lemma by a probabilistic argument, which yields a bound for L ( r , ɛ ) that is doubly exponential in poly( ɛ ).