We determine the asymptotics of the independence number of the random d-regular graph for all d≥ d0. It is highly concentrated, with constant-order fluctuations around nα∗- c∗log n for explicit constants α∗(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.
|Original language||English (US)|
|Number of pages||78|
|State||Published - Dec 1 2016|
All Science Journal Classification (ASJC) codes