pipette
ENEnglish

Optimal Mixing for Local Edge-Coloring Dynamics on Trees

Haoran wang

Preprint

En palabras de los autores

We study the mixing time of two local Markov chains for uniformly sampling proper edge colorings of trees. For a tree with vertices and maximum degree , we establish optimal mixing-time bounds for the single-edge Glauber dynamics when and for the neighboring-edge heat-bath dynamics when . Both chains mix in steps, uniformly over the number of colors . These bounds are tight in their dependence on 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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 23 de octubre. arXiv. Preprint, todavía sin revisión por pares.