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

Reconstruction of Random Colourings

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

Main Content
Current View