Skip to Main content Skip to Navigation
Conference papers

Reconstruction Thresholds on Regular Trees

Abstract : We consider themodel of broadcasting on a tree, with binary state space, on theinfinite rooted tree $T^k$ 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 $\mathbf{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 $p_11=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 $k ≥ 2$.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01183920
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Wednesday, August 12, 2015 - 9:06:25 AM
Last modification on : Saturday, November 20, 2021 - 3:49:33 AM
Long-term archiving on: : Friday, November 13, 2015 - 11:36:59 AM

File

dmAC0118.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

James B. Martin. Reconstruction Thresholds on Regular Trees. Discrete Random Walks, DRW'03, 2003, Paris, France. pp.191-204, ⟨10.46298/dmtcs.3325⟩. ⟨hal-01183920⟩

Share

Metrics

Record views

54

Files downloads

411