Uniqueness of uniform random colorings of regular trees

A q-coloring of an infinite graph G is a homomorphism from G to the complete graph Kq on q vertices. A probability measure on the set of q-colorings of G is said to be a Gibbs measure for q-colorings of G for uniform activities if for every finite portion U of G and almost every q-coloring of G[-45 degree rule]U, the conditional distribution on the coloring of U given the coloring of G[-45 degree rule]U is uniform (on the set of colorings that are admissable when the coloring of the boundary of U is taken into account). In Brightwell and Winkler (2000), one studies q-colorings of the r+1-regular tree and among other things it is shown that if q[less-than-or-equals, slant]r+1 there are multiple such Gibbs measures, whereas when r is large enough and q[greater-or-equal, slanted]1.6296r there is a unique Gibbs measure. In this paper the gap is filled in: we show that for r[greater-or-equal, slanted]1000 one has uniqueness as soon as q[greater-or-equal, slanted]r+2. Computer calculations verify that the result is also true for 3[less-than-or-equals, slant]r<1000.