Randomly coloring planar graphs with fewer colors than the maximum degree

Опубликовано 8 сентября 2016, 17:03

We study Markov chains for randomly sampling k-colorings of a graph with maximum degree D. We prove the first results, for a general class of graphs, showing fast convergence of such chains when the number of colors k << D. When D =O((log n)^(1+eps)) and k > D/log D we prove O(n log n) mixing time of the single-site update chain, known as the Glauber dynamics, for any planar graph. This result is tight, there exist planar graphs for which the Glauber dynamics has super-polynomial mixing time whenever k = o(D/ log D). A challenging aspect of the case when D is constant and k < D is that, even in a random coloring, a constant fraction of the vertices are “frozen,” with a unique color not present among its neighbors. To extend our results to this setting, we introduce a new Markov chain which recolors vertices in a partially deterministic order defined in terms of the principal eigenvector of the graph. For this chain we prove nearly-linear time convergence when k > D/ log D. This implies polynomial mixing time of the original Glauber dynamics under the same conditions. Joint work with Thomas P. Hayes and Eric Vigoda.