UC Berkeley

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. [2] showed non-reconstruction when $${\Delta \leq \frac12 k\log k - o(k\log k)}$$ . We tighten this result and show non-reconstruction when $${\Delta \leq 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 \geq k[\log k + \log \log k + 1+o(1)]}$$ .