Maximum independent sets on random regular graphs
Author(s): Ding, Jian; Sly, Allan M.; Sun, Nike
DownloadTo refer to this page use:
http://arks.princeton.edu/ark:/88435/pr19m5q| 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 graphs. |
| Publication Date: | 2016 |
| Electronic Publication Date: | 2016 |
| Citation: | Ding, Jian, Sly, Allan M., Sun, Nike. (2016). Maximum independent sets on random regular graphs. ACTA MATHEMATICA, 217 (263 - 340). doi:10.1007/s11511-017-0145-9 |
| DOI: | doi:10.1007/s11511-017-0145-9 |
| ISSN: | 0001-5962 |
| EISSN: | 1871-2509 |
| Pages: | 263 - 340 |
| Language: | English |
| Type of Material: | Journal Article |
| Journal/Proceeding Title: | ACTA MATHEMATICA |
| Version: | Author's manuscript |
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.