  Consider $k$-colorings of the complete tree of depth $\ell$ and branching
factor $\Delta$. If we fix the coloring of the leaves, as $\ell$ tends to
$\infty$, for what range of $k$ is the root uniformly distributed over all $k$
colors? This corresponds to the threshold for uniqueness of the infinite-volume
Gibbs measure. It is straightforward to show the existence of colorings of the
leaves which ``freeze'' the entire tree when $k\le\Delta+1$. For
$k\geq\Delta+2$, Jonasson proved the root is ``unbiased'' for any fixed
coloring of the leaves and thus the Gibbs measure is unique. What happens for a
{\em typical} coloring of the leaves? When the leaves have a non-vanishing
influence on the root in expectation, over random colorings of the leaves,
reconstruction is said to hold. Non-reconstruction is equivalent to extremality
of the free-boundary Gibbs measure. When $k<\Delta/\ln{\Delta}$, it is
straightforward to show that reconstruction is possible and hence the measure
is not extremal.
  We prove that for $C>1$ and $k =C\Delta/\ln{\Delta}$, that the Gibbs measure
is extremal in a strong sense: with high probability over the colorings of the
leaves the influence at the root decays exponentially fast with the depth of
the tree. Closely related results were also proven recently by Sly. The above
strong form of extremality implies that a local Markov chain that updates
constant sized blocks has inverse linear entropy constant and hence $O(N\log
N)$ mixing time where $N$ is the number of vertices of the tree.
