Extremal Cuts of Sparse Random Graphs

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)$whilethesizeoftheminimumbisectionis$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 ${\mathsf{P}}_{\ast }\approx 0.7632$ standing for the ground state energy of the latter, expressed analytically via Parisi’s formula.