{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-06","reactions":{}}