Skip to content
DraconiticResearch
Search Sources API
189,280 studies31 sourcesUpdated just now
PreprintarXiv licencearXiv

Optimal Mixing for Local Edge-Coloring Dynamics on Trees

  • Haoran wang
Open at sourcePDFDOICite

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≥Δ+2 and for the neighboring-edge heat-bath dynamics when q≥Δ+1. Both chains mix in OΔ(n(log n+log(1/ε))) 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.

Related

  1. Optimal Mixing of Glauber Dynamics for the Sherrington-Kirkpatrick Model at β< 1/2
    Sihan Wang
    arXivPreprintCC BY 4.0Full textMathematical physicsProbabilityarXiv
  2. Weighting-Based Strategies for Classification: Analysis and Local Peak Dynamics with CART Trees
    Abdoulaye Sakho, Emmanuel Malherbe, Erwan Scornet
    HALPreprintCC BY 4.0Full textStatisticsHALarXiv
  3. Optimal mixing of the systematic scan dynamics via approximate tensorization of entropy
    Antonio Blanca, Md Tahmidur Rafid
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  4. Local-to-Global Theorems Based on Cones with Applications to Graph Coloring
    Anqi Li, Shayan Oveis Gharan
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsProbabilityarXiv
  5. Learning Optimal Prescriptive Trees from Observational Data
    Nathanael Jo, Sina Aghaei, Andrés Gómez +1
    Management SciencePeer-reviewedLicence not statedFull text8 citedStatisticsOpenAlex

Cite

BibTeXRIS
BibTeX
@misc{wang2026optimal,
  title = {{Optimal Mixing for Local Edge-Coloring Dynamics on Trees}},
  author = {Haoran wang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.30625},
  eprint = {2610.30625},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.30625},
}
RIS
TY  - UNPB
TI  - Optimal Mixing for Local Edge-Coloring Dynamics on Trees
AU  - Haoran wang
PY  - 2026
DA  - 2026/10/22
PB  - arXiv
DO  - 10.48550/arxiv.2610.30625
UR  - https://arxiv.org/abs/2610.30625
AB  - 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≥Δ+2 and for the neighboring-edge heat-bath dynamics when q≥Δ+1. Both chains mix in O_Δ(n(log n+log(1/ε))) 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.
ER  -