TY - JOUR

T1 - The typical structure of sparse kr+1-free graphs

AU - Balogh, József

AU - Morris, Robert

AU - Samotij, Wojciech

AU - Warnke, Lutz

N1 - Publisher Copyright:
© 2016 American Mathematical Society.

PY - 2016

Y1 - 2016

N2 - Two central topics of study in combinatorics are the so-called evolution of random graphs, introduced by the seminal work of Erdős and Rényi, 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, Prömel, and Rothschild. In particular, we prove that for every r ≥ 2 there is an explicit constant θγ such that, letting (Formula Precented) the following holds for every positive constant ε. If m ≥ (1 + ε)mγ then almost all Kγ+1-free n-vertex graphs with m edges are γ-partite, whereas if n ≪ m ≼ (1 + ε)mγ then almost all of them are not γ-partite.

AB - Two central topics of study in combinatorics are the so-called evolution of random graphs, introduced by the seminal work of Erdős and Rényi, 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, Prömel, and Rothschild. In particular, we prove that for every r ≥ 2 there is an explicit constant θγ such that, letting (Formula Precented) the following holds for every positive constant ε. If m ≥ (1 + ε)mγ then almost all Kγ+1-free n-vertex graphs with m edges are γ-partite, whereas if n ≪ m ≼ (1 + ε)mγ then almost all of them are not γ-partite.

UR - http://www.scopus.com/inward/record.url?scp=84958824972&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958824972&partnerID=8YFLogxK

U2 - 10.1090/tran/6552

DO - 10.1090/tran/6552

M3 - Article

AN - SCOPUS:84958824972

VL - 368

SP - 6439

EP - 6485

JO - Transactions of the American Mathematical Society

JF - Transactions of the American Mathematical Society

SN - 0002-9947

IS - 9

ER -