Phase transition for the mixing time of the Glauber dynamics for coloring regular trees (Q1931316): Difference between revisions

The authors prove that the mixing time of the Glauber dynamics for random \(k\)-colorings of the complete tree with branching factor \(b\) undergoes a phase transition at \(b(1+ o_b(1))/\ln b\). They emphasize that the main result provides (nearly) sharp bounds on the mixing time and relaxation time of the Glauber dynamics for the complete tree, establishing a phase transition at the critical point \(k= b(1+ o_b(1))/\ln b\). The paper is conceived in 9 sections. After an Introduction (Section 1), in Section 2 is given an outline of the proofs of Theorem 1. Section 3 contains definitions and background materials. Upper bound on mixing time for \(C\leq 1\): proof of Theorem 4 is the subject of Section 4. In the next section the authors analyze the upper bound of the mixing time of the Glauber dynamics on the star graph \(G^*\) when \(k= Cb/\ln b\) for \(C>1\). Section 6 is devoted to the proof of the lower bounds below the threshold in Theorem 1; and a simple generalization to \(k= o(b/\ln b)\): proof of Theorem 2 is the topic of Section 7. Section 8 contains bounding the log-Sobolev constant: proof of Theorem 6; and in the last section are inserted some conclusions. From the reviewer's viewpoint, this is a very good and instructive paper.