Reconstruction for Colorings on Trees

DOI10.1137/090755783MaRDI QIDQ3094945zbMATH OpenOpenAlexFDO

Authors Nayantara Bhatnagar, Eric Vigoda, Dror Weitz, Juan Vera

Publication date 27 October 2011

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0711.3664

zbMATH Keywords

extremality of Gibbs measurerandom coloringsreconstruction

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: 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 $kleDelta+1$. For $kgeqDelta+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/lnDelta$, it is straightforward to show that reconstruction is possible and hence the measure is not extremal. We prove that for $C>1$ and $k=CDelta/lnDelta$, 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(NlogN)$ mixing time where $N$ is the number of vertices of the tree.

Recommendations

• Recoloring graphs via tree decompositions
• scientific article; zbMATH DE number 20509
• An extended formulation of the convex recoloring problem on a tree
• scientific article; zbMATH DE number 4035877
• Nonrepetitive colorings of trees
• THE COLORING OF THE TREE OF COLORINGS
• Building graphs from colored trees
• A note on trees colouring
• Improved approximation algorithm for convex recoloring of trees
• Approximation and Online Algorithms

Cited in

(12)

• Necessary and sufficient conditions for consistent root reconstruction in Markov models on trees
• Phase transition for the mixing time of the Glauber dynamics for coloring regular trees
• On generating series of coloured planar trees
• scientific article; zbMATH DE number 20509 (Why is no real title available?)
• Reconstruction/non-reconstruction thresholds for colourings of general Galton-Watson trees
• Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems
• Building graphs from colored trees
• Global alignment of molecular sequences via ancestral state reconstruction
• Local convergence of random graph colorings
• Likelihood-based root state reconstruction on a tree: sensitivity to parameters and applications
• Reconstruction of random colourings
• Gibbs measures and phase transitions on sparse random graphs

This page was built for publication: Reconstruction for Colorings on Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3094945)