Reconstruction Threshold for the Hardcore Model

Reconstruction Threshold for the Hardcore Model
复制标题

硬核模型的重构阈值

DOI：
--
复制
发表时间：
2010
期刊：
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
影响因子：
--
通讯作者：
P. Tetali
P. Tetali
中科院分区：
--
文献类型：
--
作者：
Nayantara Bhatnagar;A. Sly;P. Tetali

文献摘要

被引文献

相似文献

本文考虑了核心模型在树上的重构问题。我们确定了当λ (e+o(1)) ln2k时显示非重构的k正则树上的非重构区域的新界。我们讨论了在稀疏随机图中寻找大独立集和在树上采样独立集的马尔可夫链混合时间的关系。
In this paper we consider the reconstruction problem on the tree for the hardcore model. We determine new bounds for the nonreconstruction regime on the k-regular tree showing nonreconstruction when λ (e+o(1)) ln2 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.