### Abstract

*-colorings of the complete tree of depth*

**k****ℓ**and branching factor

*. If we fix the coloring of the leaves, for what range of*

**Δ***is the root uniformly distributed over all*

**k***colors (in the limit*

**k****ℓ→∞**)? 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 ≤ Δ****+1.**For

*≥*

**k***, 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*

**Δ+2***k*

**<**, it is straightforward to show that reconstruction is possible (and hence the measure is not extremal). We prove that for

*Δ*/ln*Δ***and**

*C*>1**, 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**

*k*=*C Δ*/ln*Δ***O (**mixing time where

*N*log*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.*

**N**Original language | English |
---|---|

Pages (from-to) | 809-826 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 25 |

Issue number | 2 |

Publication status | Published - 2011 |

### Fingerprint

### Cite this

*SIAM Journal on Discrete Mathematics*,

*25*(2), 809-826.

}

*SIAM Journal on Discrete Mathematics*, vol. 25, no. 2, pp. 809-826.

**Reconstruction for colorings on trees.** / Bhatnagar, N.; Vera, J.C.; Vigoda, E.; Weitz, D.

Research output: Contribution to journal › Article › Scientific › peer-review

TY - JOUR

T1 - Reconstruction for colorings on trees

AU - Bhatnagar, N.

AU - Vera, J.C.

AU - Vigoda, E.

AU - Weitz, D.

PY - 2011

Y1 - 2011

N2 - Consider k-colorings of the complete tree of depth ℓ 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 ℓ→∞)? 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 ≤ Δ+1. For k ≥ Δ+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 < Δ/ln Δ, 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 Δ/ln Δ, 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.

AB - Consider k-colorings of the complete tree of depth ℓ 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 ℓ→∞)? 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 ≤ Δ+1. For k ≥ Δ+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 < Δ/ln Δ, 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 Δ/ln Δ, 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.

M3 - Article

VL - 25

SP - 809

EP - 826

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 2

ER -