The interpolation method for random graphs with prescribed degrees

Abstract

We consider large random graphs with prescribed degrees, such as those generated by the configuration model. In the regime where the empirical degree distribution approaches a limit $\mu$ with finite mean, we establish the systematic convergence of a broad class of graph parameters that includes in particular the independence number, the maximum cut size and the log-partition function of the antiferromagnetic Ising and Potts models. The corresponding limits are shown to be Lipschitz and concave functions of $\mu$. Our work extends the applicability of the celebrated interpolation method, introduced in the context of spin glasses, and recently related to the fascinating problem of right-convergence of sparse graphs.

References in corpus (1)

• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs

Cited by in corpus (4)

• The adaptive interpolation method for proving replica formulas. Applications to the Curie-Weiss and Wigner spike models
• Replica Bounds by Combinatorial Interpolation for Diluted Spin Systems
• Concentration of multi-overlaps for random ferromagnetic spin models
• Convergence of Maximum Bisection Ratio of Sparse Random Graphs