Eric Vigoda

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 [Formula: see text] with [Formula: see text] verti...