Counting without sampling. New algorithms for enumeration problems using statistical physics

Details Counting without sampling. New algorithms for enumeration problems using statistical physics Counting without sampling. New algorithms for enumeration problems using statistical physics

2005-10-21

arxiv.org/abs/math/0510471v1

Mathematics

Probability

23 pages 1 figure

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Counting without sampling. New algorithms for enumeration problems using statistical physics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Counting without sampling. New algorithms for enumeration problems using statistical physics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting without sampling. New algorithms for enumeration problems using statistical physics will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-89559