Correlation decay and deterministic FPTAS for counting colorings of a graph

DOI10.1016/j.jda.2010.10.002zbMath1241.05049OpenAlexW2017226731MaRDI 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 functionstatistical physicsapproximation algorithms

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Correlation decay and the absence of zeros property of partition functions, Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite \(\Delta \)-regular tree for large \(\Delta \), Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials, Counting Independent Sets and Colorings on Random Regular Bipartite Graphs, Counting hypergraph matchings up to uniqueness threshold, Uniqueness for the 3-state antiferromagnetic Potts model on the tree, Strong spatial mixing in homomorphism spaces, An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution, On a conjecture of Sokal concerning roots of the independence polynomial, Uniqueness of Gibbs measures for continuous hardcore models, Strong spatial mixing of list coloring of graphs, Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs

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