论文标题
随机常规图的独立比的改善了复制范围
Improved replica bounds for the independence ratio of random regular graphs
论文作者
论文摘要
研究最大尺寸的独立集相当于考虑使用fugacity参数$λ$倾向于无穷大的硬核模型。在某些固定度$ D $中找到随机$ d $的随机图形的独立性$ D $在随机图理论和统计物理学中都受到了很多关注。 对于$ d \ geq 20 $，该问题猜想是展示1步复制对称性破坏（1-rsb）。通过丁，狡猾和太阳确认了（非常）突破性纸中的（非常）$ d $的独立比的相应1-RSB公式。此外，所谓的插值方法表明，此1-RSB公式是每个$ d \ geq 3 $的上限。对于$ d \ leq 19 $，此界限并不紧密，预计将是全rsb。 在这项工作中，我们使用数值优化来找到离散的$ r $ -R $ -RSB公式（$ r = 2,3,4,5 $）的良好替代参数，以获得每个度的独立比的严格上限，以$ 3 \ leq d \ leq d \ leq d \ leq 19 $。随着$ r $的增长，这些公式变得越来越复杂，有效计算其数值的挑战。同样，最小化的功能具有大量的本地最小值，这使整体优化成为艰巨的任务。
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 \geq 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 \geq 3$. For $d \leq 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 \leq d \leq 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.
