The Ising Antiferromagnet and Max Cut on Random Regular Graphs

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

Publication date: 3 June 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2009.10483

zbMATH Keywords

phase transition random regular graphs Ising antiferromagnet \textsf{Max Cut}Kesten-stigum bound

Mathematics Subject Classification ID

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

Related Items (3)

Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree ⋮ On the minimum bisection of random 3-regular graphs ⋮ Metastability of the Potts ferromagnet on random regular graphs

Cites Work

Unnamed Item
Unnamed Item
Consistency thresholds for the planted bisection model
Belief propagation, robust reconstruction and optimal recovery of block models
Spin glass models from the point of view of spin distributions
Reconstruction and estimation in the planted partition model
On the chromatic number of random regular graphs
Ising models on locally tree-like graphs
The high temperature region of the Viana-Bray diluted spin glass model
Remarks on the limiting Gibbs states on a (d+1)-tree
On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice.
Information-theoretic thresholds from the cavity method
A proof of the block model threshold conjecture
Charting the replica symmetric phase
Bounds for diluted mean-fields spin glass models
Replica bounds for optimization problems and diluted spin systems
Broken replica symmetry bounds in the mean field spin glass model
The cavity method at zero temperature
Bounds on the max and min bisection of random cubic and random 4-regular graphs
The Parisi ultrametricity conjecture
Spin systems on Bethe lattices
Bounds on the bisection width for random \(d\)-regular graphs
Extremal cuts of sparse random graphs
Factor models on locally tree-like graphs
The replica symmetric solution for Potts models on \(d\)-regular graphs
The Parisi formula
Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
Improved approximation of Max-Cut on graphs of bounded degree
Invariant Gaussian processes and independent sets on regular graphs of large girth
On the power of unique 2-prover 1-round games
Information, Physics, and Computation
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Community Detection and Stochastic Block Models
On the max‐cut of sparse random graphs
Proof of the Achievability Conjectures for the General Stochastic Block Model
Sum-of-squares proofs and the quest toward optimal algorithms
Random MAX SAT, random MAX CUT, and their phase transitions
The Sherrington-Kirkpatrick Model
The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
Community detection thresholds and the weak Ramanujan property
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Semidefinite programs on sparse random graphs and their application to community detection
Statistical Mechanics of Lattice Systems
Gibbs states and the set of solutions of random constraint satisfaction problems
Some optimal inapproximability results
MAX k‐CUT and approximating the chromatic number of random graphs
Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes
Combinatorial approach to the interpolation method and scaling limits in sparse random graphs

This page was built for publication: The Ising Antiferromagnet and Max Cut on Random Regular Graphs