arXiv preprint ·
Optimal Mixing for Local Edge-Coloring Dynamics on Trees
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
On the continuity of conditional distributions and stratification for derivative pricing
Multiple Stopping and Exercise Boundaries for American Put Options
A Gaussian Process State Space Formulation for Materials Constitutive Modeling: Application to Quasi-brittle Materials
Dimension-free regimes for unadjusted Langevin in ridge-separable models: A subspace robust Wasserstein analysis
Kernelised covariance matrices, dimension reduction and imbalanced spectral clustering
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.