RECONSTRUCTION FOR COLORINGS ON TREES

Consider k-colorings of the complete tree of depth l and branching factor.. If we fix the coloring of the leaves, for what range of k is the root uniformly distributed over all k colors (in the limit l -> infinity)? 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 <= Delta + 1. For k >= 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 typical coloring of the leaves? When the leaves have a nonvanishing influence on the root in expectation, over random colorings of the leaves, reconstruction is said to hold. Nonreconstruction 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, nonreconstruction holds; i.e., the Gibbs measure is extremal. We prove a strong form of extremality: 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. Extremality on trees and random graphs has received considerable attention recently since it may have connections to the efficiency of local algorithms.