The typical structure of sparse $K_{r+1}$-free graphs
HTML articles powered by AMS MathViewer
- by József Balogh, Robert Morris, Wojciech Samotij and Lutz Warnke PDF
- Trans. Amer. Math. Soc. 368 (2016), 6439-6485 Request permission
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 $\mathrm {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 \geqslant 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 \geqslant (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 \leqslant (1- \varepsilon )m_r$, then almost all of them are not $r$-partite.References
- Dimitris Achlioptas and Ehud Friedgut, A sharp threshold for $k$-colorability, Random Structures Algorithms 14 (1999), no. 1, 63–70. MR 1662274, DOI 10.1002/(SICI)1098-2418(1999010)14:1<63::AID-RSA3>3.0.CO;2-7
- Dimitris Achlioptas and Assaf Naor, The two possible values of the chromatic number of a random graph, Ann. of Math. (2) 162 (2005), no. 3, 1335–1351. MR 2179732, DOI 10.4007/annals.2005.162.1335
- Noga Alon, József Balogh, Béla Bollobás, and Robert Morris, The structure of almost all graphs in a hereditary property, J. Combin. Theory Ser. B 101 (2011), no. 2, 85–110. MR 2763071, DOI 10.1016/j.jctb.2010.10.001
- Noga Alon and Joel H. Spencer, The probabilistic method, 3rd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2008. With an appendix on the life and work of Paul Erdős. MR 2437651, DOI 10.1002/9780470277331
- László Babai, Miklós Simonovits, and Joel Spencer, Extremal subgraphs of random graphs, J. Graph Theory 14 (1990), no. 5, 599–622. MR 1073101, DOI 10.1002/jgt.3190140511
- József Balogh, Béla Bollobás, and Miklós Simonovits, The number of graphs without forbidden subgraphs, J. Combin. Theory Ser. B 91 (2004), no. 1, 1–24. MR 2047528, DOI 10.1016/j.jctb.2003.08.001
- József Balogh, Béla Bollobás, and Miklós Simonovits, The typical structure of graphs without given excluded subgraphs, Random Structures Algorithms 34 (2009), no. 3, 305–318. MR 2504400, DOI 10.1002/rsa.20242
- József Balogh, Béla Bollobás, and Miklós Simonovits, The fine structure of octahedron-free graphs, J. Combin. Theory Ser. B 101 (2011), no. 2, 67–84. MR 2763070, DOI 10.1016/j.jctb.2010.11.001
- József Balogh and Jane Butterfield, Excluding induced subgraphs: critical graphs, Random Structures Algorithms 38 (2011), no. 1-2, 100–120. MR 2768885, DOI 10.1002/rsa.20353
- József Balogh, Robert Morris, and Wojciech Samotij, Independent sets in hypergraphs, J. Amer. Math. Soc. 28 (2015), no. 3, 669–709. MR 3327533, DOI 10.1090/S0894-0347-2014-00816-X
- József Balogh and Dhruv Mubayi, Almost all triple systems with independent neighborhoods are semi-bipartite, J. Combin. Theory Ser. A 118 (2011), no. 4, 1494–1518. MR 2771596, DOI 10.1016/j.jcta.2011.01.006
- József Balogh and Dhruv Mubayi, Almost all triangle-free triple systems are tripartite, Combinatorica 32 (2012), no. 2, 143–169. MR 2927636, DOI 10.1007/s00493-012-2657-4
- Béla Bollobás, Random graphs, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge, 2001. MR 1864966, DOI 10.1017/CBO9780511814068
- Graham Brightwell, Konstantinos Panagiotou, and Angelika Steger, Extremal subgraphs of random graphs, Random Structures Algorithms 41 (2012), no. 2, 147–178. MR 2956053, DOI 10.1002/rsa.20413
- Amin Coja-Oghlan and Dan Vilenchik, Chasing the $k$-colorability threshold, 2013 IEEE 54th Annual Symposium on Foundations of Computer Science—FOCS 2013, IEEE Computer Soc., Los Alamitos, CA, 2013, pp. 380–389. MR 3246240, DOI 10.1109/FOCS.2013.48
- D. Conlon and T. Gowers, Combinatorial theorems in sparse random sets, arXiv:1011.4310v1 [math.CO].
- D. Conlon, W. T. Gowers, W. Samotij, and M. Schacht, On the KŁR conjecture in random graphs, Israel J. Math. 203 (2014), no. 1, 535–580. MR 3273450, DOI 10.1007/s11856-014-1120-1
- B. DeMarco and J. Kahn, Mantel’s theorem for random graphs, Random Structures Algorithms 47 (2015), no. 1, 59–72. MR 3366811, DOI 10.1002/rsa.20535
- B. DeMarco and J. Kahn, Turán’s theorem for random graphs, in preparation.
- P. Erdős, D. J. Kleitman, and B. L. Rothschild, Asymptotic enumeration of $K_{n}$-free graphs, Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973) Atti dei Convegni Lincei, No. 17, Accad. Naz. Lincei, Rome, 1976, pp. 19–27 (English, with Italian summary). MR 0463020
- P. Erdős and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960), 17–61 (English, with Russian summary). MR 125031
- P. Erdős and M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar. 1 (1966), 51–57. MR 205876
- P. Frankl and V. Rödl, Large triangle-free subgraphs in graphs without $K_4$, Graphs Combin. 2 (1986), no. 2, 135–144. MR 932121, DOI 10.1007/BF01788087
- Ehud Friedgut, Sharp thresholds of graph properties, and the $k$-sat problem, J. Amer. Math. Soc. 12 (1999), no. 4, 1017–1054. With an appendix by Jean Bourgain. MR 1678031, DOI 10.1090/S0894-0347-99-00305-7
- Ehud Friedgut, Vojtěch Rödl, and Mathias Schacht, Ramsey properties of random discrete structures, Random Structures Algorithms 37 (2010), no. 4, 407–436. MR 2760356, DOI 10.1002/rsa.20352
- Wassily Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13–30. MR 144363
- Christoph Hundack, Hans Jürgen Prömel, and Angelika Steger, Extremal graph problems for graphs with a color-critical vertex, Combin. Probab. Comput. 2 (1993), no. 4, 465–477. MR 1264719, DOI 10.1017/S0963548300000833
- Svante Janson, Tomasz Łuczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR 1782847, DOI 10.1002/9781118032718
- Yoshiharu Kohayakawa, Tomasz Łuczak, and Vojtěch Rödl, Arithmetic progressions of length three in subsets of a random set, Acta Arith. 75 (1996), no. 2, 133–163. MR 1379396, DOI 10.4064/aa-75-2-133-163
- Y. Kohayakawa, T. Łuczak, and V. Rödl, On $K^4$-free subgraphs of random graphs, Combinatorica 17 (1997), no. 2, 173–213. MR 1479298, DOI 10.1007/BF01200906
- Ph. G. Kolaitis, H. J. Prömel, and B. L. Rothschild, $K_{l+1}$-free graphs: asymptotic structure and a $0$-$1$ law, Trans. Amer. Math. Soc. 303 (1987), no. 2, 637–671. MR 902790, DOI 10.1090/S0002-9947-1987-0902790-6
- Tomasz Łuczak, On triangle-free random graphs, Random Structures Algorithms 16 (2000), no. 3, 260–276. MR 1749289, DOI 10.1002/(SICI)1098-2418(200005)16:3<260::AID-RSA3>3.3.CO;2-H
- Deryk Osthus, Hans Jürgen Prömel, and Anusch Taraz, For which densities are random triangle-free graphs almost surely bipartite?, Combinatorica 23 (2003), no. 1, 105–150. Paul Erdős and his mathematics (Budapest, 1999). MR 1996629, DOI 10.1007/s00493-003-0016-1
- Yury Person and Mathias Schacht, Almost all hypergraphs without Fano planes are bipartite, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2009, pp. 217–226. MR 2809321
- H. J. Prömel and A. Steger, The asymptotic number of graphs not containing a fixed color-critical subgraph, Combinatorica 12 (1992), no. 4, 463–473. MR 1194736, DOI 10.1007/BF01305238
- Hans Jürgen Prömel and Angelika Steger, Random $l$-colorable graphs, Random Structures Algorithms 6 (1995), no. 1, 21–37. MR 1368832, DOI 10.1002/rsa.3240060104
- Hans Jürgen Prömel and Angelika Steger, On the asymptotic structure of sparse triangle free graphs, J. Graph Theory 21 (1996), no. 2, 137–151. MR 1368739, DOI 10.1002/(SICI)1097-0118(199606)22:2<137::AID-JGT4>3.0.CO;2-O
- Vojtěch Rödl and Andrzej Ruciński, Threshold functions for Ramsey properties, J. Amer. Math. Soc. 8 (1995), no. 4, 917–942. MR 1276825, DOI 10.1090/S0894-0347-1995-1276825-6
- Vojtech Rödl and Andrzej Ruciński, Rado partition theorem for random subsets of integers, Proc. London Math. Soc. (3) 74 (1997), no. 3, 481–502. MR 1434440, DOI 10.1112/S0024611597000178
- Vojtěch Rödl and Mathias Schacht, Extremal results in random graphs, Erdös centennial, Bolyai Soc. Math. Stud., vol. 25, János Bolyai Math. Soc., Budapest, 2013, pp. 535–583. MR 3203611, DOI 10.1007/978-3-642-39286-3_{2}0
- Wojciech Samotij, Stability results for random discrete structures, Random Structures Algorithms 44 (2014), no. 3, 269–289. MR 3188596, DOI 10.1002/rsa.20477
- David Saxton and Andrew Thomason, Hypergraph containers, Invent. Math. 201 (2015), no. 3, 925–992. MR 3385638, DOI 10.1007/s00222-014-0562-8
- M. Schacht, Extremal results for random discrete structures, submitted.
- M. Simonovits, A method for solving extremal problems in graph theory, stability problems, Theory of Graphs (Proc. Colloq., Tihany, 1966) Academic Press, New York, 1968, pp. 279–319. MR 0233735
- Angelika Steger, On the evolution of triangle-free graphs, Combin. Probab. Comput. 14 (2005), no. 1-2, 211–224. MR 2128103, DOI 10.1017/S0963548304006613
- Paul Turán, Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok 48 (1941), 436–452 (Hungarian, with German summary). MR 18405
- L. Warnke, On the evolution of ${K_4}$-free graphs, Master’s thesis, ETH Zürich, 2009.
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
- Email: jobal@math.uiuc.edu
- Robert Morris
- Affiliation: IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ, Brasil
- MR Author ID: 777846
- Email: rob@impa.br
- Wojciech Samotij
- Affiliation: School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel – and – Trinity College, Cambridge CB2 1TQ, United Kingdom
- MR Author ID: 871997
- Email: samotij@post.tau.ac.il
- Lutz Warnke
- Affiliation: Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, United Kingdom
- MR Author ID: 952699
- Email: L.Warnke@dpmms.cam.ac.uk
- 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
- © Copyright 2016 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 368 (2016), 6439-6485
- MSC (2010): Primary 05A16, 05C30, 05C35, 05C80
- DOI: https://doi.org/10.1090/tran/6552
- MathSciNet review: 3461039