The Ising antiferromagnet and max cut on random regular graphs

2020/09/22 by Amin Coja‐Oghlan, Coja-Oghlan, Amin, Philipp Loick +5 · 2 citations
Mathematics · Physics and Astronomy · #05C80 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics

paper · pdf · doi:10.48550/arxiv.2009.10483

openalex publication_date 2020/09/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• Bisection width, max-cut and internal partitions of 5-regular graphs
• From small eigenvalues to large cuts, and Chowla's cosine problem
• RSB bounds on the maximum cut

Related

• The Ising antiferromagnet in the replica symmetric phase
• Critical behavior of the annealed ising model on random regular graphs
• RSB bounds on the maximum cut
• On the occupancy fraction of the antiferromagnetic Ising model
• Annealed limit theorems for the ising model on random regular graphs