Does Glauber Dynamics mix for the hard-core model in the uniqueness region?

We study the hard-core (gas) model defined on independent sets of an input graph where the independent sets are weighted by a parameter lambda>0. For constant Delta, previous work of Weitz (2006) established an FPTAS for the partition function for graphs of maximum degree Delta when lambda < critical-lambda(Delta). Sly (2010) showed that there is no FPRAS, unless NP=RP, when lambda > critical-lambda(Delta).

The threshold critical-lambda(Delta) is the critical point for the statistical physics phase transition for uniqueness/non-uniqueness on the infinite Delta-regular tree. The running time of Weitz's algorithm is exponential in log(Delta). We present an FPRAS for the partition function whose running time is roughly quadratic in n. We analyze the simple single-site Markov chain known as the Glauber dynamics for sampling from the associated Gibbs distribution.

For every tau>0 we prove there exists a constant Delta0(tau) such that for all graphs with maximum degree Delta>=\Delta0(tau) and girth at least 7, the mixing time of the Glauber dynamics is O(n log (n)) when  lambda < (1-tau)critical-lambda(Delta). Our proof utilizes loopy BP (belief propagation) which is a widely-used algorithm for inference in graphical models.

Joint work with Charilaos Efthymiou, Thomas P. Hayes, Eric Vigoda, and Yitong Yin.