Reconstruction of symmetric Potts Models

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 $q$-state Potts model when $q\ge 5$. Moreover, we determine asymptotics for the reconstruction thresholds.

References in corpus (4)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Phase Transitions in the Coloring of Random Graphs
• On the freezing of variables in random constraint satisfaction problems
• Reconstruction of Random Colourings

Cited by in corpus (5)

• Global and Local Information in Clustering Labeled Block Models
• Reconstruction Threshold for the Hardcore Model
• On the Purity of the free boundary condition Potts measure on random trees
• A symmetric entropy bound on the non-reconstruction regime of Markov chains on Galton-Watson trees
• A computational method for bounding the probability of reconstruction on trees