A Deterministic Algorithm for Counting Colorings with 2∆ Colors (Jingcheng Liu)
We give a polynomial time deterministic approximation algorithm (an FPTAS) for counting the number of q-colorings of a graph of maximum degree ∆, provided only that q ≥ 2∆. This substantially improves on previous deterministic algorithms for this problem, the best of which requires q ≥ 2.58∆, and matches the natural bound for randomized algorithms obtained by a straightforward application of Markov chain Monte Carlo. In the special case when the graph is also triangle-free, we show that our algorithm applies under the 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. Our algorithm exploits the so-called “polynomial interpolation” method of Barvinok, identifying a suitable region of the complex plane in which the Potts model partition function has no zeros. Interestingly, our method for identifying this zero-free region leverages probabilistic and combinatorial ideas that have been used in the analysis of Markov chains.
Based on joint work with Alistair Sinclair and Piyush Srivastava.
2019-05-08 14:00 ~ 15:00
Jingcheng Liu, UC Berkeley
Room 602, School of Information Management & Engineering, Shanghai University of Finance & Economics