Maximum independent sets on random regular graphs

Jian Ding; Allan Sly; Nike Sun

doi:10.1007/s11511-017-0145-9

Maximum independent sets on random regular graphs

Jian Ding, Allan Sly, Nike Sun

Research output: Contribution to journal › Article › peer-review

28 Scopus citations

Abstract

We determine the asymptotics of the independence number of the random d-regular graph for all d≥ d₀. It is highly concentrated, with constant-order fluctuations around nα_∗- c_∗log 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 language	English (US)
Pages (from-to)	263-340
Number of pages	78
Journal	Acta Mathematica
Volume	217
Issue number	2
DOIs	https://doi.org/10.1007/s11511-017-0145-9
State	Published - Dec 1 2016
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Mathematics

Access to Document

10.1007/s11511-017-0145-9

Cite this

@article{1c33b111ffe74a0995612532875fe595,

title = "Maximum independent sets on random regular graphs",

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∗log 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.",

author = "Jian Ding and Allan Sly and Nike Sun",

note = "Publisher Copyright: {\textcopyright} 2016, Institut Mittag-Leffler.",

year = "2016",

month = dec,

day = "1",

doi = "10.1007/s11511-017-0145-9",

language = "English (US)",

volume = "217",

pages = "263--340",

journal = "Acta Mathematica",

issn = "0001-5962",

publisher = "Springer Netherlands",

number = "2",

}

TY - JOUR

T1 - Maximum independent sets on random regular graphs

AU - Ding, Jian

AU - Sly, Allan

AU - Sun, Nike

PY - 2016/12/1

Y1 - 2016/12/1

N2 - 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∗log 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.

AB - 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∗log 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.

UR - http://www.scopus.com/inward/record.url?scp=85022217854&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85022217854&partnerID=8YFLogxK

U2 - 10.1007/s11511-017-0145-9

DO - 10.1007/s11511-017-0145-9

M3 - Article

AN - SCOPUS:85022217854

SN - 0001-5962

VL - 217

SP - 263

EP - 340

JO - Acta Mathematica

JF - Acta Mathematica

IS - 2

ER -

Maximum independent sets on random regular graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this