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

preprint2012arXivOpen access

Abstract

We study local Markov chains for sampling 3-colorings of the discrete torus TL,d=0,...,L−1dT_{L,d}={0,..., L-1}^d. We show that there is a constant ρ≈.22ρ\approx .22 such that for all even L≥4L \geq 4 and dd 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 TL,dT_{L,d} that updates the color of at most ρLdρL^d vertices at each step and whose stationary distribution is uniform, then the convergence to stationarity of $\cM$ is exponential in Ld−1L^{d-1}. Our proof is based on a conductance argument that builds on sensitive new combinatorial enumeration techniques.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.