The Glauber dynamics for edge‐colorings of trees. Issue 4 (26th September 2020)

• Record Type: Journal Article
• Authors: Delcourt, Michelle; Heinrich, Marc; Perarnau, Guillem
• Is Part Of: Random structures & algorithms. Volume 57:Issue 4(2020)
• Page Start: 1050
• Page End: 1076
• Publication Date: 2020-09-26
• Subjects: edge‐colorings -- glauber dynamics -- rapid mixing -- trees; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20960
• Languages: English
• ISSNs: 1042-9832

Abstract

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.