Skip to main content

Maximum independent sets on random regular graphs

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

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr19m5q
Full metadata record
DC FieldValueLanguage
dc.contributor.authorDing, Jian-
dc.contributor.authorSly, Allan M.-
dc.contributor.authorSun, Nike-
dc.date.accessioned2019-04-05T20:00:30Z-
dc.date.available2019-04-05T20:00:30Z-
dc.date.issued2016en_US
dc.identifier.citationDing, 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-9en_US
dc.identifier.issn0001-5962-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr19m5q-
dc.description.abstractWe 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.en_US
dc.format.extent263 - 340en_US
dc.languageEnglishen_US
dc.language.isoen_USen_US
dc.relation.ispartofACTA MATHEMATICAen_US
dc.rightsAuthor's manuscripten_US
dc.titleMaximum independent sets on random regular graphsen_US
dc.typeJournal Articleen_US
dc.identifier.doidoi:10.1007/s11511-017-0145-9-
dc.date.eissued2016en_US
dc.identifier.eissn1871-2509-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat 
1310.4787.pdf1.3 MBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.