Maximum independent sets on random regular graphs

Jian Ding, Allan Sly, Nike Sun

Research output: Contribution to journalArticlepeer-review

27 Scopus citations


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α- clog 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 languageEnglish (US)
Pages (from-to)263-340
Number of pages78
JournalActa Mathematica
Issue number2
StatePublished - Dec 1 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Mathematics


Dive into the research topics of 'Maximum independent sets on random regular graphs'. Together they form a unique fingerprint.

Cite this