Termination-time conjecture for random greedy independent sets in hypergraphs

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 QiQ\approx i. For the sum-free process, this predicts termination when 2npn1/2t2np\approx n^{1/2}t, namely at

i=(23+o(1))n1/2log1/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.

Sources & referencesView supporting material

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.