The interpolation method for random graphs with prescribed degrees

DOI10.1017/S0963548315000139MaRDI QIDQ5366899zbMATH OpenFDO

Authors Justin Salez

Publication date 10 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.6647

Mathematics Subject Classification ID

Vertex degrees (05C07) Random graphs (graph-theoretic aspects) (05C80) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

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.

Recommendations

• Convergence of maximum bisection ratio of sparse random graphs
• Right-convergence of sparse random graphs
• Random graphs with a given degree sequence

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Convergent sequences of sparse graphs: a large deviations approach
• Critical behavior in inhomogeneous random graphs
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 1033392 (Why is no real title available?)
• scientific article; zbMATH DE number 2230267 (Why is no real title available?)
• scientific article; zbMATH DE number 3073237 (Why is no real title available?)
• Left and right convergence of graphs with bounded degree
• Maximum independent sets on random regular graphs
• Mean field models for spin glasses. Volume I: Basic examples.
• Optimal Transport
• Replica bounds for diluted non-Poissonian spin systems
• Replica bounds for optimization problems and diluted spin systems
• Right-convergence of sparse random graphs
• Sparse graphs: metrics and random models
• The phase transition in inhomogeneous random graphs
• The probability that a random multigraph is simple
• The probability that a random multigraph is simple. II
• The Sherrington-Kirkpatrick model
• The thermodynamic limit in mean field spin glass models

Cited in

(11)

• Replica bounds by combinatorial interpolation for diluted spin systems
• Convergence of maximum bisection ratio of sparse random graphs
• Limit theory of combinatorial optimization for random geometric graphs
• Typicality and entropy of processes on infinite trees
• Concentration of multi-overlaps for random dilute ferromagnetic spin models
• The adaptive interpolation method for proving replica formulas. Applications to the Curie–Weiss and Wigner spike models
• Central limit theorem for statistics of subcritical configuration models
• Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree
• Edge ideals of Erdős-Rényi random graphs: linear resolution, unmixedness and regularity
• Normal approximation for statistics of randomly weighted complexes
• The fractional chromatic number of random graphs

This page was built for publication: The interpolation method for random graphs with prescribed degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5366899)