The Ising antiferromagnet and max cut on random regular graphs

Understand

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\'a 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.