Yuster's triangle-packing conjecture for random graphs
Yuster's triangle-packing conjecture for random graphs
Let be the binomial random graph, and let a -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
then asymptotically almost surely has a -packing containing all but at most 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
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.