Universality in random graphs via optimal linking systems: trees and beyond

@misc{antonir2026universality,
  title = {{Universality in random graphs via optimal linking systems: trees and beyond}},
  author = {Asaf Cohen Antonir and Lyuben Lichev and Maksim Zhukovskii},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2608.06358},
  eprint = {2608.06358},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.06358},
  note = {CC BY 4.0},
}

TY  - UNPB
TI  - Universality in random graphs via optimal linking systems: trees and beyond
AU  - Asaf Cohen Antonir
AU  - Lyuben Lichev
AU  - Maksim Zhukovskii
PY  - 2026
DA  - 2026/11/02
PB  - arXiv
DO  - 10.48550/arxiv.2608.06358
UR  - https://arxiv.org/abs/2608.06358
AB  - We develop a framework for proving universality results in sparse random graphs. As a first application, we show that there exists an absolute constant C>1 such that, with high probability, for every fixed constant Δ, the binomial random graph G(n,Cln n/n) contains every n-vertex tree with maximum degree at most Δ. This answers a question of Montgomery (Advances in Mathematics, 2019). We also determine, for every p satisfying Cln n/n≤ p=n^−1+o(1), the minimum girth ℓ (up to an absolute multiplicative constant) for which with high probability G(n,p) contains all cycle factors of girth at least Ω(ℓ). In particular, with high probability G(n,Cln n/n) contains all cycle factors of girth at least Cln n/lnln n, which is optimal up to a constant factor. This extends an earlier result of Ferber, Kronenberg, and Luh (Transactions of the American Mathematical Society, 2019) and significantly improves a corollary of a deep result of Kahn, Lubetzky, and Wormald (Communications on Pure and Applied Mathematics, 2017). One of the key ingredients in the proofs is establishing the optimal depth of linking systems in sparse random graphs.
ER  -