RAPID MIXING OF GLAUBER DYNAMICS UP TO UNIQUENESS VIA CONTRACTION

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 \Delta when the infinite regular tree lies in the uniqueprint, https://arxiv.org/abs/1111.7064, 2021]. Moreover, in the tree nonuniqueness region, Sly in posium on Foundations of Computer Science, 2010, pp. 287--296] 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 [Counting independent sets up to the tree threshold, in Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006, pp. 140--149] or the polynomial interpolation approach developed by Barvinok [Combinatorics and Complexity of Partition Functions, Springer, 2016]. However, the running time is only polynomial for constant \Delta . For the hardcore model, recent work of Anari, Liu, and Oveis Gharan [Spectral independence in highdimensional expanders and applications to the hardcore model, in Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science, 2020, pp. 1319--1330] 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 important, 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 and polynomial interpolation approaches immediately imply rapid mixing of the Glauber dynamics. Our proof utilizes the fact 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.

Automated summary

The FPTAS method can be used to estimate the partition function for general antiferromagnetic 2-spin systems on graphs with maximum degree Δ. In the tree nonuniqueness region, it is proven that there is no FPRAS to estimate the partition function unless NP = RP. This work connects three disparate algorithmic approaches and shows that contraction of tree recursions with a suitable potential function establishes rapid mixing of the Glauber dynamics.