The Interpolation Method for Random Graphs with Prescribed Degrees
Author:
- 19 June 2015
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 25 (3) , 436-447
Abstract
We consider large random graphs with prescribed degrees, as generated by the configuration model. In the regime where the empirical degree distribution approaches a limit μ with finite mean, we establish the systematic convergence of a broad class of graph parameters that includes the independence number, the maximum cut size, the logarithm of the Tutte polynomial, and the free energy of the anti-ferromagnetic Ising and Potts models. Contrary to previous works, our results are not a priori limited to the free energy of some prescribed graphical model. They apply more generally to any additive, Lipschitz and concave graph parameter. In addition, the corresponding limits are shown to be Lipschitz and concave in the degree distribution μ. This considerably extends the applicability of the celebrated interpolation method, introduced in the context of spin glasses, and recently related to the challenging question of right-convergence of sparse graphs.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- The probability that a random multigraph is simple. IIJournal of Applied Probability, 2014
- Combinatorial approach to the interpolation method and scaling limits in sparse random graphsThe Annals of Probability, 2013
- Right-convergence of sparse random graphsProbability Theory and Related Fields, 2013
- Left and right convergence of graphs with bounded degreeRandom Structures & Algorithms, 2012
- Sparse graphs: Metrics and random modelsRandom Structures & Algorithms, 2011
- The Probability That a Random Multigraph is SimpleCombinatorics, Probability and Computing, 2009
- The phase transition in inhomogeneous random graphsRandom Structures & Algorithms, 2007
- Replica bounds for diluted non-Poissonian spin systemsJournal of Physics A: General Physics, 2003
- No Cycling in the Graphs!Electronic Notes in Discrete Mathematics, 2002
- A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular GraphsEuropean Journal of Combinatorics, 1980