Extremal cuts of sparse random graphs. (English) Zbl 1372.05196

Dembo, Amir; Montanari, Andrea; Sen, Subhabrata

Ann. Probab. 45, No. 2, 1190-1217 (2017).

Summary: For Erdős-Rényi random graphs with average degree \(\gamma\), and uniformly random \(\gamma\)-regular graph on \(n\) vertices, we prove that with high probability the size of both the Max-Cut and maximum bisection are \(n(\frac{\gamma}{4}+\mathsf{P}_\ast\sqrt{\frac{\gamma}{4}}+o(\sqrt{\gamma}))+o(n)\) while the size of the minimum bisection is \(n(\frac{\gamma}{4}-\mathsf{P}_\ast\sqrt{\frac{\gamma}{4}}+o(\sqrt{\gamma}))+o(n)\). Our derivation relates the free energy of the anti-ferromagnetic Ising model on such graphs to that of the Sherrington-Kirkpatrick model, with \(\mathsf{P}_\ast\approx0.7632\) standing for the ground state energy of the latter, expressed analytically via Parisi’s formula.

MSC:

05C80	Random graphs (graph-theoretic aspects)
05C42	Density (toughness, etc.)
68R10	Graph theory (including graph drawing) in computer science
82B44	Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics

Keywords:

max-cut; bisection; Erdős-Rényi graph; regular graph; Ising model; spin glass; Parisi formula