The typical structure of graphs with no large cliques

Abstract

In 1987, Kolaitis, Prömel and Rothschild proved that, for every fixed $r\in \mathbb{N}$, almost every $n$-vertex $K_{r+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 Erdős-Simonovits stability theorem, the hypergraph container method, and a counting technique developed by Balogh, Bollobás and Simonovits.

14 pages, minor changes

References in corpus (1)

• A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity