Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Reconstruction Thres ...
Conference paper

Reconstruction Thresholds on Regular Trees

James B. Martin (1)
(1) Laboratoire d'informatique Algorithmique : Fondements et Applications
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2002
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03)
Proceedings
DOI
10.46298/dmtcs.3325
License
https://about.hal.science/hal-authorisation-v1
Indicators
803
Views
674
Downloads

Reconstruction Thresholds on Regular Trees

James B. Martin (1)
(1) Laboratoire d'informatique Algorithmique : Fondements et Applications
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$.
Keywords
  • [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]
  • broadcasting on a tree
  • reconstruction
  • hard-core model
  • Gibbs measure
  • extremality
Cited by

Source: OpenCitations

  • Robust reconstruction on trees is determined by the second eigenvalue

    arXiv (Cornell University)

    Authors : Svante Janson, Elchanan Mossel

    Journal reference : Volume 32, 2004, pp.

    DOI : 10.1214/009117904000000153

  • A symmetric entropy bound on the non-reconstruction regime of Markov chains on Galton-Watson trees

    Electronic Communications in Probability

    Authors : Christof Külske, Marco Formentin ORCID

    Journal reference : Volume 14, 2009, pp.

    DOI : 10.1214/ecp.v14-1516

  • Gibbs measures for hardcore-solid-on-solid models on Cayley trees

    Journal of Statistical Mechanics Theory and Experiment

    Authors : Benedikt Jahnel ORCID, Utkir Rozikov ORCID

    Journal reference : Volume 2024, 2024, pp. 073202

    DOI : 10.1088/1742-5468/ad5433

  • Gibbs measures of Potts model on Cayley trees: A survey and applications

    arXiv (Cornell University)

    Authors : U. A. Rozikov ORCID

    Journal reference : Volume 33, 2021, pp.

    DOI : 10.1142/s0129055x21300077

  • Reconstruction for Colorings on Trees

    arXiv (Cornell University)

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

    Journal reference : Volume 25, 2011, pp. 809-826

    DOI : 10.1137/090755783

  • Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method

    arXiv (Cornell University)

    Authors : David Gamarnik, Tomasz Nowicki ORCID, Grzegorz Swirszcz

    Journal reference : Volume 28, 2005, pp. 76-106

    DOI : 10.1002/rsa.20072

  • Maximum Weight Independent Sets and Matchings in Sparse Random Graphs

    Lecture notes in computer science

    Authors : David Gamarnik, Tomasz Nowicki ORCID, Grzegorz Swirszcz

    Journal reference : Volume , 2004, pp. 357-368

    DOI : 10.1007/978-3-540-27821-4_32

  • Reconstruction Threshold for the Hardcore Model

    Lecture notes in computer science

    Authors : Nayantara Bhatnagar, Allan Sly ORCID, Prasad Tetali

    Journal reference : Volume , 2010, pp. 434-447

    DOI : 10.1007/978-3-642-15369-3_33

  • New disordered phases of the (s,1/2) -mixed spin Ising model for arbitrary spin s

    Chaos Solitons & Fractals

    Authors : Hasan Akın ORCID

    Journal reference : Volume 189, 2024, pp. 115733

    DOI : 10.1016/j.chaos.2024.115733

  • Decay of correlations for the hardcore model on the $d$-regular random graph

    Electronic Journal of Probability

    Authors : Nayantara Bhatnagar, Allan Sly ORCID, Prasad Tetali

    Journal reference : Volume 21, 2016, pp.

    DOI : 10.1214/16-ejp3552

  • Extremality of some Gibbs measures for the Blume–Capel HC-model on a Cayley tree

    Vestnik Udmurtskogo Universiteta Matematika Mekhanika Komp yuternye Nauki

    Authors : Khatamov N.M.

    Journal reference : Volume 32, 2022, pp. 256-277

    DOI : 10.35634/vm220207

  • Fast mixing for independent sets, colorings, and other models on trees

    Random Structures and Algorithms

    Authors : Fabio Martinelli ORCID, Alistair Sinclair ORCID, Dror Weitz

    Journal reference : Volume 31, 2006, pp. 134-172

    DOI : 10.1002/rsa.20132

  • Extremality of Translation-Invariant Phases for a Three-State SOS-Model on the Binary Tree

    Journal of Statistical Physics

    Authors : C. Kuelske ORCID, U. A. Rozikov ORCID

    Journal reference : Volume 160, 2015, pp. 659-680

    DOI : 10.1007/s10955-015-1279-9
Preview
Loading PDF preview...