MathSciDoc: An Archive for Mathematician ∫

 
Log In
Sign Up
Help
Go
 

Maximum independent sets on random regular graphs

Jian Ding University of Chicago Allan Sly University of California, Berkeley Nike Sun Stanford University

Probability mathscidoc:1911.43040

Gold Award Paper in 2020

Acta Mathematica, 217, (2), 263-340, 2016
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.
No keywords uploaded!
[ Download ] [ 2019-11-28 15:25:24 uploaded by actaadmin ] [ 790 downloads ] [ 0 comments ] 
@inproceedings{jian2016maximum,
  title={Maximum independent sets on random regular graphs},
  author={Jian Ding, Allan Sly, and Nike Sun},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20191128152524825749551},
  booktitle={Acta Mathematica},
  volume={217},
  number={2},
  pages={263-340},
  year={2016},
}
Jian Ding, Allan Sly, and Nike Sun. Maximum independent sets on random regular graphs. 2016. Vol. 217. In Acta Mathematica. pp.263-340. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20191128152524825749551.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved