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

2012/06/14 by David Galvin, Galvin, David, Dana Randall +1
Computer Science · Mathematics · #05C15 #68R10 #68W25 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.1206.3193

openalex publication_date 2012/06/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 ρ≈ .22 such that for all even L ≥ 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 ρ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.

Related

• Phase coexistence and torpid mixing in the 3-coloring model on Z^d
• Mixing Time on the Kagome Lattice
• Sampling 3-colourings of regular bipartite graphs
• Rapid mixing in Markov chains
• Mixing time for the random walk on the range of the random walk on tori