Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
Zongchen Chen, Kuikui Liu, Eric Vigoda
Abstract
For general antiferromagnetic 2-spin systems, including the hardcore model on weighted independent sets and the antiferromagnetic Ising model, there is an FPTAS for the partition function on graphs of maximum degree Δ when the infinite regular tree lies in the uniqueness region by Li et al. (2013). Moreover, in the tree non-uniqueness region, Sly (2010) showed that there is no FPRAS to estimate the partition function unless NP=RP. The algorithmic results follow from the correlation decay approach due to Weitz (2006) or the polynomial interpolation approach developed by Barvinok (2016). However the running time is only polynomial for constant Δ. For the hardcore model, recent work of Anari et al. (2020) establishes rapid mixing of the simple single-site Markov chain known as the Glauber dynamics in the tree uniqueness region. Our work simplifies their analysis of the Glauber dynamics by considering the total pairwise influence of a fixed vertex v on other vertices, as opposed to the total influence of other vertices on v, thereby extending their work to all 2-spin models and improving the mixing time. More importantly our proof ties together the three disparate algorithmic approaches: we show that contraction of the so-called tree recursions with a suitable potential function, which is the primary technique for establishing efficiency of Weitz's correlation decay approach and Barvinok's polynomial interpolation approach, also establishes rapid mixing of the Glauber dynamics. We emphasize that this connection holds for all 2-spin models (both antiferromagnetic and ferromagnetic), and existing proofs for the correlation decay or polynomial interpolation approach immediately imply rapid mixing of the Glauber dynamics. Our proof utilizes that the graph partition function is a divisor of the partition function for Weitz's self-avoiding walk tree. This fact leads to new tools for the analysis of the influence of vertices, and may be of independent interest for the study of complex zeros.