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

Abstract

We establish the existence of free energy limits for several combinatorial models on Erdös-Rényi graph $\mathbb{G}(N,\lfloor cN\rfloor )$ and random $r$-regular graph $\mathbb{G}(N,r)$. For a variety of models, including independent sets, MAX-CUT, coloring and K-SAT, we prove that the free energy both at a positive and zero temperature, appropriately rescaled, converges to a limit as the size of the underlying graph diverges to infinity. In the zero temperature case, this is interpreted as the existence of the scaling limit for the corresponding combinatorial optimization problem. For example, as a special case we prove that the size of a largest independent set in these graphs, normalized by the number of nodes converges to a limit w.h.p. This resolves an open problem which was proposed by Aldous (Some open problems) as one of his six favorite open problems. It was also mentioned as an open problem in several other places: Conjecture 2.20 in Wormald [In Surveys in Combinatorics, 1999 (Canterbury) (1999) 239-298 Cambridge Univ. Press]; Bollobás and Riordan [Random Structures Algorithms 39 (2011) 1-38]; Janson and Thomason [Combin. Probab. Comput. 17 (2008) 259-264] and Aldous and Steele [In Probability on Discrete Structures (2004) 1-72 Springer].

Published in at http://dx.doi.org/10.1214/12-AOP816 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• Factor models on locally tree-like graphs

Cited by in corpus (29)

• Extremal Cuts of Sparse Random Graphs
• Information-theoretic thresholds from the cavity method
• Local algorithms for independent sets are half-optimal
• Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
• Suboptimality of local algorithms for a class of max-cut problems
• The adaptive interpolation method for proving replica formulas. Applications to the Curie-Weiss and Wigner spike models
• Minimal contagious sets in random regular graphs
• Harnessing the Bethe free energy
• Limits of discrete distributions and Gibbs measures on random graphs
• A positive temperature phase transition in random hypergraph 2-coloring
• Spin systems on Bethe lattices
• Factor of iid percolation on trees
• The replica symmetric phase of random constraint satisfaction problems
• The interpolation method for random graphs with prescribed degrees
• Improved replica bounds for the independence ratio of random regular graphs
• On the chromatic number of random regular graphs
• The greedy independent set in a random graph with given degrees
• The number of solutions for random regular NAE-SAT
• On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model
• The rank of random matrices over finite fields
• Large deviations of the greedy independent set algorithm on sparse random graphs
• Convergence of Maximum Bisection Ratio of Sparse Random Graphs
• Breaking of 1RSB in random MAX-NAE-SAT
• Percolation with small clusters on random graphs
• Free Energy Subadditivity for Symmetric Random Hamiltonians
• Metastability and maximal-entropy joinings of Gibbs measures on finitely-generated groups
• Free energy equivalence between mean-field models and nonsparsely diluted mean-field models
• Decomposing random regular graphs into stars
• On MAXCUT in strictly supercritical random graphs, and coloring of random graphs and random tournaments