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

Abstract

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 [Formula: see text] with [Formula: see text] vertices and maximum degree [Formula: see text], when the number of colors [Formula: see text] satisfies [Formula: see text], we prove that the Glauber dynamics has an optimal relaxation time of [Formula: see text], where the relaxation time is the inverse of the spectral gap. This is optimal in the range of [Formula: see text] in terms of [Formula: see text], as Dyer, Goldberg, and Jerrum [ Ann. Appl. Probab., 16 (2006), pp. 185–230] showed that the relaxation time is [Formula: see text] when [Formula: see text]. For the case [Formula: see text], we show that an alternative Markov chain, called neighboring edge dynamics, which updates a pair of neighboring edges, has relaxation time [Formula: see text]. Moreover, for the [Formula: see text]-regular complete tree, we prove [Formula: see text] mixing time bounds for the Glauber dynamics when [Formula: see text]. Our proofs establish approximate tensorization of variance via a novel inductive approach where the base case is a tree of height [Formula: see text], which we analyze using a canonical path argument.