Extremal Cuts of Sparse Random Graphs

Amir Dembo, Andrea Montanari, Subhabrata Sen

For Erdős-Rényi 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…