Reconstruction of random colourings

Research output: Contribution to journalArticlepeer-review

41 Scopus citations


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 log k - o. We tighten this result and show non-reconstruction when, which is very close to the best known bound establishing reconstruction which is δ ≥ k[log k+log log k+1+o(1)].

Original languageEnglish (US)
Pages (from-to)943-961
Number of pages19
JournalCommunications In Mathematical Physics
Issue number3
StatePublished - Jun 2009
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Statistical and Nonlinear Physics
  • Mathematical Physics


Dive into the research topics of 'Reconstruction of random colourings'. Together they form a unique fingerprint.

Cite this