THE TYPICAL STRUCTURE OF GRAPHS WITH NO LARGE CLIQUES

摘要

In 1987, Kolaitis, Promel and Rothschild proved that, for every fixed r is an element of N, almost every n-vertex Kr+1 -free graph is r-partite. In this paper we extend this result to all functions r = r (n) with r <= (log n)(1/4). The proof combines a new (close to sharp) supersaturation version of the Erdos-Simonovits stability theorem, the hypergraph container method, and a counting technique developed by Balogh, Bollobas and Simonovits.