Convergence of maximum bisection ratio of sparse random graphs

DOI10.1214/18-ECP164zbMath1398.05182arXiv1802.01619OpenAlexW3098888108MaRDI QIDQ1800843

Brice Huang

Publication date: 24 October 2018

Published in: Electronic Communications in Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1802.01619

zbMATH Keywords

interpolation methodconfiguration model2-spin spin glassmaximum bisection

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Density (toughness, etc.) (05C42)

Related Items (2)

Free energy subadditivity for symmetric random Hamiltonians ⋮ Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree

Cites Work

• Right-convergence of sparse random graphs
• Bounds for diluted mean-fields spin glass models
• The thermodynamic limit in mean field spin glass models
• Replica bounds for optimization problems and diluted spin systems
• The Interpolation Method for Random Graphs with Prescribed Degrees
• Replica bounds for diluted non-Poissonian spin systems
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs

This page was built for publication: Convergence of maximum bisection ratio of sparse random graphs