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

  • Aukosh Jagannath

    University of Waterloo, Canada
  • Subhabrata Sen

    Harvard University, Cambridge, USA
On the unbalanced cut problem and the generalized Sherrington–Kirkpatrick model cover
Download PDF

A subscription is required to access this article.

Abstract

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 -spin glasses and derive strict comparison inequalities for such models as the alphabet changes.

Cite this article

Aukosh Jagannath, Subhabrata Sen, On the unbalanced cut problem and the generalized Sherrington–Kirkpatrick model. Ann. Inst. Henri Poincaré Comb. Phys. Interact. 8 (2021), no. 1, pp. 35–88

DOI 10.4171/AIHPD/97