Existence conjecture for independent-set densities in sparse random graphs
Let denote the maximum size of an independent set in the Erdős–Rényi random graph , and let denote the maximum size of an independent set in a random -regular graph. The parameters satisfy and .
Independent-set density existence conjecture. For every and , the limits
exist.
The conjecture concerns the existence of limiting expected independent-set densities in both sparse Erdős–Rényi and random regular graphs. The supplied text says that it remains a conjecture and attributes it to prior work by Aldous and Steele and to Aldous's collection of open problems.
References
- David Gamarnik, Tomasz Nowicki and Grzegorz Swirscsz, “Maximum Weight Independent Sets and Matchings in Sparse Random Graphs. Exact Results using the Local Weak Convergence Method”, arXiv:math/0309441 (2003).
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.