Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree
<|reference_start|>Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree: 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 $T$ with $n$ vertices and maximum degree $\Delta$, when the number of colors $q$ satisfies $q\geq\Delta+2$ then we prove that the Glauber dynamics has an optimal relaxation time of $O(n)$, where the relaxation time is the inverse of the spectral gap. This is optimal in the range of $q$ in terms of $\Delta$ as Dyer, Goldberg, and Jerrum (2006) showed that the relaxation time is $\Omega(n^3)$ when $q=\Delta+1$. For the case $q=\Delta+1$, we show that an alternative Markov chain which updates a pair of neighboring edges has relaxation time $O(n)$. Moreover, for the $\Delta$-regular complete tree we prove $O(n\log^2{n})$ mixing time bounds for the respective Markov chain. Our proofs establish approximate tensorization of variance via a novel inductive approach, where the base case is a tree of height $\ell=O(\Delta^2\log^2{\Delta})$, which we analyze using a canonical paths argument.<|reference_end|>
@article{carlson2024optimal,
    title={Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the
  Max Degree},
    author={Charlie Carlson, Xiaoyu Chen, Weiming Feng, Eric Vigoda},
    journal={arXiv preprint arXiv:2407.04576},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.04576},
    primaryClass={cs.DM cs.DS math.PR}
}