The Mixing Time of Glauber Dynamics for Colouring Regular Trees

2008/06/05 by Leslie Ann Goldberg, Mark Jerrum, Goldberg, Leslie Ann +4 · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics #cs.CC #cs.DM

paper · pdf · doi:10.48550/arxiv.0806.0921

arxiv created 2008/06/05 · openalex publication_date 2008/06/05 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider Metropolis Glauber dynamics for sampling proper q-colourings of the n-vertex complete b-ary tree when 3≤ q≤ b/2ln(b). We give both upper and lower bounds on the mixing time. For fixed q and b, our upper bound is n^{O(b/log b)} and our lower bound is n^{Ω(b/q log(b))}, where the constants implicit in the O() and Ω() notation do not depend upon n, q or b.

Cited by

• Faster Mixing of the Jerrum-Sinclair Chain

Related

• Glauber dynamics for colourings of chordal graphs and graphs of bounded treewidth
• The Glauber dynamics for edge-colourings of trees
• Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree
• Glauber Dynamics of colorings on trees
• Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets