Termination-time conjecture for random greedy independent sets in hypergraphs
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 denote the number of open elements after step , and let be the number of elements already chosen. Termination-time conjecture. The algorithm terminates with high probability at an asymptotic step satisfying . For the sum-free process, this predicts termination when , namely at
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
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.