Improved replica bounds for the independence ratio of random regular graphs

Abstract

Studying independent sets of maximum size is equivalent to considering the hard-core model with the fugacity parameter $\lambda$ tending to infinity. Finding the independence ratio of random $d$-regular graphs for some fixed degree $d$ has received much attention both in random graph theory and in statistical physics. For $d\ge 20$ the problem is conjectured to exhibit 1-step replica symmetry breaking (1-RSB). The corresponding 1-RSB formula for the independence ratio was confirmed for (very) large $d$ in a breakthrough paper by Ding, Sly, and Sun. Furthermore, the so-called interpolation method shows that this 1-RSB formula is an upper bound for each $d\ge 3$. For $d\le 19$ this bound is not tight and full-RSB is expected. In this work we use numerical optimization to find good substituting parameters for discrete $r$-RSB formulas ($r=2,3,4,5$) to obtain improved rigorous upper bounds for the independence ratio for each degree $3\le d\le 19$. As $r$ grows, these formulas get increasingly complicated and it becomes challenging to compute their numerical values efficiently. Also, the functions to minimize have a large number of local minima, making global optimization a difficult task.

References in corpus (1)

• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model

Cited by in corpus (2)

• Replica bound for Ising spin glass models in one dimension
• Decomposing random regular graphs into stars