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 (19)

• Statistical mechanics of complex networks
• Evolution of networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• The phase transition in inhomogeneous random graphs
• Generating simple random graphs with prescribed degree distribution
• A General Formalism for Inhomogeneous Random Graphs
• An Extended Variational Principle for the SK Spin-Glass Model
• General properties of overlap probability distributions in disordered spin systems. Toward Parisi ultrametricity
• Extremal Cuts of Sparse Random Graphs
• The free energy in a multi-species Sherrington-Kirkpatrick model
• The Parisi formula for mixed $p$-spin models
• Spin glass models from the point of view of spin distributions
• On the structure of quasi-stationary competing particle systems
• Parisi formula, disorder chaos and fluctuation for the ground state energy in the spherical mixed p-spin models
• Free energy and complexity of spherical bipartite models
• Low Temperature Asymptotics in Spherical Mean Field Spin Glasses
• Dynamical critical exponents for the mean-field Potts glass
• 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