Reconstruction for colorings on trees

N. Bhatnagar, J.C. Vera, E. Vigoda, D. Weitz

Research output: Contribution to journalArticleScientificpeer-review

Abstract

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 Δ+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 Δ/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.
Original languageEnglish
Pages (from-to)809-826
JournalSIAM Journal on Discrete Mathematics
Volume25
Issue number2
Publication statusPublished - 2011

Fingerprint

Colouring
Leaves
Gibbs Measure
Roots
K-tree
Mixing Time
Local Algorithms
Free Boundary
Random Graphs
Branching
Markov chain
Uniqueness
Update
Entropy
Entire
Decay
Imply
Range of data

Cite this

Bhatnagar, N., Vera, J. C., Vigoda, E., & Weitz, D. (2011). Reconstruction for colorings on trees. SIAM Journal on Discrete Mathematics, 25(2), 809-826.
Bhatnagar, N. ; Vera, J.C. ; Vigoda, E. ; Weitz, D. / Reconstruction for colorings on trees. In: SIAM Journal on Discrete Mathematics. 2011 ; Vol. 25, No. 2. pp. 809-826.
@article{983716a26dfb4ad78c6c550277c784bb,
title = "Reconstruction for colorings on trees",
abstract = "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.",
author = "N. Bhatnagar and J.C. Vera and E. Vigoda and D. Weitz",
year = "2011",
language = "English",
volume = "25",
pages = "809--826",
journal = "SIAM Journal on Discrete Mathematics",
issn = "0895-4801",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "2",

}

Bhatnagar, N, Vera, JC, Vigoda, E & Weitz, D 2011, 'Reconstruction for colorings on trees', 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.

In: SIAM Journal on Discrete Mathematics, Vol. 25, No. 2, 2011, p. 809-826.

Research output: Contribution to journalArticleScientificpeer-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 -

Bhatnagar N, Vera JC, Vigoda E, Weitz D. Reconstruction for colorings on trees. SIAM Journal on Discrete Mathematics. 2011;25(2):809-826.