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 (n³) 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²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 (²²), which we analyze using a canonical paths argument.