In 1987, Kolaitis, Prömel and Rothschild proved that, for every fixed r∈ℕ, 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 ⩽ (logn)1/4. The proof combines a new (close to sharp) supersaturation version of the Erdős-Simonovits stability theorem, the hypergraph container method, and a counting technique developed by Balogh, Bollobás and Simonovits.
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Computational Mathematics