Abstract
We study local Markov chains for sampling 3-colorings of the discrete torus . We show that there is a constant such that for all even and 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 that updates the color of at most vertices at each step and whose stationary distribution is uniform, then the convergence to stationarity of $\cM$ is exponential in . Our proof is based on a conductance argument that builds on sensitive new combinatorial enumeration techniques.
Connections
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 review
No reviews yet.
Discussion 0
Add a comment
No comments yet.