Reconstruction of Random Colourings

Details Reconstruction of Random Colourings Reconstruction of Random Colourings

2008-02-24

arxiv.org/abs/0802.3487v2

Mathematics

Probability

Added references, updated notation

Scientific paper

10.1007/s00220-009-0783-7

Reconstruction problems have been studied in a number of contexts including biology, information theory and and statistical physics. We consider the reconstruction problem for random $k$-colourings on the $\Delta$-ary tree for large $k$. Bhatnagar et. al. showed non-reconstruction when $\Delta \leq \frac12 k\log k - o(k\log k)$ and reconstruction when $\Delta \geq 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 - \ln 2 -o(1)]$ and reconstruction when $\Delta \geq k[\log k + \log \log k + 1+o(1)]$.

Affiliated with

Also associated with

No associations

Rating

Reconstruction of Random Colourings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Reconstruction of Random Colourings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reconstruction of Random Colourings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-427061