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.