Improved Replica Bounds for the Independence Ratio of Random Regular Graphs

Harangi, Viktor (2023) Improved Replica Bounds for the Independence Ratio of Random Regular Graphs. JOURNAL OF STATISTICAL PHYSICS, 190 (3). No-60. ISSN 0022-4715

Preview

Text RSB_bounds_20230127.pdf Download (967kB) | Preview

Abstract

Studying independent sets of maximum size is equivalent to considering the hard-core model with the fugacity parameter λ 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≥ 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≥ 3. For d≤ 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 ≤ d≤ 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.

Actions (login required)

Edit Item