Reconstruction of Random Colourings
Open Access Publications from the University of California

## Published Web Location

https://doi.org/10.1007/s00220-009-0783-7
Abstract

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)]}$$ .

Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.