Id: arxiv/2608.06358 Url: https://arxiv.org/abs/2608.06358 Tags: math.CO, math.PR Score: 0 Title: Universality in random graphs via optimal linking systems: trees and beyond Domain: math.CO Source: arxiv Authors: Asaf Cohen Antonir, Lyuben Lichev, Maksim Zhukovskii Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-08-06 Page: https://delphi.science/r/arxiv/2608.06358 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,C\ln 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 $C\ln n/n\leq p=n^{-1+o(1)}$, the minimum girth $\ell$ (up to an absolute multiplicative constant) for which with high probability $G(n,p)$ contains all…