paper

Triangle packings in randomly perturbed graphs

arXiv:2604.25250

Abstract

The longstanding Nash-Williams conjecture asserts that every $K_{3}$ -divisible graph $G$ with $I^´ (G) \geq 3 n /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 \geq n^{- 1/2 + ε}$ . In this paper, we study near-perfect triangle packings in randomly perturbed graphs. We prove that for every $d > 0$ and every $p > 2 d / (1 + 2 d)$ , if $G_{d}$ is a $d n$ -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 \leq 1/2$ , thereby determining the threshold in this range. A key ingredient in the proof is a new triangle-weighting lemma for weighted complete graphs.

15 pages, 1 figure. Based on Delcourt and Postle's recent proof of Nash-Williams Conjecture, we establish a complete picture regarding the sharpness of $p_{d}$