Counting in two-spin models on d-regular graphs
Authors:
- Allan SlyASAllan Sly
- Nike SunNSNike Sun
Open Access
- 1 November 2014
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Probability
- Vol. 42 (6) , 2383-2416
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.Keywords
This publication has 23 references indexed in Scilit:
- The weak limit of Ising models on locally tree-like graphsProbability Theory and Related Fields, 2010
- Gibbs measures and phase transitions on sparse random graphsBrazilian Journal of Probability and Statistics, 2010
- Ising models on locally tree-like graphsThe Annals of Applied Probability, 2010
- On the hardness of sampling independent sets beyond the tree thresholdProbability Theory and Related Fields, 2008
- On the maximum satisfiability of random formulasJournal of the ACM, 2007
- The two possible values of the chromatic number of a random graphAnnals of Mathematics, 2005
- Rigorous location of phase transitions in hard optimization problemsNature, 2005
- Polynomial-Time Approximation Algorithms for the Ising ModelSIAM Journal on Computing, 1993
- Countable State Space Markov Random Fields and Markov Chains on TreesThe Annals of Probability, 1983
- Statistical theory of superlatticesProceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 1935