**
Counting without Sampling:
Asymptotics of the log-Partition Function for Certain Statistical Physics
Models
**

**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]