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

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.


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
Full Text: DOI arXiv Euclid