Spatial mixing and approximation algorithms for graphs with bounded connective constant
arXiv:1308.1762 · doi:10.1109/FOCS.2013.40
Abstract
The hard core model in statistical physics is a probability distribution on independent sets in a graph in which the weight of any independent set I is proportional to lambda^(|I|), where lambda > 0 is the vertex activity. We show that there is an intimate connection between the connective constant of a graph and the phenomenon of strong spatial mixing (decay of correlations) for the hard core model; specifically, we prove that the hard core model with vertex activity lambda < lambda_c(Delta + 1) exhibits strong spatial mixing on any graph of connective constant Delta, irrespective of its maximum degree, and hence derive an FPTAS for the partition function of the hard core model on such graphs. Here lambda_c(d) := d^d/(d-1)^(d+1) is the critical activity for the uniqueness of the Gibbs measure of the hard core model on the infinite d-ary tree. As an application, we show that the partition function can be efficiently approximated with high probability on graphs drawn from the random graph model G(n,d/n) for all lambda < e/d, even though the maximum degree of such graphs is unbounded with high probability. We also improve upon Weitz's bounds for strong spatial mixing on bounded degree graphs (Weitz, 2006) by providing a computationally simple method which uses known estimates of the connective constant of a lattice to obtain bounds on the vertex activities lambda for which the hard core model on the lattice exhibits strong spatial mixing. Using this framework, we improve upon these bounds for several lattices including the Cartesian lattice in dimensions 3 and higher. Our techniques also allow us to relate the threshold for the uniqueness of the Gibbs measure on a general tree to its branching factor (Lyons, 1989).
26 pages. In October 2014, this paper was superseded by arxiv:1410.2595. Before that, an extended abstract of this paper appeared in Proc. IEEE Symposium on the Foundations of Computer Science (FOCS), 2013, pp. 300-309
References in corpus (6)
- Enumeration of self-avoiding walks on the square lattice
- Exact thresholds for Ising-Gibbs samplers on general graphs
- Coupling with the stationary distribution and improved sampling for colorings and independent sets
- Spatial mixing and approximation algorithms for graphs with bounded connective constant
- Correlation Decay up to Uniqueness in Spin Systems
- MCMC sampling colourings and independent sets of G(n,d/n) near the uniqueness threshold
Cited by in corpus (14)
- Spatial mixing and approximation algorithms for graphs with bounded connective constant
- FPTAS for #BIS with Degree Bounds on One Side
- Strong spatial mixing for repulsive point processes
- MCMC sampling colourings and independent sets of G(n,d/n) near the uniqueness threshold
- Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model
- Counting hypergraph matchings up to uniqueness threshold
- Computing the Independence Polynomial: from the Tree Threshold down to the Roots
- Sampling colorings almost uniformly in sparse random graphs
- Spatial mixing and approximate counting for Potts model on graphs with bounded average degree
- Spatial Mixing of Coloring Random Graphs
- Potential-weighted connective constants and uniqueness of Gibbs measures
- Approximate Capacities of Two-Dimensional Codes by Spatial Mixing
- Approximation algorithms for the random-field Ising model
- Deterministic counting of graph colourings using sequences of subgraphs