COUNTING IN TWO-SPIN MODELS ON d-REGULAR GRAPHS

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 st...

Full description

Saved in:
Bibliographic Details
Published in:The Annals of probability 2014-11, Vol.42 (6), p.2383-2416
Main Authors: Sly, Allan, Sun, Nike
Format: Article
Language:English
Subjects:
60K35
68Q87
82B20
anti-ferromagnetic Ising model
Approximation
Bethe free energy
Flux density
Free energy
Gibbs uniqueness threshold
Graph theory
Hard-core model
Hardness
independent sets
Ising model
locally tree-like graphs
Markov chains
Mathematical functions
Mathematical models
Mathematical moments
Modeling
Physics
Recursion
Studies
Uniqueness
Vertices
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0091-1798
2168-894X
DOI:10.1214/13-AOP888