Communications in Mathematical Physics Reconstruction of Random Colourings
Communications in Mathematical Physics Reconstruction of Random Colourings
复制标题
数学物理通讯随机着色的重建
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
A. Sly
中科院分区：
文献类型：
--
作者：
A. Sly
重建问题已经在许多背景下研究，包括生物学，信息论和统计物理学。本文研究了大k时二元树上随机k-着色的重建问题。Bhatnagar等人[2]证明了当k ≤ 1 2k log k−o（k log k）时的非重建。我们收紧了这个结果，当k ≤ k[log k+log log k+1−log 2−o（1）]时，证明了非重构，这非常接近于建立重构的最佳已知界，即k ≥ k[log k+log log k+1+o（1）]。
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 ∆ ≤ 1 2k log k−o(k log k). We tighten this result and show nonreconstruction 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)].