Correlation decay and deterministic FPTAS for counting colorings of a graph
From MaRDI portal
Publication:414468
DOI10.1016/j.jda.2010.10.002zbMath1241.05049MaRDI QIDQ414468
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
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, Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs, Strong spatial mixing of list coloring of graphs, Strong spatial mixing in homomorphism spaces, Counting Independent Sets and Colorings on Random Regular Bipartite Graphs, 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 \), 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, On a conjecture of Sokal concerning roots of the independence polynomial, Uniqueness of Gibbs measures for continuous hardcore models
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item