James B. Martin - Reconstruction Thresholds on Regular Trees

dmtcs:3325 - Discrete Mathematics & Theoretical Computer Science, January 1, 2003, DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03) - https://doi.org/10.46298/dmtcs.3325
Reconstruction Thresholds on Regular TreesArticle

Authors: James B. Martin 1

  • 1 Laboratoire d'informatique Algorithmique : Fondements et Applications

We consider themodel of broadcasting on a tree, with binary state space, on theinfinite rooted tree Tk in which each node has k children. The root of the tree takesa random value 0 or 1, and then each node passes a value independently to each of its children according to a 2x2 transition matrix P. We say that reconstruction is possible if the values at the dth level of the tree contain non-vanishing information about the value at the root as d. Extending a method of Brightwell and Winkler, we obtain new conditions under which reconstruction is impossible, both in the general case and in the special case p11=0. The latter case is closely related to the hard-core model from statistical physics; a corollary of our results is that, for the hard-core model on the (k+1)-regular tree with activity λ=1, the unique simple invariant Gibbs measure is extremal in the set of Gibbs measures, for any k2.


Volume: DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03)
Section: Proceedings
Published on: January 1, 2003
Imported on: May 10, 2017
Keywords: extremality,broadcasting on a tree,reconstruction,hard-core model,Gibbs measure,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

9 Documents citing this article

Consultation statistics

This page has been seen 377 times.
This article's PDF has been downloaded 273 times.