A Deterministic Algorithm for Counting Colorings with 2-Delta Colors

We give a polynomial time deterministic approximation algorithm (an FPTAS) for counting the number of q-colorings of a graph of maximum degree Delta, provided only that q ≥ 2Delta. This substantially improves on previous deterministic algorithms for this problem, the best of which requires q ≥ 2. 58Delta, and matches the natural bound for randomized algorithms obtained by a straightforward application of Markov chain Monte Carlo. In the case when the graph is also triangle-free, we show that our algorithm applies under the weaker condition q ≥ αΔ+β, where α ≈ 1. 764 and β = β(α) are absolute constants. Our result applies more generally to list colorings, and to the partition function of the anti-ferromagnetic Potts model. The core of our argument is the establishment of a region in the complex plane in which the Potts model partition function (a classical graph polynomial) has no zeros. This result, which substantially sharpens previous work on the same problem, is of independent interest. Our algorithms follow immediately from zero-freeness via the “polynomial interpolation" method of Barvinok. Interestingly, our method for identifying the zero-free region leverages probabilistic and combinatorial ideas that have been used in the analysis of Markov chains.

Authors

• Jingcheng Liu 0001
• Alistair Sinclair
• Piyush Srivastava 0001

Keywords

• Approximation algorithms
• Color
• Markov processes
• Partitioning algorithms
• Heuristic algorithms
• Correlation
• Interpolation
• Markov Chain
• Potential Model
• Maximum Degree
• Partition Function
• Complex Plane
• Polynomial Interpolation
• Loss Of Generality
• Markov Chain Monte Carlo
• Imaginary Part
• Proof Of Theorem
• Complex Numbers
• Base Case
• Rest Of This Section
• Vertices
• Theorem States
• Marginal Probability
• Statistical Physics
• Proof Of The Lemma
• Mean Value Theorem
• List Size
• Induction Hypothesis
• Decay Of Correlations
• Strong Mixing
• Lemma States
• Trivially True
• Class Of Graphs
• Polynomial Of Degree
• Real Axis
• Actual Probability
• Triangle Inequality
• Approximate counting, Graph coloring, Potts model, Partition function, Stability theory, De randomization