Reconstruction of Random Colourings
Skip to main content
Open Access Publications from the University of California

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 Δ-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.

Main Content
Current View