Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
The Glauber Dynamics for Colourings of Bounded Degree Trees
verfasst von : Brendan Lucier, Michael Molloy, Yuval Peres
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the Glauber dynamics Markov chain for
k
-colourings of trees with maximum degree Δ. For
k
≥ 3, we show that the mixing time on
every
tree is at most
n
O
(1 + Δ/(
k
logΔ))
. This bound is tight up to the constant factor in the exponent, as evidenced by the complete tree. Our proof uses a weighted canonical paths analysis and a variation of the block dynamics that exploits the differing relaxation times of blocks.