Reconstruction problems have been studied in a number of contexts including biology, information theory and statistical physics. We consider the reconstruction problem for random k-colourings on the Δ-ary tree for large k. Bhatnagar et al.  showed non-reconstruction when log k - o. We tighten this result and show non-reconstruction when, which is very close to the best known bound establishing reconstruction which is δ ≥ k[log k+log log k+1+o(1)].
All Science Journal Classification (ASJC) codes
- Statistical and Nonlinear Physics
- Mathematical Physics