2018/12/13 by Michelle Delcourt, Delcourt, Michelle, Marc Heinrich +3 · 1 citation
Computer Science · Mathematics · #05C15 #60J10 #68W20 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #cs.DM #cs.DS #math.CO #math.PR #msc:05C15 #msc:60J10 #msc:68W20
paper · pdf · doi:10.48550/arxiv.1812.05577
29 pages
arxiv created 2020/07/30 · arxiv updated 2020/07/31
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.