On the structure of dense graphs with fixed clique number

We study structural properties of graphs with fixed clique number and high minimum degree. In particular, we show that there exists a function L “ Lpr, eq, such that every Kr-free graph G on n vertices with minimum degree at least p 2r 5 2r 3 ` eqn is homomorphic to a Kr-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 [On the structure of triangle-free graphs of large minimum degree, Combinatorica 26 (2006), no. 4, 489–493] and, more recently, Goddard and Lyle [Dense graphs with small clique number, J. Graph Theory 66 (2011), no. 4, 319-331] deduced the general case from Łuczak’s result. Łuczak’s proof was based on an application of Szemeredi’s regularity lemma and, as a consequence, it only gave rise to a tower-type bound on Lp3, eq. The proof presented here replaces the application of the regularity lemma by a probabilistic argument, which yields a bound for Lpr, eq that is doubly exponential in polypeq. §