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

UC Berkeley

UC Berkeley Previously Published Works bannerUC Berkeley

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's open access policies. Let us know how this access is important for you.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View