A non-Markovian coupling for randomly sampling colorings

Abstract

We study a simple Markov chain, known as the Glauber dynamics, for randomly sampling (proper) k-colorings of an input graph G on n vertices with maximum degree /spl Delta/ and girth g. We prove the Glauber dynamics is close to the uniform distribution after O(n log n) steps whenever k > (1 + /spl epsiv/)/spl Delta/, for all /spl epsiv/ > 0, assuming g /spl ges/ 9 and /spl Delta/ = /spl Omega/(log n). The best previously known bounds were k > 11/spl Delta//6 for general graphs, and k > 1.489/spl Delta/ for graphs satisfying girth and maximum degree requirements. Our proof relies on the construction and analysis of a non-Markovian coupling. This appears to be the first application of a non-Markovian coupling to substantially improve upon known results.