 |
Center for Nonlinear Studies |
The hard-core model has received much attention in the past couple of decades as a lattice gas model with hard constraints in statistical physics, a multicast model of calls in communication networks, and as a weighted independent set problem in combinatorics, probability and theoretical computer science. In this model, each independent set I in a graph G is weighted as c^|I| for a positive real parameter c . For large c , computing the partition function (namely, the summation of weights over independent sets) is a well known computationally challenging problem. On the other hand, the problem is tractable for small enough c. Recently, Dror Weitz (2006)and Allan Sly (2010) have identified a threshold c* for c where the hardness of estimating the above partition function undergoes a computational transition for general graphs. In this work, we focus on the well-studied particular case of the square lattice graph, and provide a new lower bound for the threshold on the computational transition, in particular taking it well above c* that is the threshold for general graphs. Our technique re nes and builds on the tree of self-avoiding walks approach of Weitz, resulting in a new technical sufficient criterion (of wider applicability) for establishing strong spatial mixing for the hard-core model. Our new criterion achieves better bounds on strong spatial mixing when the graph has extra structure, improving upon what can be achieved by just using the maximum degree. Applying our technique to the square lattice, we prove that strong spatial mixing holds for all c < 2:3882, improving upon the work of Weitz that held for c < 1:6875. Our results imply a fully-polynomial deterministic approximation algorithm for estimating the partition function, as well as rapid mixing of the associated Glauber dynamics to sample from the hard-core distribution. (Based on joint work with Ricardo Restrepo, Prasad Tetali, Eric Vigoda, and Linji Yang.)
Host: Misha Chertkov, chertkov@lanl.gov, 665-8119