Conjecture on near-perfect triangle packings in randomly perturbed regular graphs
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.