%0 Journal Article
%T Maximum independent sets on random regular graphs
%A Jian Ding
%A Allan Sly
%A Nike Sun
%J Mathematics
%D 2013
%I arXiv
%X 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_* - c_*\log n$ for explicit constants $\alpha_*(d)$ and $c_*(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.
%U http://arxiv.org/abs/1310.4787v1