Reconstruction threshold for the hardcore model

DOI10.1007/978-3-642-15369-3_33MaRDI QIDQ3588426zbMATH OpenOpenAlexFDO

Authors Nayantara Bhatnagar, Allan Sly, Prasad Tetali

Publication date 10 September 2010

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.3531

Mathematics Subject Classification ID

Trees (05C05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

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 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.

Recommendations

• scientific article; zbMATH DE number 2046068
• Phase transition for Glauber dynamics for independent sets on regular trees
• Decay of correlations for the hardcore model on the d-regular random graph
• Phase transition for Glauber dynamics for independent sets on regular trees
• Reconstruction for the Potts model

Cited in

(8)

• Necessary and sufficient conditions for consistent root reconstruction in Markov models on trees
• The asymptotics of the clustering transition for random constraint satisfaction problems
• Decay of correlations for the hardcore model on the d-regular random graph
• A second threshold for the hard‐core model on a Bethe lattice
• Phase transition of the reconstructability of a general model with different in-community and out-community mutations on an infinite tree
• Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems
• Sparse reconstruction in spin systems. I: iid spins
• Reconstruction of random colourings

This page was built for publication: Reconstruction threshold for the hardcore model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3588426)