Extremal cuts of sparse random graphs

For Erdős–Rényi random graphs with average degree γ, and uniformly random γ-regular graph on n vertices, we prove that with high probability the size of both the Max-Cut and maximum bisection are n(γ/4+P*√γ/4+o(√γ))+o(n) while the size of the minimum bisection is n(γ/4-P*√γ/4+o(√γ))+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 P*≈0.7632 standing for the ground state energy of the latter, expressed analytically via Parisi’s formula.