Correlation decay in statistical physics and applications to counting problems

Опубликовано 6 сентября 2016, 6:02

We propose a new approach 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 approximations only to the logarithm of the total count (log-partition function). But on the positive side, unlike Markov chain based algorithms, our approach provides deterministic guarantee on approximations. Moreover, for regular graphs with large girth we compute explicit limits counting values. For example, we show that every $4$ regular $n$-node graph with large girth has asymptotically $(1.494...)^n$ independent sets, independently of the graph and $(2\sqrt{3})^n$ proper $4$-colorings. In other words we compute the asymptotic limit of the log-partition function. Our results extend  to random regular graphs.   Joint work with Antar Bandyopadhyay.