On the unbalanced cut problem and the generalized Sherrington–Kirkpatrick model
On the unbalanced cut problem and the generalized Sherrington–Kirkpatrick model
We establish a strict asymptotic inequality between a class of graph partition problems on the sparse Erdős–Rényi and random regular graph ensembles with the same average degree. Along the way, we establish a variational representation for the ground state energy for generalized mixed p -spin glasses and derive strict comparison …