Optimal Mixing for Local Edge-Coloring Dynamics on Trees

Source abstract

We study the mixing time of two local Markov chains for uniformly sampling proper edge colorings of trees. For a tree with $n$ vertices and maximum degree $Δ$, we establish optimal mixing-time bounds for the single-edge Glauber dynamics when $q\geΔ+2$ and for the neighboring-edge heat-bath dynamics when $q\geΔ+1$. Both chains mix in $O_Δ(n(\log n+\log(1/\varepsilon)))$ steps, uniformly over the number of colors $q$. These bounds are tight in their dependence on $n$ for fixed $Δ$. Our proof establishes log-Sobolev inequalities through local color release, reusable recoloring buffers, and component entropy mixing. The two dynamics require different local constructions: a two-spare-color buffer for single-edge updates and a second-layer controller for neighboring-edge updates. The resulting entropy analysis applies to general bounded-degree trees, including regimes where worst-case spatial mixing fails.