Reconstruction of Random Colourings

Abstract

Reconstruction problems have been studied in a number of contexts including biology, information theory and and statistical physics. We consider the reconstruction problem for random $k$-colourings on the $\Delta$-ary tree for large $k$. Bhatnagar et. al. showed non-reconstruction when $\Delta \le \frac{1}{2}k\log k-o(k\log k)$ and reconstruction when $\Delta \ge k\log k+o(k\log k)$. We tighten this result and show non-reconstruction when $\Delta \le k[\log k+\log \log k+1-\ln 2-o(1)]$ and reconstruction when $\Delta \ge k[\log k+\log \log k+1+o(1)]$.

Added references, updated notation

References in corpus (6)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Phase Transitions in the Coloring of Random Graphs
• Reconstruction on trees and spin glass transition
• On the freezing of variables in random constraint satisfaction problems
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Robust reconstruction on trees is determined by the second eigenvalue

Cited by in corpus (23)

• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Typology of phase transitions in Bayesian inference problems
• Biased landscapes for random Constraint Satisfaction Problems
• Phase transitions in the $q$-coloring of random hypergraphs
• Broadcasting on Random Directed Acyclic Graphs
• The large deviations of the whitening process in random constraint satisfaction problems
• Reconstruction of symmetric Potts Models
• Phase transition for the mixing time of the Glauber dynamics for coloring regular trees
• Reconstruction Threshold for the Hardcore Model
• Gibbs Measures and Phase Transitions on Sparse Random Graphs
• The Tightness of the Kesten-Stigum Reconstruction Bound of Symmetric Model with Multiple Mutations
• The asymptotics of the clustering transition for random constraint satisfaction problems
• Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
• Broadcasting on Two-Dimensional Regular Grids
• Reconstruction of colourings without freezing
• 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
• Broadcasting on Bounded Degree DAGs
• Glauber Dynamics of colorings on trees
• Broadcasting colourings on trees. A combinatorial view
• The Glauber dynamics for edge-colourings of trees
• Sufficient condition for root reconstruction by parsimony on binary trees with general weights
• A computational method for bounding the probability of reconstruction on trees