MAX κ-CUT AND THE INHOMOGENEOUS POTTS SPIN GLASS

• 成果类型: Article
• 署名作者: Jagannath, Aukosh; Ko, Justin; Sen, Subhabrata
• 署名单位: University of Toronto; Stanford University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/17-AAP1337
• 发表日期: 2018
• 页码: 1536-1572
• 关键词: free-energy; statistical-mechanics; convergent sequences; parisi formula; Random graphs; models

摘要

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.