期刊论文详细信息
Electronic Communications in Probability | |
Convergence of maximum bisection ratio of sparse random graphs | |
Brice Huang1  | |
关键词: 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
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO201910284230755ZK.pdf | 214KB | download |