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 (3)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• 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

Cited by in corpus (2)

• Reconstruction of symmetric Potts Models
• Gibbs Measures and Phase Transitions on Sparse Random Graphs