Folklore conjecture on the final size of random greedy triangle packing

About 16 years old · traced to

Let G(i)G(i) be the graph remaining after ii triangles have been removed in the random greedy triangle-packing process on the complete graph on nn vertices. Let MM be the stopping time when the process produces a triangle-free graph, and let E(M)E(M) be its edge set. An event holds with high probability if its probability tends to 11 as n→∞n\to\infty.

Folklore conjecture. With high probability,

∣E(M)∣=n3/2+o(1).|E(M)|=n^{3/2+o(1)}.

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 n7/4+o(1)n^{7/4+o(1)}.

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

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.