Correlation Decay up to Uniqueness in Spin Systems

Abstract

We give a complete characterization of the two-state anti-ferromagnetic spin systems which are of strong spatial mixing on general graphs. We show that a two-state anti-ferromagnetic spin system is of strong spatial mixing on all graphs of maximum degree at most $\Delta$ if and only if the system has a unique Gibbs measure on infinite regular trees of degree up to $\Delta$, where $\Delta$ can be either bounded or unbounded. As a consequence, there exists an FPTAS for the partition function of a two-state anti-ferromagnetic spin system on graphs of maximum degree at most $\Delta$ when the uniqueness condition is satisfied on infinite regular trees of degree up to $\Delta$. In particular, an FPTAS exists for arbitrary graphs if the uniqueness is satisfied on all infinite regular trees. This covers as special cases all previous algorithmic results for two-state anti-ferromagnetic systems on general-structure graphs. Combining with the FPRAS for two-state ferromagnetic spin systems of Jerrum-Sinclair and Goldberg-Jerrum-Paterson, and the hardness results of Sly-Sun and independently of Galanis-Stefankovic-Vigoda, this gives a complete classification, except at the phase transition boundary, of the approximability of all two-state spin systems, on either degree-bounded families of graphs or family of all graphs.

This new version has corrected an error in Lemma 21 in Appendix A in the original version

References in corpus (2)

• The computational hardness of counting in two-spin models on d-regular graphs
• Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets

Cited by in corpus (8)

• The computational hardness of counting in two-spin models on d-regular graphs
• Spatial mixing and approximation algorithms for graphs with bounded connective constant
• Inapproximability for Antiferromagnetic Spin Systems in the Tree Non-Uniqueness Region
• More on zeros and approximation of the Ising partition function
• Computing the Independence Polynomial: from the Tree Threshold down to the Roots
• Approximating the partition function of planar two-state spin systems
• Inapproximability After Uniqueness Phase Transition in Two-Spin Systems
• Entropic Independence II: Optimal Sampling and Concentration via Restricted Modified Log-Sobolev Inequalities