Torpid Mixing of Local Markov Chains on 3-Colorings of the Discrete Torus

Abstract

We study local Markov chains for sampling 3-colorings of the discrete torus $T_{L,d}={0,...,L-1}^d$. We show that there is a constant $\rho \approx .22$ such that for all even $L\ge 4$ and $d$ sufficiently large, certain local Markov chains require exponential time to converge to equilibrium. More precisely, if $\cM$ is a Markov chain on the set of proper 3-colorings of $T_{L,d}$ that updates the color of at most $\rho L^d$ vertices at each step and whose stationary distribution is uniform, then the convergence to stationarity of $\cM$ is exponential in $L^{d-1}$. Our proof is based on a conductance argument that builds on sensitive new combinatorial enumeration techniques.

9 pages. Originally appeared in the proceedings of SODA 2007