Title: A connection between MAX $κ$-CUT and the inhomogeneous Potts spin glass in the large degree limit,
Abstract: 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, involving the ground state of a constrained
inhomogeneous Potts spin glass. We derive a Parisi type formula for the free
energy of this model, with possible constraints on the proportions, and derive
the limiting ground state energy by a suitable zero temperature limit.