Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

Request Permissions   Purchase Content 


The typical structure of sparse $ K_{r+1}$-free graphs

Authors: József Balogh, Robert Morris, Wojciech Samotij and Lutz Warnke
Journal: Trans. Amer. Math. Soc. 368 (2016), 6439-6485
MSC (2010): Primary 05A16, 05C30, 05C35, 05C80
Published electronically: January 14, 2016
MathSciNet review: 3461039
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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 $ \textup {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 \ge 2$, there is an explicit constant $ \theta _r$ such that, letting $ m_r = \theta _r n^{2-\frac {2}{r+2}} (\log n)^{1/\left [\binom {r+1}{2}-1\right ]}$, the following holds for every positive constant $ \varepsilon $. If $ m \ge (1+\varepsilon ) m_r$, then almost all $ K_{r+1}$-free $ n$-vertex graphs with $ m$ edges are $ r$-partite, whereas if $ n \ll m \le (1- \varepsilon )m_r$, then almost all of them are not $ r$-partite.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05A16, 05C30, 05C35, 05C80

Retrieve articles in all journals with MSC (2010): 05A16, 05C30, 05C35, 05C80

Additional Information

József Balogh
Affiliation: Department of Mathematics, University of Illinois, 1409 W. Green Street, Urbana, Illinois 61801 – and – Mathematical Institute, University of Szeged, Szeged, Hungary

Robert Morris
Affiliation: IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ, Brasil

Wojciech Samotij
Affiliation: School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel – and – Trinity College, Cambridge CB2 1TQ, United Kingdom

Lutz Warnke
Affiliation: Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, United Kingdom

Received by editor(s): July 23, 2013
Received by editor(s) in revised form: August 22, 2014
Published electronically: January 14, 2016
Additional Notes: The research of the first author was supported in part by Marie Curie Fellowship IIF-327763, NSF CAREER Grant DMS-0745185, UIUC Campus Research Board Grants 11067 and 13039 (Arnold O. Beckman Research Award), and OTKA Grant K76099. The research of the second author was supported in part by CNPq bolsa de Produtividade em Pesquisa. The research of the third author was supported in part by ERC Advanced Grant DMMCA and Trinity College JRF. The research of the fourth author was supported in part by Peterhouse JRF
Article copyright: © Copyright 2016 American Mathematical Society