EXTREMAL CUTS OF SPARSE RANDOM GRAPHS

• 成果类型: Article
• 署名作者: Dembo, Amir; Montanari, Andrea; Sen, Subhabrata
• 署名单位: Stanford University; Stanford University; Stanford University
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/15-AOP1084
• 发表日期: 2017
• 页码: 1190-1217
• 关键词: bisection; bounds

摘要

For Erdos-Renyi random graphs with average degree gamma, and uniformly random gamma-regular graph on n vertices, we prove that with high probability the size of both the Max-Cut and maximum bisection are n(gamma/4 + P-* root gamma/4 + o(root gamma)) + o(n) while the size of the minimum bisection is n(gamma/4 - P-* root gamma/4 + o(root gamma)) + o(n). Our derivation relates the free energy of the anti-ferromagnetic Ising model on such graphs to that of the SherringtonKirkpatrick model, with P-* approximate to 0.7632 standing for the ground state energy of the latter, expressed analytically via Parisi's formula.