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 $μ$ 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 $μ$. 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.