Conjecture on near-perfect triangle packings in randomly perturbed regular graphs
Conjecture on near-perfect triangle packings in randomly perturbed regular graphs
Let , let be a -regular graph on vertices, and let be the binomial random graph. A triangle packing is a collection of edge-disjoint triangles; it covers all but edges if the number of uncovered edges is as .
Near-perfect packing conjecture. If
then with high probability there exists a triangle packing in that covers all but edges.
This conjecture is proposed as the tightness of the paper's lower bound for in the regime , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.