## Optimal threshold for a random graph to be 2-universal

HTML articles powered by AMS MathViewer

- by Asaf Ferber, Gal Kronenberg and Kyle Luh PDF
- Trans. Amer. Math. Soc.
**372**(2019), 4239-4262 Request permission

## Abstract:

For a family of graphs $\mathcal {F}$, a graph $G$ is $\mathcal {F}$-universal if $G$ contains every graph in $\mathcal {F}$ as a (not necessarily induced) subgraph. For the family of all graphs on $n$ vertices and of maximum degree at most two, $\mathcal {H}(n,2)$, we prove that there exists a constant $C$ such that for $p \geq C \left ( \frac {\log n}{n^2} \right )^{\frac {1}{3}},$ the binomial random graph $G(n,p)$ is typically $\mathcal {H}(n,2)$-universal. This bound is optimal up to the constant factor as illustrated in the seminal work of Johansson, Kahn, and Vu for triangle factors. Our result improves significantly on the previous best bound of $p \geq C \left (\frac {\log n}{n}\right )^{\frac {1}{2}}$ due to Kim and Lee. In fact, we prove the stronger result that for $\mathcal {H}^{\ell }(n,2)$, the family of all graphs on $n$ vertices, of maximum degree at most two and of girth at least $\ell$, $G(n,p)$ is typically $\mathcal H^{\ell }(n,2)$-universal when $p \geq C \left (\frac {\log n}{n^{\ell -1}}\right )^{\frac {1}{\ell }}.$ This result is also optimal up to the constant factor. Our results verify (in a weak form) a classical conjecture of Kahn and Kalai.## References

- Noga Alon and Vera Asodi,
*Sparse universal graphs*, J. Comput. Appl. Math.**142**(2002), no. 1, 1–11. Probabilistic methods in combinatorics and combinatorial optimization. MR**1910514**, DOI 10.1016/S0377-0427(01)00455-1 - Noga Alon and Michael Capalbo,
*Sparse universal graphs for bounded-degree graphs*, Random Structures Algorithms**31**(2007), no. 2, 123–133. MR**2343715**, DOI 10.1002/rsa.20143 - Noga Alon and Michael Capalbo,
*Optimal universal graphs with deterministic embedding*, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2008, pp. 373–378. MR**2485323** - Noga Alon, Michael Capalbo, Yoshiharu Kohayakawa, Vojtěch Rödl, Andrzej Ruciński, and Endre Szemerédi,
*Universality and tolerance (extended abstract)*, 41st Annual Symposium on Foundations of Computer Science (Redondo Beach, CA, 2000) IEEE Comput. Soc. Press, Los Alamitos, CA, 2000, pp. 14–21. MR**1931800**, DOI 10.1109/SFCS.2000.892007 - Noga Alon, Michael Capalbo, Yoshiharu Kohayakawa, Vojtěch Rödl, Andrzej Ruciński, and Endre Szemerédi,
*Near-optimum universal graphs for graphs with bounded degrees (extended abstract)*, Approximation, randomization, and combinatorial optimization (Berkeley, CA, 2001) Lecture Notes in Comput. Sci., vol. 2129, Springer, Berlin, 2001, pp. 170–180. MR**1910361**, DOI 10.1007/3-540-44666-4_{2}0 - Noga Alon and Zoltán Füredi,
*Spanning subgraphs of random graphs*, Graphs Combin.**8**(1992), no. 1, 91–94. MR**1157513**, DOI 10.1007/BF01271712 - Noga Alon, Michael Krivelevich, and Benny Sudakov,
*Embedding nearly-spanning bounded degree trees*, Combinatorica**27**(2007), no. 6, 629–644. MR**2384408**, DOI 10.1007/s00493-007-2182-z - Noga Alon and Joel H. Spencer,
*The probabilistic method*, 4th ed., Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016. MR**3524748** - L. Babai, F. R. K. Chung, P. Erdős, R. L. Graham, and J. H. Spencer,
*On graphs which contain all sparse graphs*, Theory and practice of combinatorics, North-Holland Math. Stud., vol. 60, North-Holland, Amsterdam, 1982, pp. 21–26. MR**806964** - József Balogh, Béla Csaba, Martin Pei, and Wojciech Samotij,
*Large bounded degree trees in expanding graphs*, Electron. J. Combin.**17**(2010), no. 1, Research Paper 6, 9. MR**2578901** - József Balogh, Béla Csaba, and Wojciech Samotij,
*Local resilience of almost spanning trees in random graphs*, Random Structures Algorithms**38**(2011), no. 1-2, 121–139. MR**2768886**, DOI 10.1002/rsa.20345 - Małgorzata Bednarska and Tomasz Łuczak,
*Biased positional games for which random strategies are nearly optimal*, Combinatorica**20**(2000), no. 4, 477–488. MR**1804821**, DOI 10.1007/s004930070002 - Sandeep N. Bhatt, F. R. K. Chung, F. T. Leighton, and Arnold L. Rosenberg,
*Universal graphs for bounded-degree trees and planar graphs*, SIAM J. Discrete Math.**2**(1989), no. 2, 145–155. MR**990447**, DOI 10.1137/0402014 - Béla Bollobás,
*Modern graph theory*, Graduate Texts in Mathematics, vol. 184, Springer-Verlag, New York, 1998. MR**1633290**, DOI 10.1007/978-1-4612-0619-4 - M. R. Capalbo and S. R. Kosaraju,
*Small universal graphs*, Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999) ACM, New York, 1999, pp. 741–749. MR**1798099**, DOI 10.1145/301250.301446 - F. R. K. Chung and R. L. Graham,
*On graphs which contain all small trees*, J. Combinatorial Theory Ser. B**24**(1978), no. 1, 14–23. MR**505812**, DOI 10.1016/0095-8956(78)90072-2 - F. R. K. Chung and R. L. Graham,
*On universal graphs*, Second International Conference on Combinatorial Mathematics (New York, 1978) Ann. New York Acad. Sci., vol. 319, New York Acad. Sci., New York, 1979, pp. 136–140. MR**556017** - F. R. K. Chung and R. L. Graham,
*On universal graphs for spanning trees*, J. London Math. Soc. (2)**27**(1983), no. 2, 203–211. MR**692525**, DOI 10.1112/jlms/s2-27.2.203 - F. R. K. Chung, R. L. Graham, and N. Pippenger,
*On graphs which contain all small trees. II*, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976) Colloq. Math. Soc. János Bolyai, vol. 18, North-Holland, Amsterdam, 1978, pp. 213–223. MR**0505813** - David Conlon, Asaf Ferber, Rajko Nenadov, and Nemanja Škorić,
*Almost-spanning universality in random graphs*, Random Structures Algorithms**50**(2017), no. 3, 380–393. MR**3632416**, DOI 10.1002/rsa.20661 - Domingos Dellamonica Jr., Yoshiharu Kohayakawa, Vojtěch Rödl, and Andrzej Ruciński,
*An improved upper bound on the density of universal random graphs*, Random Structures Algorithms**46**(2015), no. 2, 274–299. MR**3302898**, DOI 10.1002/rsa.20545 - 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 A. Rényi,
*On the existence of a factor of degree one of a connected random graph*, Acta Math. Acad. Sci. Hungar.**17**(1966), 359–368. MR**200186**, DOI 10.1007/BF01894879 - Asaf Ferber, Kyle Luh, and Oanh Nguyen,
*Embedding large graphs into a random graph*, Bull. Lond. Math. Soc.**49**(2017), no. 5, 784–797. MR**3742445**, DOI 10.1112/blms.12066 - Asaf Ferber, Rajko Nenadov, and Ueli Peter,
*Universality of random graphs and rainbow embedding*, Random Structures Algorithms**48**(2016), no. 3, 546–564. MR**3481273**, DOI 10.1002/rsa.20596 - J. Friedman and N. Pippenger,
*Expanding graphs contain all small trees*, Combinatorica**7**(1987), no. 1, 71–76. MR**905153**, DOI 10.1007/BF02579202 - P. E. Haxell,
*Tree embeddings*, J. Graph Theory**36**(2001), no. 3, 121–130. MR**1814529**, DOI 10.1002/1097-0118(200103)36:3<121::AID-JGT1000>3.0.CO;2-U - Svante Janson, Tomasz Łuczak, and Andrzej Ruciński,
*An exponential bound for the probability of nonexistence of a specified subgraph in a random graph*, Random graphs ’87 (Poznań, 1987) Wiley, Chichester, 1990, pp. 73–87. MR**1094125** - Svante Janson, Tomasz Łuczak, and Andrzej Ruciński,
*An exponential bound for the probability of nonexistence of a specified subgraph in a random graph*, Random graphs ’87 (Poznań, 1987) Wiley, Chichester, 1990, pp. 73–87. MR**1094125** - Daniel Johannsen, Michael Krivelevich, and Wojciech Samotij,
*Expanders are universal for the class of all spanning trees*, Combin. Probab. Comput.**22**(2013), no. 2, 253–281. MR**3021334**, DOI 10.1017/S0963548312000533 - Anders Johansson, Jeff Kahn, and Van Vu,
*Factors in random graphs*, Random Structures Algorithms**33**(2008), no. 1, 1–28. MR**2428975**, DOI 10.1002/rsa.20224 - Jeff Kahn and Gil Kalai,
*Thresholds and expectation thresholds*, Combin. Probab. Comput.**16**(2007), no. 3, 495–502. MR**2312440**, DOI 10.1017/S0963548307008474 - Jeong Han Kim and Sang June Lee,
*Universality of random graphs for graphs of maximum degree two*, SIAM J. Discrete Math.**28**(2014), no. 3, 1467–1478. MR**3259784**, DOI 10.1137/130942437 - Michael Krivelevich,
*Embedding spanning trees in random graphs*, SIAM J. Discrete Math.**24**(2010), no. 4, 1495–1500. MR**2746703**, DOI 10.1137/100805753 - R. Montgomery,
*Embedding bounded degree spanning trees in random graphs*, preprint, arXiv:1405.6559, 2014. - L. Pósa,
*Hamiltonian circuits in random graphs*, Discrete Math.**14**(1976), no. 4, 359–364. MR**389666**, DOI 10.1016/0012-365X(76)90068-6 - Oliver Riordan,
*Spanning subgraphs of random graphs*, Combin. Probab. Comput.**9**(2000), no. 2, 125–148. MR**1762785**, DOI 10.1017/S0963548399004150 - Vojtěch Rödl,
*A note on universal graphs*, Ars Combin.**11**(1981), 225–229. MR**629872** - Douglas B. West,
*Introduction to graph theory*, Prentice Hall, Inc., Upper Saddle River, NJ, 1996. MR**1367739**

## Additional Information

**Asaf Ferber**- Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
- MR Author ID: 897983
- Email: ferbera@mit.edu
**Gal Kronenberg**- Affiliation: School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, 6997801, Israel
- MR Author ID: 1131484
- Email: galkrone@mail.tau.ac.il
**Kyle Luh**- Affiliation: Center of Mathematical Sciences and Applications, Harvard University, Cambridge, Massachusetts 02138
- MR Author ID: 1011513
- Email: kluh@cmsa.fas.harvard.edu
- Received by editor(s): February 3, 2017
- Received by editor(s) in revised form: August 15, 2018
- Published electronically: April 18, 2019
- Additional Notes: The second author was supported by the Prof. Rahamimoff Travel Grants Program for Young Scientists of the US-Israel Binational Science Foundation (BSF)

The third author was supported by the National Science Foundation under Award No. 1702533. - © Copyright 2019 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**372**(2019), 4239-4262 - MSC (2010): Primary 05C80, 05C60
- DOI: https://doi.org/10.1090/tran/7727
- MathSciNet review: 4009429