Abstract : 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 recent 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, unlike Markov chain based algorithms, 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 asymptotically $(1.494\ldots)^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 asymptotically $(q(1-{1\over q})^{r\over 2})^n$, for large $n$. In statistical physics terminology, we compute explicitly the partition function (free energy) in these cases. We extend our results to random regular graphs graphs also. The explicit results obtained in this paper would be hard to derive via Markov chain sampling technique.
[Joint work with David Gamarnik]