Maximum independent sets on random regular graphs

Jian Ding, Allan Sly, Nike Sun

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

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
Volume217
Issue number2
DOIs
StatePublished - Dec 1 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

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

Cite this