Counting in two-spin models on d-regular graphs

Allan Sly, Nike Sun

Research output: Contribution to journalArticlepeer-review

55 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)2383-2416
Number of pages34
JournalAnnals of Probability
Volume42
Issue number6
DOIs
StatePublished - 2014

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Keywords

  • Anti-ferromagnetic ising model
  • Bethe free energy
  • Gibbs uniqueness threshold
  • Hard-core model
  • Independent sets
  • Locally tree-like graphs

Fingerprint Dive into the research topics of 'Counting in two-spin models on d-regular graphs'. Together they form a unique fingerprint.

Cite this