Convergence of Maximum Bisection Ratio of Sparse Random Graphs
arXiv:1802.01619 · doi:10.1214/18-ECP164
Abstract
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.
arXiv comment11 pages, 1 figure; added acknowledgement of a previous unpublished result
References in corpus (5)
- The Thermodynamic Limit in Mean Field Spin Glass Models
- Replica bounds for diluted non-Poissonian spin systems
- Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
- Conjecture on the maximum cut and bisection width in random regular graphs
- The interpolation method for random graphs with prescribed degrees