Resumen de Extremal cuts of sparse random graphs

Amir Dembo, Andrea Montanari, Subhabrata Sen

• For Erdős–Rényi random graphs with average degree γγ, and uniformly random γγ-regular graph on nn 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)n(γ4+P∗γ4+o(γ))+o(n) while the size of the minimum bisection is n(γ4−P∗γ4−−√+o(γ−−√))+o(n)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.7632P∗≈0.7632 standing for the ground state energy of the latter, expressed analytically via Parisi’s formula.