Maximum independent sets on random regular graphs

Abstract

We determine the asymptotics of the independence number of the random $d$-regular graph for all $d\ge d_0$. It is highly concentrated, with constant-order fluctuations around $n{\alpha }_{\ast }-c_{\ast }\log n$ for explicit constants ${\alpha }_{\ast }(d)$ and $c_{\ast }(d)$. Our proof rigorously confirms the one-step replica symmetry breaking heuristics for this problem, and we believe the techniques will be more broadly applicable to the study of other combinatorial properties of random graphs.

References in corpus (1)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems

Cited by in corpus (9)

• Local algorithms for independent sets are half-optimal
• The asymptotic $k$-SAT threshold
• Minimal contagious sets in random regular graphs
• Harnessing the Bethe free energy
• Optimization on Sparse Random Hypergraphs and Spin Glasses
• The greedy independent set in a random graph with given degrees
• The number of solutions for random regular NAE-SAT
• On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model
• Percolation with small clusters on random graphs