Reconstruction threshold for the hardcore model

Nayantara Bhatnagar, Allan Sly, Prasad Tetali

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

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 λ < (ln2-o(1)1n 2 k/2lnlnk improving the previous best bound of λ<e-1. This is almost tight as reconstruction is known to hold 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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings
Pages434-447
Number of pages14
DOIs
StatePublished - Nov 15 2010
Externally publishedYes
Event13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010 - Barcelona, Spain
Duration: Sep 1 2010Sep 3 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6302 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010
CountrySpain
CityBarcelona
Period9/1/109/3/10

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Reconstruction threshold for the hardcore model'. Together they form a unique fingerprint.

  • Cite this

    Bhatnagar, N., Sly, A., & Tetali, P. (2010). Reconstruction threshold for the hardcore model. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings (pp. 434-447). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6302 LNCS). https://doi.org/10.1007/978-3-642-15369-3_33