  We propose a new type of approximate counting algorithms for the problems of
enumerating the number of independent sets and proper colorings in low degree
graphs with large girth. Our algorithms are not based on a commonly used Markov
chain technique, but rather are inspired by developments in statistical physics
in connection with correlation decay properties of Gibbs measures and its
implications to uniqueness of Gibbs measures on infinite trees, reconstruction
problems and local weak convergence methods.
  On a negative side, our algorithms provide $\epsilon$-approximations only to
the logarithms of the size of a feasible set (also known as free energy in
statistical physics). But on the positive side, our approach provides
deterministic as opposed to probabilistic guarantee on approximations.
Moreover, for some regular graphs we obtain explicit values for the counting
problem. For example, we show that every 4-regular $n$-node graph with large
girth has approximately $(1.494...)^n$ independent sets, and in every
$r$-regular graph with $n$ nodes and large girth the number of $q\geq
r+1$-proper colorings is approximately $[q(1-{1\over q})^{r\over 2}]^n$, for
large $n$. In statistical physics terminology, we compute explicitly the limit
of the log-partition function. We extend our results to random regular graphs.
Our explicit results would be hard to derive via the Markov chain method.
