Source-linked AI summary
Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
Mohsen Bayati, David Gamarnik, Prasad Tetali
TL;DR
The paper addresses whether normalized free energies and combinatorial optimization values converge on sparse Erdős–Rényi and random regular graphs. It develops a simpler combinatorial interpolation method, applies it across several models and graph ensembles, and proves the requested limits, including the independent-set scaling limit.
Problem
The paper studies whether normalized free energies and optimization values, including largest independent-set sizes, have limits as sparse random graphs grow.
Method
The paper simplifies and extends interpolation, treating zero-temperature optimization directly and applying the method to several models on Erdős–Rényi and random regular graphs.
Results
The paper proves existence of the rate limit for coloring, K-SAT, and NAE-K-SAT and establishes appropriately rescaled limits for optimization problems, including independent set.
Takeaways & Limitations
The results establish scaling limits for several sparse-graph combinatorial models and resolve the previously stated open problem for the independent-set size.
Takeaways & Limitations
For random regular graphs, the results require subsequences with Nr/K integral, and the large-deviation rate was not proved in that setting.
Abstract
from arXiv · showhide
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].
1. Introduction.
The paper simplifies and extends interpolation methods to establish limits for combinatorial optimization and free-energy quantities on sparse random graphs. It also treats random regular graphs and derives large-deviation rates for satisfiability-related models.
- Results and technical contributions: The work applies interpolation to independent set, MAX-CUT, Ising, coloring, K-SAT, and NAE-K-SAT, with coloring as the first nonbinary application.
- Results and technical contributions: A simpler combinatorial interpolation scheme treats zero-temperature optimization directly and proves limits for appropriately rescaled optimization values, including independent sets.This resolves the previously stated open problem for the independent set model.
- Results and technical contributions: The interpolation results extend from Erdős–Rényi graphs to random regular graphs and corresponding hypergraph ensembles.
- Introduction: The paper establishes a large-deviation principle for satisfiability in coloring, K-SAT, and NAE-K-SAT on Erdős–Rényi graphs.The motivating conjecture concerns a critical density separating high-probability satisfiability from nonsatisfiability.
- Introduction: For coloring, K-SAT, and NAE-K-SAT, the limit r(c)=lim N^-1 log p(c,N) exists for every c, without proving the satisfiability conjecture itself.Under the conjectured threshold behavior, the rate is zero below the threshold and negative above it.
2. Sparse random hypergraphs.
The paper defines sparse Erdős–Rényi and random regular graph or hypergraph ensembles, then represents several combinatorial models through Markov random fields and their ground-state or partition-function values.
- 2. Sparse random hypergraphs: A hypergraph is r-regular when every node appears in exactly r hyperedges, requiring Nr/K to be an integer.
- 2. Sparse random hypergraphs: Sparse Erdős–Rényi models use M=⌊cN⌋ randomly selected hyperedges with constant c, while random regular models fix each node’s degree at a constant r.The framework includes directed and undirected, simple and nonsimple variants.
- 2. Sparse random hypergraphs: The sparse Erdős–Rényi degree of a typical node is approximately Poisson with parameter cK.This motivates the term sparse random Erdős–Rényi graph.
- Combinatorial models: The models are unified as Markov random fields with node and edge potentials, whose optimized assignment value is the ground state.The associated Gibbs measure uses a partition function that approaches the ground-state value in the zero-temperature limit.
- Combinatorial models: Independent set, MAX-CUT, coloring, K-SAT, and NAE-K-SAT arise from different choices of alphabets and node or edge potentials.For example, independent-set assignments forbid adjacent selected nodes while maximizing the number selected.
- Combinatorial models: Directed hypergraphs are especially useful for K-SAT and NAE-K-SAT because the ordering of nodes in clauses matters.
3. Main results.
The paper proves scaling limits for optimization and log-partition functions across several sparse random-graph models, and establishes large-deviation rates for satisfiability in Erdős–Rényi graphs. It also derives consequences for satisfiability thresholds and resolves the independent-set scaling-limit problem.
- Erdős–Rényi graphs: Optimization values converge after normalization for six models on Erdős–Rényi graphs, including independent set, thereby resolving the stated open problem.The convergence also holds with high probability, and the proof treats zero temperature directly.
- Satisfiability: A critical-value corollary shows that below the threshold instances admit nearly satisfiable assignments, whereas above it every assignment violates linearly many clauses.The corresponding interpretation for coloring is analogous.
- Satisfiability: For coloring, K-SAT, and NAE-K-SAT, the satisfiability probability has a limiting exponential rate r(c), although the paper does not prove the full satisfiability conjecture.The result identifies a well-defined rate whenever convergence to zero is exponentially fast.
- Erdős–Rényi graphs: The normalized log-partition function converges with high probability to z(c), which is Lipschitz continuous and monotone in c according to the model.It is nondecreasing for MAX-CUT, coloring, K-SAT, and NAE-K-SAT, and nonincreasing for independent set.
- Random regular graphs: For random regular graphs, normalized optimization values and finite-temperature log-partition functions also converge, but large-deviation rates for coloring and SAT variants remain open.The regular-graph statements use subsequences for which the underlying random hypergraph is well-defined.
- Proof strategy: The interpolation proof yields approximate superadditivity of expected optimization values and expected log-partition functions, which is converted into limits using concentration and standard convergence arguments.The key decomposition compares one graph with a disjoint union of smaller random graphs.
6. Proofs: Random regular graphs.
The proof extends interpolation to random regular graphs by transforming a regular configuration into two nearly regular components, while controlling interpolation failure and model-specific objective changes.
- The regular-graph theorem applies when N1r/K and N2r/K are integers and is completed by handling both balanced and highly unbalanced partitions.
- The procedure replaces cross-part hyperedges in G(N,r,T) with within-part hyperedges, producing two nearly regular random graphs when it succeeds.
- The method analyzes independent sets, MAX-CUT, Ising, coloring, K-SAT, and NAE-K-SAT through model-specific changes in the objective under hyperedge replacement.
- For independent sets, adding an edge decreases the optimum only when both endpoints belong to the vertices contained in every largest independent set.
- The interpolation succeeds with probability at least 1 − O(N exp(−N^δ)) for some δ > 0.
APPENDIX A: PROOF OF LEMMA 1
The appendix proves a uniform bound for satisfiability under random edge additions, treating K-SAT, NAE-K-SAT, and coloring separately.
- For satisfiable K-SAT and NAE-K-SAT instances, adding a random hyperedge preserves satisfiability with probability at least ω, where ω ≥ 1/2.
- For K-SAT, the preservation probability is at least 1 − 1/2^K, while for NAE-K-SAT it is 1 − 1/2^(K−1).
- For coloring, a colorable graph that is not δ-unusual remains properly colorable after a random edge is added with probability at least δ(1 − δ).
- The coloring argument bounds the number of δ-unusual graphs using the first moment method and iterates the edge-addition inequality.
APPENDIX B: MODIFIED SUPER-ADDITIVITY THEOREM
The appendix establishes convergence for nonnegative sequences satisfying a near super-additivity condition with a sublinear correction term.
- The proposition is a special case of a more general classical theorem of de Bruijn and Erdős.
- Under the stated near super-additivity hypothesis, the normalized sequence a_N has a limit as N tends to infinity.
- The proof extends the inequality from integer to real arguments by defining a_N = a_floor(N), while retaining the O(N^α) correction.
- Repeatedly decomposing large N into balanced and fixed-size parts bounds a_N using values near the limiting supremum.