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 the hard-core (independent set) model when the activity parameter λ is small, and also the Potts (q-coloring) model. We only consider the graphs with large girth. In particular, we prove that asymptotically the logarithm of the number of independent sets of any r-regular graph with large girth when rescaled is approximately constant if r ≥ 5. For example, we show that every 4-regular n-node graph with large girth has approximately (1.494 ...)n -many independent sets, for large n. Further, we prove that for every r-regular graph with r ≥ 2, with n nodes and large girth, the number of proper q ≥ r + 1 colorings is approximately [q(1 - 1/q )r/2]n, for large n. 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
[Joint work with David Gamarnik]