THE TYPICAL STRUCTURE OF SPARSE Kr+1-FREE GRAPHS

Two central topics of study in combinatorics are the so-called evolution of random graphs, introduced by the seminal work of Erdos and Renyi, and the family of H-free graphs, that is, graphs which do not contain a subgraph isomorphic to a given (usually small) graph H. A widely studied problem that lies at the interface of these two areas is that of determining how the structure of a typical H-free graph with n vertices and m edges changes as m grows from 0 to ex(n, H). In this paper, we resolve this problem in the case when H is a clique, extending a classical result of Kolaitis, Promel, and Rothschild. In particular, we prove that for every r >= 2, there is an explicit constant theta(r) such that, letting m(r) = theta(r)n(2-2/r+1)(log n)(1/[(r+1/2)-1]), the following holds for every positive constant epsilon. If m >= (1 + epsilon)m(r), then almost all Kr+1-free n-vertex graphs with m edges are r-partite, whereas if n << m << (1 - epsilon) m(r), then almost all of them are not r-partite.