  For Erd\H{o}s-R\'enyi 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\Big(\frac{\gamma}{4} + {{\sf P}}_* \sqrt{\frac{\gamma}{4}} +
o(\sqrt{\gamma})\Big) + o(n)$ while the size of the minimum bisection is
$n\Big(\frac{\gamma}{4}-{{\sf P}}_*\sqrt{\frac{\gamma}{4}} +
o(\sqrt{\gamma})\Big) + 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 ${{\sf P}}_* \approx 0.7632$ standing for
the ground state energy of the latter, expressed analytically via Parisi's
formula.
