A connection between MAX $\kappa$-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.

References in corpus (4)

• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• Free energy and complexity of spherical bipartite models
• Low Temperature Asymptotics in Spherical Mean Field Spin Glasses
• Optimization on Sparse Random Hypergraphs and Spin Glasses

Cited by in corpus (9)

• Suboptimality of local algorithms for a class of max-cut problems
• Free energy in multi-species mixed $p$-spin spherical models
• Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
• The Overlap Gap Property in Principal Submatrix Recovery
• Free Energy of Multiple Systems of Spherical Spin Glasses with Constrained Overlaps
• On the $K$-sat model with large number of clauses
• On ${\ell }_p$-Gaussian-Grothendieck problem
• Disorder chaos in some diluted spin glass models
• Light Cone Cancellation for Variational Quantum Eigensolver in Solving Noisy Max-Cut