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

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. Â© 2016, Institut Mittag-Leffler.

Original language	English
Pages (from-to)	263 - 340
Journal	Acta Mathematica
Volume	217
Issue number	2
DOIs	https://doi.org/10.1007/s11511-017-0145-9
Publication status	Published - 2016

Access to Document

10.1007/s11511-017-0145-9

Cite this

@article{a6929d4a7c3e4dab892d563101465d80,

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{\^a}‰¥ d0. It is highly concentrated, with constant-order fluctuations around n{\^I}±{\^a}ˆ—- c{\^a}ˆ—log n for explicit constants {\^I}±{\^a}ˆ—(d) and c{\^a}ˆ—(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. {\^A}{\textcopyright} 2016, Institut Mittag-Leffler.",

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

year = "2016",

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

language = "English",

volume = "217",

pages = "263 -- 340",

journal = "Acta Mathematica",

publisher = "Springer",

number = "2",

}

TY - JOUR

T1 - Maximum independent sets on random regular graphs **

AU - Ding, Jian

AU - Sly, Allan

AU - Sun, Nike

PY - 2016

Y1 - 2016

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. Â© 2016, Institut Mittag-Leffler.

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. Â© 2016, Institut Mittag-Leffler.

U2 - 10.1007/s11511-017-0145-9

DO - 10.1007/s11511-017-0145-9

M3 - Article

VL - 217

SP - 263

EP - 340

JO - Acta Mathematica

JF - Acta Mathematica

IS - 2

ER -

Maximum independent sets on random regular graphs **

Abstract

Access to Document

Fingerprint

Cite this