Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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
Similar Articles
  • 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
  • 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