On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model

Abstract

We establish a strict asymptotic inequality between a class of graph partition problems on the sparse End\H{o]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 inequalities for such models as the alphabet changes.

References in corpus (4)

• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• Suboptimality of local algorithms for a class of max-cut problems
• Free energy and complexity of spherical bipartite models
• On spin distributions for generic p-spin models

Cited by in corpus (1)

• Optimization on Sparse Random Hypergraphs and Spin Glasses