Convergence of maximum bisection ratio of sparse random graphs

Electronic Communications in Probability

Brice Huang¹ 

关键词: Interpolation method;    maximum bisection;    2-spin spin glass;    configuration model;   

DOI  :  10.1214/18-ECP164

学科分类：统计和概率

来源: Institute of Mathematical Statistics

【 摘 要 】

We consider sequences of large sparse random graphs whose degree distribution approaches a limit with finite mean. This model includes both the random regular graphs and the Erdös-Renyi graphs of constant average degree. We prove that the maximum bisection ratio of such a graph sequence converges almost surely to a deterministic limit. We extend this result to so-called 2-spin spin glasses in the paramagnetic to ferromagnetic regime. Our work generalizes the graph interpolation method to some non-additive graph parameters.

【 授权许可】

CC BY