Reconstruction of Random Colourings

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 Delta-ary tree for large k. Bhatnagar et al. [2] showed non-reconstruction when Delta <= 1/2k log k-o(k log k). We tighten this result and shown on reconstruction when. Delta <= k[log k+log log k+1-log 2-o(1)], which is very close to the best known bound establishing reconstruction which is Delta <= k[log k+log log k+1+o(1)].