Yuster's triangle-packing conjecture for random graphs

Let G(n,p)G(n,p) be the binomial random graph, and let a K3K_3-packing be a collection of pairwise edge-disjoint triangles. Its leave consists of the edges not covered by the packing.

Yuster's triangle-packing conjecture. If

p(1+ε)lognn,p\geq (1+\varepsilon)\sqrt{\frac{\log n}{n}},

then asymptotically almost surely G(n,p)G(n,p) has a K3K_3-packing containing all but at most 3n3n edges.

This conjecture concerns the threshold for packing triangles with a small leave. The surrounding discussion reports little progress on Yuster's conjectures and presents the paper's results as improvements to the known bounds, so the conjecture remains open in the supplied source.

Sources & referencesView supporting material

Primary source

Michelle Delcourt, Tom Kelly and Luke Postle, “Clique Decompositions in Random Graphs via Refined Absorption”, arXiv:2402.17857 (2024).

Additional references

3 papers in this index state this conjecture (2014–2024). The statement above is taken from the most recent of them; the others are arXiv:2008.07904, arXiv:1408.4870.

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.