Reconstruction for the Potts model
From MaRDI portal
Abstract: The reconstruction problem on the tree has been studied in numerous contexts including statistical physics, information theory and computational biology. However, rigorous reconstruction thresholds have only been established in a small number of models. We prove the first exact reconstruction threshold in a non-binary model establishing the Kesten-Stigum bound for the 3-state Potts model on regular trees of large degree. We further establish that the Kesten-Stigum bound is not tight for the -state Potts model when . Moreover, we determine asymptotics for the reconstruction thresholds.
An infinite rooted tree is considered where every vertex has \(d\) children. The spin \(\sigma_{\rho}\) on the root \(\rho\) is chosen from \({\mathcal C}=\{1,\ldots,q\}\) according to some initial distribution and then propagates along the edges of the tree according to a transition matrix \(M\) with \(M_{i,j}=M_{i,k}\) for \(j,k\in {\mathcal C}\setminus \{i\}\) and \(M_{i,i}=1-p\). The associated reconstruction problem naturally arises in computational biology, information theory and statistical physics. The most general result on the reconstruction problem is the Kesten-Stigum bound which states that a reconstruction problem is solvable when \(\lambda^2d>1\), where \(\lambda=1-pq/(q-1)\). The author proves the first exact reconstruction threshold in a nonbinary model establishing the Kesten-Stigum bound for the 3-state Potts model on regular trees of large degree \(d\). He further establishes that the Kesten-Stigum bound is not tight for the \(q\)-state Potts model when \(q\geq 5\). In this case, he gives the precise asymptotics of the threshold for fixed \(q\) as \(d\) goes to infinity.
Recommendations
- Reconstruction for the Potts model
- scientific article; zbMATH DE number 50597
- scientific article; zbMATH DE number 29361
- Reconstruction on trees and spin glass transition
- The Potts model on the Morita lattice
- The Potts and random-cluster models
- Potts models on Feynman diagrams
- Potts models on hierarchical lattices and renormalization group dynamics
- scientific article; zbMATH DE number 3851104
Cites work
- A computational method for bounding the probability of reconstruction on trees
- Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes
- Broadcasting on trees and the Ising model.
- Convergence of stochastic processes
- Fast mixing for independent sets, colorings, and other models on trees
- Gibbs rapidly samples colorings of \(G(n, d/n)\)
- Gibbs states and the set of solutions of random constraint satisfaction problems
- Glauber dynamics on trees and hyperbolic graphs
- scientific article; zbMATH DE number 2151257 (Why is no real title available?)
- Information flow on trees
- On the extremality of the disordered state for the Ising model on the Bethe lattice
- On the freezing of variables in random constraint satisfaction problems
- On the purity of the free boundary condition Potts measure on random trees
- On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice.
- Optimal phylogenetic reconstruction
- Phase transitions in phylogeny
- Randomly coloring constant degree graphs
- Reconstruction and clustering in random constraint satisfaction problems
- Reconstruction of random colourings
- Reconstruction on trees and spin glass transition
- Reconstruction on trees: Beating the second eigenvalue
Cited in
(43)- Necessary and sufficient conditions for consistent root reconstruction in Markov models on trees
- Spectral measures of factor of i.i.d. processes on vertex-transitive graphs
- Non-robust phase transitions in the generalized clock model on trees
- The tightness of the Kesten-Stigum reconstruction bound of symmetric model with multiple mutations
- Charting the replica symmetric phase
- Broadcasting on trees and the Ising model.
- Robust reconstruction on trees is determined by the second eigenvalue.
- Uniqueness for the 3-state antiferromagnetic Potts model on the tree
- Sufficient condition for root reconstruction by parsimony on binary trees with general weights
- On the computational tractability of statistical estimation on amenable graphs
- Broadcasting on random recursive trees
- Reconstructibility of a general DNA evolution model
- Information reconstruction on an infinite tree for a \(4\times 4\)-state asymmetric model with community effects
- Large degree asymptotics and the reconstruction threshold of the asymmetric binary channels
- A computational method for bounding the probability of reconstruction on trees
- Reconstruction threshold for the hardcore model
- Reconstruction and estimation in the planted partition model
- Fuzzy transformations and extremality of Gibbs measures for the Potts model on a Cayley tree
- The replica symmetric phase of random constraint satisfaction problems
- Phase transition of the reconstructability of a general model with different in-community and out-community mutations on an infinite tree
- Reconstruction of pairwise interactions using energy-based models*
- Gibbs measures of Potts model on Cayley trees: a survey and applications
- Phase transition for the Ising model with mixed spins on a Cayley tree
- Extremality of translation-invariant phases for a three-state SOS-model on the binary tree
- Reconstruction for the Potts model
- Reconstruction/non-reconstruction thresholds for colourings of general Galton-Watson trees
- Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems
- The Swendsen–Wang dynamics on trees
- Combinatorial statistics and the sciences
- Existence of gradient Gibbs measures on regular trees which are not translation invariant
- Statistical reconstruction of the GFF and KT transition
- Reconstruction on trees: exponential moment bounds for linear estimators
- The extremality of disordered phases for the mixed spin-(1,1/2) Ising model on a Cayley tree of arbitrary order
- Broadcasting in random recursive DAGs
- Exact phase transitions for stochastic block models and reconstruction on trees
- Analysis of Gibbs measures and stability of dynamical system linked to (1, 1/2)-mixed Ising model on (m, k)-ary trees
- Time and knowability in evolutionary processes
- Hard-core and soft-core Widom-rowlinson models on Cayley trees
- Likelihood-based root state reconstruction on a tree: sensitivity to parameters and applications
- Three-state p-SOS models on binary Cayley trees
- On the purity of the free boundary condition Potts measure on random trees
- Reconstruction of random colourings
- Reconstruction on trees and spin glass transition
This page was built for publication: Reconstruction for the Potts model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q717882)
