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

Abstract

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(nlog2 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.