{"id":"arxiv/2604.25250","url":"https://arxiv.org/abs/2604.25250","tags":["math.CO"],"score":0,"title":"Triangle packings in randomly perturbed graphs","domain":"math.CO","source":"arxiv","authors":["Xinbu Cheng","Hong Liu","Lanchao Wang","Zhifei Yan"],"reviews":0,"subject":"math.CO","summary":"The longstanding Nash-Williams conjecture asserts that every $K_3$-divisible graph $G$ with $δ(G)\\ge 3n/4$ admits a triangle decomposition. In the random setting, Frankl and Rödl showed that, with high probability, $G(n,p)$ contains a triangle packing covering all but $o(n^2p)$ edges whenever $p\\ge n^{-1/2+\\varepsilon}$. In this paper, we study near-perfect triangle packings in randomly perturbed graphs. We prove that for every $d>0$ and every $p>2d/(1+2d)$, if $G_d$ is a $dn$-regular graph on $n$ vertices, then with high probability the union $G_d\\cup G(n,p)$ contains a triangle packing…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-28","reactions":{}}