Reconstruction for Colorings on Trees

Details Reconstruction for Colorings on Trees Reconstruction for Colorings on Trees

2007-11-23

arxiv.org/abs/0711.3664v3

SIAM J. on Discrete Math, 25(2):809-826, 2011

Mathematics

Probability

Suggestions by journal referees were incorporated

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Reconstruction for Colorings on Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Reconstruction for Colorings on Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reconstruction for Colorings on Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-363009