episciences.org_3325_1675067912
1675067912
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
01
01
2003
DMTCS Proceedings vol. AC,...
Proceedings
Reconstruction Thresholds on Regular Trees
James B.
Martin
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 nonvanishing 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 hardcore model from statistical physics; a corollary of our results is that, for the hardcore 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$.
01
01
2003
3325
https://hal.science/hal01183920v1
10.46298/dmtcs.3325
https://dmtcs.episciences.org/3325

https://dmtcs.episciences.org/3325/pdf

https://dmtcs.episciences.org/3325/pdf