Folklore conjecture on the final size of random greedy triangle packing
Let be the graph remaining after triangles have been removed in the random greedy triangle-packing process on the complete graph on vertices. Let be the stopping time when the process produces a triangle-free graph, and let be its edge set. An event holds with high probability if its probability tends to as .
Folklore conjecture. With high probability,
The conjecture reflects the belief that the final graph behaves like an Erdős–Rényi random graph with the same edge density. Estimating the final number of edges remains open; the paper notes that the best known upper bound is .
References
Primary source
Tom Bohman, Alan Frieze and Eyal Lubetzky, “Random greedy triangle-packing beyond the 7/4 barrier”, arXiv:1108.1781 (2012).
Additional references
2 papers in this index state this conjecture (2010–2011). The statement above is taken from the most recent of them; the others are arXiv:1004.2418.
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
No solutions have been posted yet.