Zero-Freeness is All You Need: A Weitz-Type FPTAS for the Entire Lee-Yang Zero-Free Region
Preprint
Abstract
We present a Weitz-type FPTAS for the ferromagnetic Ising model across the entire Lee-Yang zero-free region, without relying on the strong spatial mixing (SSM) property. Our algorithm is Weitz-type for two reasons. First, it expresses the partition function as a telescoping product of ratios, with the key being to approximate each ratio. Second, it uses Weitz's self-avoiding walk tree, and truncates it at logarithmic depth to give a good and efficient approximation. The key difference from the standard Weitz algorithm is that we approximate a carefully designed edge-deletion ratio instead of the marginal probability of a vertex's spin, ensuring our algorithm does not require SSM. Furthermore, by establishing local dependence of coefficients (LDC), we indeed prove a novel form of SSM for these edge-deletion ratios, which, in turn, implies the standard SSM for the random cluster model. This is the first SSM result for the random cluster model on general graphs, beyond lattices. We prove LDC using a new division relation, and remarkably, such relations hold quite universally. As a result, we establish LDC for a variety of models. Combined with existing zero-freeness results for these models, we derive new SSM results for them. Our work suggests that both Weitz-type FPTASes and SSM can be derived from zero-freeness, while zero-freeness alone suffices for Weitz-type FPTASes, SSM additionally requires LDC, a combinatorial property independent of zero-freeness.Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Optimal Zero‐Free Regions for the Independence Polynomial of Bounded Degree HypergraphsRandom Structures & Algorithms, 2025
- Swendsen-Wang dynamics for the ferromagnetic Ising model with external fieldsInformation and Computation, 2023
- Contraction: A Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin SystemsJournal of Statistical Physics, 2021
- Fisher zeros and correlation decay in the Ising modelJournal of Mathematical Physics, 2019
- Combinatorics and Complexity of Partition Functions2016
- Approximation Algorithms for Two-State Anti-Ferromagnetic Spin Systems on Bounded Degree GraphsJournal of Statistical Physics, 2014
- Approximating partition functions of the two-state spin systemInformation Processing Letters, 2011
- Counting without sampling: Asymptotics of the log‐partition function for certain statistical physics modelsRandom Structures & Algorithms, 2008
- Ising model in half-space: A series of phase transitions in low magnetic fieldsTheoretical and Mathematical Physics, 2007
- The multivariate Tutte polynomial (alias Potts model) for graphs and matroids2005