Skip to main content

Maximum independent sets on random regular graphs

Author(s): Ding, Jian; Sly, Allan M.; Sun, Nike

To refer to this page use:
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.