{"docId":3325,"paperId":3325,"url":"https:\/\/dmtcs.episciences.org\/3325","doi":"10.46298\/dmtcs.3325","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":248,"name":"DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03)"}],"section":[{"sid":66,"title":"Proceedings","description":[]}],"repositoryName":"Hal","repositoryIdentifier":"hal-01183920","repositoryVersion":1,"repositoryLink":"https:\/\/hal.science\/hal-01183920v1","dateSubmitted":"2017-05-10 17:11:32","dateAccepted":null,"datePublished":"2003-01-01 00:00:00","titles":{"en":"Reconstruction Thresholds on Regular Trees"},"authors":["Martin, James B."],"abstracts":{"en":"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\u2192\u221e$. 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 $\u03bb =1$, the unique simple invariant Gibbs measure is extremal in the set of Gibbs measures, for any $k \u2265 2$."},"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]"]}