THE GLAUBER DYNAMICS FOR COLORINGS OF BOUNDED DEGREE TREES

摘要

We study the Glauber dynamics Markov chain for k-colorings of trees with maximum degree A. For k ≥ 3, we show that the mixing time on the complete tree is n~(°<1+Δ/(k log Δ))). For k ≥ 4 we extend our analysis to show that the mixing time on any tree is at most n°(1+AA' los A>). Our proof uses a weighted canonical paths analysis and introduces a variation of the block dynamics that exploits the differing relaxation times of blocks.