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 (9)

• The Bethe lattice spin glass revisited
• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• The Parisi formula has a unique minimizer
• Replica bounds for diluted non-Poissonian spin systems
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
• Local algorithms for independent sets are half-optimal
• Invariant Gaussian processes and independent sets on regular graphs of large girth
• Spin systems on Bethe lattices
• Replica Bounds by Combinatorial Interpolation for Diluted Spin Systems

Cited by in corpus (2)

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