Correlation decay in statistical physics and applications to counting problems

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√{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.

Speaker Details

David Gamarnik received B.A. in mathematics from New York University in 1993 and Ph.D. in Operations Research from MIT in 1998. Since then he worked as a research staff member in IBM Research, Department of Mathematical Sciences, before joining Operations Research Group in MIT in Sloan School of Management in 2005.His research interests include applied probability and stochastic processes with application to queueing theory, probabilistic analysis of combinatorial structures and algorithms. He is a recipient of an Erlang Prize from INFORMS Applied Probability Society in 2004.

Date:
Speakers:
David Gamarnik
Affiliation:
MIT Sloan School of Management