Maximum independent sets on random regular graphs |
| |
| Authors: | Jian Ding Allan Sly Nike Sun |
| |
| Affiliation: | 1.Statistics Department,University of Chicago,Chicago,U.S.A.;2.Department of Statistics,University of California, Berkeley,Berkeley,U.S.A.;3.Mathematical Sciences Institute,Australian National University,Canberra,Australia;4.Department of Statistics,Stanford University,Stanford,U.S.A. |
| |
| Abstract: | We determine the asymptotics of the independence number of the random d-regular graph for all ({dgeq d_0}). It is highly concentrated, with constant-order fluctuations around ({nalpha_*-c_*log n}) for explicit constants ({alpha_*(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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
