Other

Maximum independent sets on random regular graphs

Volume: 217, Issue: 2, Pages: 263 - 340
Published: Jan 1, 2016
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α∗-c∗logn 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...
Paper Details
Title
Maximum independent sets on random regular graphs
Published Date
Jan 1, 2016
Volume
217
Issue
2
Pages
263 - 340
Citation AnalysisPro
  • Scinapse’s Top 10 Citation Journals & Affiliations graph reveals the quality and authenticity of citations received by a paper.
  • Discover whether citations have been inflated due to self-citations, or if citations include institutional bias.