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.