The Glauber dynamics for edges colourings of trees
share
Let T be a tree on n vertices and with maximum degree Δ. We show that for k≥Δ+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 ≤Δ. 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.
READ FULL TEXT