Annales de l’Institut Henri Poincaré D
Full-Text PDF (473 KB) | Metadata | Table of Contents | AIHPD summary
Published online: 2020-12-12
On the unbalanced cut problem and the generalized Sherrington–Kirkpatrick modelAukosh Jagannath and Subhabrata Sen (1) University of Waterloo, Canada
(2) Harvard University, Cambridge, USA
We establish a strict asymptotic inequality between a class of graph partition problems on the sparse Erdő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.
Keywords: Random graphs, unbalanced cuts, spin glasses, gamma convergence
Jagannath Aukosh, Sen Subhabrata: On the unbalanced cut problem and the generalized Sherrington–Kirkpatrick model. Ann. Inst. Henri Poincaré Comb. Phys. Interact. 8 (2021), 35-88. doi: 10.4171/AIHPD/97