2008/02/29 by Allan Sly · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Markov Chains and Monte Carlo Methods #math.PR #msc:60K35 #msc:82B26
paper · pdf · doi:10.1007/s00220-009-0783-7
Added references, updated notation
arxiv created 2008/05/23 · openalex publication_date 2009/03/19 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
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 Δ ≤ \frac12 klog k - o(klog k) . We tighten this result and show non-reconstruction when Δ ≤ k[log k + log log k + 1 - log 2 -o(1)] , which is very close to the best known bound establishing reconstruction which is Δ ≥ k[log k + log log k + 1+o(1)] .