Abstract
For antiferromagnetic 2spin systems, a beautiful connection has been established, namely that the following three notions align perfectly: the uniqueness in infinite regular trees, the decay of correlations (also known as spatial mixing), and the approximability of the partition function. The uniqueness condition implies spatial mixing, and an FPTAS for the partition function exists based on spatial mixing. On the other hand, nonuniqueness implies some long range correlation, based on which NPhardness reductions are built. These connections for ferromagnetic 2spin systems are much less clear, despite their similarities to antiferromagnetic systems. The celebrated JerrumSinclair Markov chain [JS93] works even if spatial mixing or uniqueness fails.
We provide some partial answers. We use (β,γ) to denote the (+,+) and (−,−) edge interactions and λ the external field, where βγ>1. If all fields satisfy λ<λ_c (assuming β≤γ), where λ_c=(γ/β)^{(Δ_c+1)/2} and Δ_c=(\sqrt{βγ}+1)/(\sqrt{βγ}−1), then a weaker version of spatial mixing holds in all trees. Moreover, if β≤1, then λ<λ_c is sufficient to guarantee strong spatial mixing and FPTAS. This improves the previous best algorithm, which is an FPRAS based on Markov chains and works for λ<γ/β [LLZ14a]. The bound λ_c is almost optimal. When β≤1, uniqueness holds in all infinite regular trees, if and only if λ≤λ^int_c, where λ^int_c=(γ/β)(⌈Δc⌉+1)/2. If we allow fields λ>λ^int′_c, where λ^int′_c=(γ/β)(⌊Δc⌋+2)/2, then approximating the partition function is #BIShard.
BibTeX  Entry
@InProceedings{guo_et_al:LIPIcs:2016:6654,
author = {Heng Guo and Pinyan Lu},
title = {{Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2Spin Systems}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
pages = {31:131:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770187},
ISSN = {18688969},
year = {2016},
volume = {60},
editor = {Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6654},
URN = {urn:nbn:de:0030drops66547},
doi = {10.4230/LIPIcs.APPROXRANDOM.2016.31},
annote = {Keywords: Approximate counting; Ising model; Spin systems; Correlation decay}
}
Keywords: 

Approximate counting; Ising model; Spin systems; Correlation decay 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) 
Issue Date: 

2016 
Date of publication: 

06.09.2016 