2026-07-26T05:18:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12503 2024-03-06T10:50:18Z ddc:004 open_access

Contraction: A Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems Shao, Shuai Sun, Yuxin 2-Spin system Correlation decay Zero-freeness Phase transition Contraction 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 are able to extend the existence of correlation decay to these complex regions from real parameters. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shuai Shao and Yuxin Sun 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.96 urn:nbn:de:0030-drops-125036 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.96 eng https://creativecommons.org/licenses/by/3.0/legalcode