Reconstruction Threshold for the Hardcore Model

Details Reconstruction Threshold for the Hardcore Model Reconstruction Threshold for the Hardcore Model

2010-04-20

arxiv.org/abs/1004.3531v1

Mathematics

Probability

14 pages, 2 figures

Scientific paper

In this paper we consider the reconstruction problem on the tree for the hardcore model. We determine new bounds for the non-reconstruction regime on the k-regular tree showing non-reconstruction when lambda < (ln 2-o(1))ln^2(k)/(2 lnln(k)) improving the previous best bound of lambda < e-1. This is almost tight as reconstruction is known to hold when lambda> (e+o(1))ln^2(k). We discuss the relationship for finding large independent sets in sparse random graphs and to the mixing time of Markov chains for sampling independent sets on trees.

Affiliated with

Also associated with

No associations

Rating

Reconstruction Threshold for the Hardcore Model 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 Threshold for the Hardcore Model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reconstruction Threshold for the Hardcore Model will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-474901