Counting without sampling: Asymptotics of the log‐partition function for certain statistical physics models

Authors:
Publisher website
Google Scholar
Abstract
In this article we propose new methods for computing the asymptotic value for the logarithm of the partition function (free energy) for certain statistical physics models on certain type of finite graphs, as the size of the underlying graph goes to infinity. The two models considered are thehard‐core(independent set) model when theactivityparameter λis small, and also the Potts (q‐coloring) model. We only consider the graphs withlarge girth. In particular, we prove that asymptotically the logarithm of the number ofindependent setsof anyr‐regular graph with large girth when rescaled is approximately constant ifr≤ 5. For example, we show that every 4‐regularn‐node graph with large girth has approximately (1.494…)n‐many independent sets, for largen. Further, we prove that for everyr‐regular graph withr≥ 2, withnnodes and large girth, the number of properq≥r+ 1 colorings is approximately${[q{(1 - {1 \over q})}^{r \over 2} ]^n}$ n, for largen. We also show that these results hold for random regular graphs with high probability (w.h.p.) as well.As a byproduct of our method we obtain simple algorithms for the problem of computing approximately the logarithm of the number of independent sets and proper colorings, in low degree graphs with large girth. These algorithms are deterministic and use certain correlation decay properties for the corresponding Gibbs measures, and its implications to uniqueness of the Gibbs measures on the infinite trees, as well as some simplecavity trickwhich is well known in the physics and the Markov chain sampling literature.© 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008

This publication has 26 references indexed in Scilit: