Contraction: a Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems

Abstract

We study complex zeros of the partition function of 2-spin systems, viewed as a multivariate polynomial in terms of the edge interaction parameters and the uniform external field. We obtain new zero-free regions in which all these parameters are complex-valued. Crucially based on the zero-freeness, we show the existence of correlation decay in these regions. As a consequence, we obtain an FPTAS for computing the partition function of 2-spin systems on graphs of bounded degree for these parameter settings. We introduce the contraction property as a unified sufficient condition to devise FPTAS via either Weitz's algorithm or Barvinok's algorithm. Our main technical contribution is a very simple but general approach to extend any real parameter of which the 2-spin system exhibits correlation decay to its complex neighborhood where the partition function is zero-free and correlation decay still exists. This result formally establishes the inherent connection between two distinct notions of phase transition for 2-spin systems: the existence of correlation decay and the zero-freeness of the partition function via a unified perspective, contraction.

arXiv comment21 pages, 3 figures. Update: two correlation decay sets were added; a discussion with an independent work by Liu with similar results was given

References in corpus (10)

• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Bounds on the Complex Zeros of (Di)Chromatic Polynomials and Potts-Model Partition Functions
• The Complexity of Weighted Boolean #CSP
• The computational hardness of counting in two-spin models on d-regular graphs
• Fisher zeros and correlation decay in the Ising model
• The Ising Partition Function: Zeros and Deterministic Approximation
• Location of zeros for the partition function of the Ising model on bounded degree graphs
• Zeros of ferromagnetic 2-spin systems

Cited by in corpus (3)

• Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
• Correlation decay and partition function zeros: Algorithms and phase transitions
• Absence of zeros implies strong spatial mixing