Treffer: CORRELATION DECAY AND PARTITION FUNCTION ZEROS: ALGORITHMS AND PHASE TRANSITIONS.

We explore connections between the phenomenon of correlation decay (more precisely, strong spatial mixing) and the location of Lee--Yang and Fisher zeros for various spin systems. In particular we show that, in many instances, proofs showing that weak spatial mixing on the Bethe lattice (infinite Δ -regular tree) implies that strong spatial mixing on all graphs of maximum degree Δ can be lifted to the complex plane, establishing the absence of zeros of the associated partition function in a complex neighborhood of the region in parameter space corresponding to strong spatial mixing. This allows us to give unified proofs of several recent results of this kind, including the resolution by Peters and Regts of the Sokal conjecture for the partition function of the hard-core lattice gas. It also allows us to prove new results on the location of Lee--Yang zeros of the antiferromagnetic Ising model. We show further that our methods extend to the case when weak spatial mixing on the Bethe lattice is not known to be equivalent to strong spatial mixing on all graphs. In particular, we show that results on strong spatial mixing in the antiferromagnetic Potts model can be lifted to the complex plane to give new zero-freeness results for the associated partition function, significantly sharpening previous results of Sokal and others. This new extension is also of independent algorithmic interest: it allows us to give the first polynomial time deterministic approximation algorithm (a fully polynomial time approximation scheme (FPTAS)) for counting the number of q-colorings of a graph of maximum degree Δ provided only that q ≥ 2Δ, a question that has been studied intensively. This matches the natural bound for randomized algorithms obtained by a straightforward application of Markov chain Monte Carlo. In the case when the graph is also triangle-free, we show that our algorithm applies under the weaker condition q ≥ αΔ + β, where α ≈ 1.764 and β = α(α) are absolute constants. [ABSTRACT FROM AUTHOR]

Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)