Counting in two-spin models on d-regular graphs
Date
2014
Authors
Sly, Allan
Sun, Nike
Journal Title
Journal ISSN
Volume Title
Publisher
Institute of Mathematical Statistics
Abstract
We establish that the normalized log-partition function of any two-spin
system on bipartite locally tree-like graphs converges to a limiting “free
energy density” which coincides with the (nonrigorous) Bethe prediction of
statistical physics. Using this result, we characterize the local structure of
two-spin systems on locally tree-like bipartite expander graphs without the
use of the second moment method employed in previous works on these questions.
As a consequence, we show that for both the hard-core model and the
anti-ferromagnetic Ising model with arbitrary external field, it is NP-hard to
approximate the partition function or approximately sample from the model
on d-regular graphs when the model has nonuniqueness on the d-regular tree.
Together with results of Jerrum–Sinclair, Weitz, and Sinclair–Srivastava–
Thurley, this gives an almost complete classification of the computational
complexity of homogeneous two-spin systems on bounded-degree graphs.
Description
Keywords
Hard-core model, independent sets, anti-ferromagnetic Ising model, locally tree-like graphs, Bethe free energy, Gibbs uniqueness threshold
Citation
Collections
Source
The Annals of Probability
Type
Journal article
Book Title
Entity type
Access Statement
Open Access
License Rights
Restricted until
Downloads
File
Description
Published Version