Correlation decay and deterministic FPTAS for counting colorings of a graph

DOI10.1016/j.jda.2010.10.002zbMath1241.05049MaRDI QIDQ414468

J. Herrera, H. S. Yoon

Publication date: 11 May 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2010.10.002

zbMATH Keywords

partition function; statistical physics; approximation algorithms

Mathematics Subject Classification ID

05C30: Enumeration in graph theory

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials, Strong spatial mixing of list coloring of graphs, Strong spatial mixing in homomorphism spaces, An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution, Counting hypergraph matchings up to uniqueness threshold, Uniqueness for the 3-state antiferromagnetic Potts model on the tree, Uniqueness of Gibbs measures for continuous hardcore models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Countable state space Markov random fields and Markov chains on trees
• Sequential cavity method for computing free energy and surface pressure
• Markov random fields on an infinite tree
• Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem
• Uniqueness of uniform random colorings of regular trees
• A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• Improved bounds for sampling colorings
• Counting independent sets up to the tree threshold
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Strong Spatial Mixing with Fewer Colors for Lattice Graphs
• Pseudorandomness and Combinatorial Constructions
• Prescribing a System of Random Variables by Conditional Distributions
• Graphical models