Robust reconstruction on trees is determined by the second eigenvalue.

DOI10.1214/009117904000000153zbMath1061.60105arXivmath/0406447OpenAlexW3102586875MaRDI QIDQ1889794

Svante Janson, Elchanan Mossel

Publication date: 10 December 2004

Published in: The Annals of Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0406447

zbMATH Keywords

branching numberrobust phase transitionreconstruction on trees

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Phase transitions (general) in equilibrium statistical mechanics (82B26) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Related Items (17)

Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information ⋮ On the purity of the free boundary condition Potts measure on random trees ⋮ Reconstruction of random colourings ⋮ Combinatorial statistics and the sciences ⋮ Phase transitions in theq-coloring of random hypergraphs ⋮ Non-robust phase transitions in the generalized clock model on trees ⋮ On the inference of large phylogenies with long branches: how long is too long? ⋮ Phase transition in the sample complexity of likelihood-based phylogeny inference ⋮ Community Detection and Stochastic Block Models ⋮ The critical Ising model on trees, concave recursions and nonlinear capacity ⋮ Global alignment of molecular sequences via ancestral state reconstruction ⋮ Evolutionary trees and the Ising model on the Bethe lattice: A proof of Steel's conjecture ⋮ Phase transitions in phylogeny ⋮ On the computational tractability of statistical estimation on amenable graphs ⋮ Biased landscapes for random constraint satisfaction problems ⋮ Optimization of the dynamic transition in the continuous coloring problem ⋮ Broadcasting on random recursive trees

Cites Work

• Random walks and percolation on trees
• Gibbs measures and phase transitions
• Markov random fields on an infinite tree
• Remarks on the limiting Gibbs states on a (d+1)-tree
• Information flow on trees
• A phase transition for a random cluster model on phylogenetic trees.
• On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice.
• Glauber dynamics on trees: Boundary conditions and mixing time
• Glauber dynamics on trees and hyperbolic graphs
• Robust phase transitions for Heisenberg and other models on general trees
• The Ising model and percolation on trees and tree-like graphs
• Reconstruction on trees: Beating the second eigenvalue
• Broadcasting on trees and the Ising model.
• On the extremality of the disordered state for the Ising model on the Bethe lattice
• Phase transitions in phylogeny
• Signal propagation and noisy circuits
• Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes
• On the maximum tolerable noise for reliable computation by formulas
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Robust reconstruction on trees is determined by the second eigenvalue.