Premium
The Glauber dynamics for edge‐colorings of trees
Author(s) -
Delcourt Michelle,
Heinrich Marc,
Perarnau Guillem
Publication year - 2020
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20960
Subject(s) - glauber , mathematics , combinatorics , tree (set theory) , monotonic function , ergodic theory , degree (music) , discrete mathematics , enhanced data rates for gsm evolution , upper and lower bounds , block (permutation group theory) , relaxation (psychology) , computer science , pure mathematics , physics , mathematical analysis , scattering , optics , psychology , telecommunications , social psychology , acoustics
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.