COUNTING IN TWO-SPIN MODELS ON d-REGULAR GRAPHS

• 成果类型: Article
• 署名作者: Sly, Allan; Sun, Nike
• 署名单位: University of California System; University of California Berkeley; Australian National University; Stanford University
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/13-AOP888
• 发表日期: 2014
• 页码: 2383-2416
• 关键词: phase-transitions; independent sets; hardness

摘要

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.