A connection between MAX $\kappa$-CUT and the inhomogeneous Potts spin glass in the large degree limit

Aukosh Jagannath, Justin Ko, Subhabrata Sen

We study the asymptotic behavior of the Max $\kappa$-cut on a family of sparse, inhomogeneous random graphs. In the large degree limit, the leading term is a variational problem, involv…