Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree

We address the convergence rate of Markov chains for randomly generating an edge coloring of a given tree. Our focus is on the Glauber dynamics which updates the color at a randomly chosen edge in each step. For a tree T with n vertices and maximum degree Δ, when the number of colors q satisfies q ≥ Δ + 2 then we prove that the Glauber dynamics has an optimal relaxation time of O (n), where the relaxation time is the inverse of the spectral gap. This is optimal in the range of q in terms of Δ as Dyer, Goldberg, and Jerrum (2006) showed that the relaxation time is Ω(n3) when q = Δ + 1. For the case q = Δ + 1, we show that an alternative Markov chain which updates a pair of neighboring edges has relaxation time O (n ). Moreover, for the Δ-regular complete tree we prove O (n log2 n ) mixing time bounds for the respective Markov chain. Our proofs establish approximate tensorization of variance via a novel inductive approach, where the base case is a tree of height ℓ = O (Δ2 log2 Δ), which we analyze using a canonical paths argument.