Perfectly Sampling $k\ge (8/3+o(1))\Delta$-Colorings in Graphs

Abstract

We present a randomized algorithm which takes as input an undirected graph $G$ on $n$ vertices with maximum degree $\Delta$, and a number of colors $k\ge (8/3+o_{\Delta }(1))\Delta$, and returns -- in expected time $\tilde{O}(n{\Delta }^2\log k)$ -- a proper $k$-coloring of $G$ distributed perfectly uniformly on the set of all proper $k$-colorings of $G$. Notably, our sampler breaks the barrier at $k=3\Delta$ encountered in recent work of Bhandari and Chakraborty [STOC 2020]. We also sketch how to modify our methods to relax the restriction on $k$ to $k\ge (8/3-{\epsilon }_0)\Delta$ for an absolute constant ${\epsilon }_0>0$. As in the work of Bhandari and Chakraborty, and the pioneering work of Huber [STOC 1998], our sampler is based on Coupling from the Past [Propp&Wilson, Random Struct. Algorithms, 1995] and the bounding chain method [Huber, STOC 1998; Häggström&Nelander, Scand. J. Statist., 1999]. Our innovations include a novel bounding chain routine inspired by Jerrum's analysis of the Glauber dynamics [Random Struct. Algorithms, 1995], as well as a preconditioning routine for bounding chains which uses the algorithmic Lovász Local Lemma [Moser&Tardos, J.ACM, 2010].

21 pages; comments welcome!