Conjecture on near-perfect triangle packings in randomly perturbed regular graphs

Let d>1/2d>1/2, let GdG_d be a dndn-regular graph on nn vertices, and let G(n,p)G(n,p) be the binomial random graph. A triangle packing is a collection of edge-disjoint triangles; it covers all but o(n2)o(n^2) edges if the number of uncovered edges is o(n2)o(n^2) as nn\rightarrow\infty.

Near-perfect packing conjecture. If

p>(34d)/(44d),p>(3-4d)/(4-4d),

then with high probability there exists a triangle packing in GdG(n,p)G_d\cup G(n,p) that covers all but o(n2)o(n^2) edges.

This conjecture is proposed as the tightness of the paper's lower bound for pdp_d in the regime d>1/2d>1/2, without assuming the Nash-Williams conjecture. Its resolution is not supplied, so it remains open.

Sources & referencesView supporting material

Primary source

Xinbu Cheng, Hong Liu, Lanchao Wang and Zhifei Yan, “Triangle packings in randomly perturbed graphs”, arXiv:2604.25250 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.