论文标题
在随机的常规图上切割的抗fiferromagnet和max
The Ising antiferromagnet and max cut on random regular graphs
论文作者
论文摘要
Ising AntiferRomagnet是一个重要的统计物理模型，与{\ sc max cut}问题密切相关。将空间混合参数与矩的方法和插值方法相结合，我们指出了物理学家预测的复制对称性破坏相变。此外，我们严格地在Zdeborová和Boettcher预测的随机常规图的{\ sc Max Cut}上建立上限[统计力学杂志2010]。作为一种应用，我们证明了随机常规图上的脱骨随机块模型的信息理论阈值与kesten-stigum绑定一致。
The Ising antiferromagnet is an important statistical physics model with close connections to the {\sc Max Cut} problem. Combining spatial mixing arguments with the method of moments and the interpolation method, we pinpoint the replica symmetry breaking phase transition predicted by physicists. Additionally, we rigorously establish upper bounds on the {\sc Max Cut} of random regular graphs predicted by Zdeborová and Boettcher [Journal of Statistical Mechanics 2010]. As an application we prove that the information-theoretic threshold of the disassortative stochastic block model on random regular graphs coincides with the Kesten-Stigum bound.
