{"id":"arxiv/2610.30625","url":"https://arxiv.org/abs/2610.30625","tags":["cs.DS","math.PR"],"score":0,"title":"Optimal Mixing for Local Edge-Coloring Dynamics on Trees","domain":"cs.DS","source":"arxiv","authors":["Haoran wang"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-22","reactions":{}}