On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model
arXiv:1707.09042
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 -spin glasses and derive strict comparison inequalities for such models as the alphabet changes.
References in corpus (14)
- Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
- Community detection and graph partitioning
- Extremal Cuts of Sparse Random Graphs
- The Parisi formula has a unique minimizer
- Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
- A Dynamic Programming Approach to the Parisi Functional
- Suboptimality of local algorithms for a class of max-cut problems
- Free energy and complexity of spherical bipartite models
- Free energy in the generalized Sherrington-Kirkpatrick mean field model
- Low Temperature Asymptotics in Spherical Mean Field Spin Glasses
- Some Properties of the Phase Diagram for Mixed -Spin Glasses
- Maximum independent sets on random regular graphs
- The Legendre structure of the Parisi formula
- On spin distributions for generic p-spin models