Termination-time conjecture for random greedy independent sets in hypergraphs

At least 10 years old · documented by

Consider the random greedy independent set algorithm on a sufficiently nice hypergraph, meaning one that is almost uniform, almost regular, and not too sparse. Let QQ denote the number of open elements after step ii, and let ii be the number of elements already chosen. Termination-time conjecture. The algorithm terminates with high probability at an asymptotic step ii satisfying Q≈iQ\approx i. For the sum-free process, this predicts termination when 2np≈n1/2t2np\approx n^{1/2}t, namely at

i=(23+o(1))n1/2log⁡1/2n.i=\left(\sqrt{\frac{2}{3}}+o(1)\right)n^{1/2}\log^{1/2}n.

This conjecture proposes a general heuristic for locating the end of random greedy independent-set processes by comparing the number of open elements with the number already selected. The paper establishes a lower bound for the sum-free process but does not establish this predicted termination time in full, so the conjecture remains open.

References

Primary source

Patrick Bennett, “The sum-free process”, arXiv:1502.01644 (2019).

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.