Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree
Charlie Carlson, Xiaoyu Chen, Weiming Feng, Eric Vigoda
Source 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.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.