Correlation decay and deterministic FPTAS for counting colorings of a graph

Bandyopadhyay, 2008, Counting without sampling. Asymptotics of the log-partition function for certain statistical physics models, Random Structures Algorithms, 33, 452, 10.1002/rsa.20236 M. Bayati, D. Gamarnik, D. Katz, C. Nair, P. Tetali, Simple deterministic approximation algorithms for counting matchings, in: Proc. 39th Ann. Symposium on the Theory of Computing (STOC), 2007. Brightwell, 2002, Random colorings of a Cayley tree, 247 Brightwell, 2004, Graph homomorphisms and long range action, 29 Dobrushin, 1970, Prescribing a system of random variables by the help of conditional distributions, Theory Probab. Appl., 15, 469, 10.1137/1115049 Frieze, 2006, Survey of Markov chains for randomly sampling colorings D. Gamarnik, D. Katz, Correlation decay and deterministic FPTAS for counting list-colorings of a graph, in: Proceedings of 18th ACM–SIAM Symposium on Discrete Algorithms (SODA), 2007. Gamarnik, 2009, Sequential cavity method for computing free energy and surface pressure, J. Stat. Phys., 137, 205, 10.1007/s10955-009-9849-3 Gamarnik, 2010, A deterministic approximation algorithm for computing a permanent of a 0,1 matrix, J. Comput. System Sci., 76, 879, 10.1016/j.jcss.2010.05.002 Goldberg, 2005, Strong spatial mixing with fewer colors for lattice graphs, SIAM J. Comput., 35, 486, 10.1137/S0097539704445470 Jerrum, 1995, A very simple algorithm for estimating the number of k-colourings of a low-degree graph, Random Structures Algorithms, 7, 157, 10.1002/rsa.3240070205 M. Jerrum, Counting, sampling and integrating: algorithms and complexity, Lecture notes, 2006, Chapter 3. Jerrum, 1997, The Markov chain Monte Carlo method: an approach to approximate counting and integration Jonasson, 2002, Uniqueness of uniform random colorings of regular trees, Statist. Probab. Lett., 57, 243, 10.1016/S0167-7152(02)00054-8 Jordan, 2004, Graphical models, Statist. Sci. (Special Issue on Bayesian Statistics), 19, 140 K. Jung, D. Shah, On correctness of belief propagation algorithm, preprint, 2006. Kelly, 1985, Stochastic models of computer communication systems, J. R. Stat. Soc. Ser. B, 47, 379 Salas, 1997, Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem, J. Stat. Phys., 86, 551, 10.1007/BF02199113 Scott, 2005, The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma, J. Stat. Phys., 118, 1151, 10.1007/s10955-004-2055-4 Spitzer, 1975, Markov random fields on an infinite tree, Ann. Probab., 3, 387, 10.1214/aop/1176996347 Tatikonda, 2002, Loopy belief propagation and Gibbs measures L. Trevisan, Pseudorandomness and combinatorial constructions, in: Proceedings of ICM, Madrid, 2006. Vigoda, 2000, Improved bounds for sampling colorings, J. Math. Phys., 41, 1555, 10.1063/1.533196 Wainwright, 2005, A variational principle for graphical models D. Weitz, Counting independent sets up to the tree threshold, in: Proc. 38th Ann. Symposium on the Theory of Computing, 2006. J. Yedidia, W. Freeman, Y. Weiss, Understanding belief propagation and its generalizations, Mitsubishi Elect. Res. Lab., 2000, No. TR-2001-22. S. Zachary, Countable state space Markov random fields and Markov chains on tree, Ann. Probab. 11, 894–903.