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

Optimal threshold for a random graph to be 2-universal

Authors: Asaf Ferber, Gal Kronenberg and Kyle Luh
Journal: Trans. Amer. Math. Soc. 372 (2019), 4239-4262
MSC (2010): Primary 05C80, 05C60
DOI: https://doi.org/10.1090/tran/7727
Published electronically: April 18, 2019
MathSciNet review: 4009429
Full-text PDF

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.

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

References

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

Retrieve articles in all journals with MSC (2010): 05C80, 05C60

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

Keywords: Random graphs, universal graphs, universality, graph embedding
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.
Article copyright: © Copyright 2019 American Mathematical Society