تقرير
Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree
| العنوان: | Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree |
|---|---|
| المؤلفون: | Carlson, Charlie, Chen, Xiaoyu, Feng, Weiming, Vigoda, Eric |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Discrete Mathematics, Computer Science - Data Structures and Algorithms, Mathematics - Probability |
| الوصف: | 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. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2407.04576 |
| رقم الأكسشن: | edsarx.2407.04576 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |