Triangle packings in randomly perturbed graphs

The longstanding Nash-Williams conjecture asserts that every $K_3$-divisible graph $G$ with $\delta (G)\ge 3n\mathrm{/}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^{2}p)$ edges whenever $p\ge n^{-1\mathrm{/}2+\epsilon }$. In this paper, we study near-perfect triangle packings in randomly perturbed graphs. We prove that for every $d>0$ and every $p>2d\mathrm{/}(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 covering all but $o(n^2)$ edges. Moreover, this bound on $p$ is best possible for $0<d\le 1\mathrm{/}2$, thereby determining the threshold in this range. A key ingredient in the proof is a new triangle-weighting lemma for weighted complete graphs.