The Glauber dynamics for edge-colourings of trees

Abstract

Let $T$ be a tree on $n$ vertices and with maximum degree $\Delta$. We show that for $k\ge \Delta +1$ the Glauber dynamics for $k$-edge-colourings of $T$ mixes in polynomial time in $n$. The bound on the number of colours is best possible as the chain is not even ergodic for $k\le \Delta$. Our proof uses a recursive decomposition of the tree into subtrees; we bound the relaxation time of the original tree in terms of the relaxation time of its subtrees using block dynamics and chain comparison techniques. Of independent interest, we also introduce a monotonicity result for Glauber dynamics that simplifies our proof.

29 pages

References in corpus (7)

• Absence of Phase Transition for Antiferromagnetic Potts Models via the Dobrushin Uniqueness Theorem
• Reconstruction of Random Colourings
• Systematic scan for sampling colorings
• Linear Programming Bounds for Randomly Sampling Colorings
• Rapid mixing of Glauber dynamics for colorings below Vigoda's $11/6$ threshold
• Randomly coloring graphs of bounded treewidth
• Efficient Generation of One-Factorizations through Hill Climbing