The Glauber dynamics for edge‐colorings of trees. Issue 4 (26th September 2020) - Delcourt, Michelle; Heinrich, Marc; Perarnau, Guillem
Abstract : Let T be a tree on n vertices and with maximum degree Δ . We show that for k ≥ Δ + 1 the Glauber dynamics for k ‐edge‐ colorings of T mixes in polynomial time in n . The bound on the number of colors 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.