The Ising antiferromagnet and max cut on random regular graphs

DOI10.1137/20M137999XMaRDI QIDQ6349625arXivFDO

Authors Amin Coja-Oghlan, Philipp Loick, Balázs F. Mezei, Gregory B. Sorkin

Publication date 22 September 2020

Published in arXiv

Full work available at URL https://doi.org/10.1137/20M137999X

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Statistical mechanics, structure of matter (82-XX)

arXiv classification

cs.DMmath.COmath.PR

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

This page was built for publication: The Ising antiferromagnet and max cut on random regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6349625)