Bootstrap percolation on the hypercube

József Balogh, Béla Bollobás

Research output: Contribution to journalArticlepeer-review

Abstract

In the bootstrap percolation on the n-dimensional hypercube, in the initial position each of the 2 n sites is occupied with probability p and empty with probability 1-p, independently of the state of the other sites. Every occupied site remains occupied for ever, while an empty site becomes occupied if at least two of its neighbours are occupied. If at the end of the process every site is occupied, we say that the (initial) position spans the hypercube. We shall show that there are constants c 1,c 2>0 such that for [InlineMediaObject not available: see fulltext.] the probability of spanning tends to 1 as n→∞, while for [InlineMediaObject not available: see fulltext.] the probability tends to 0. Furthermore, we shall show that for each n the transition has a sharp threshold function.

Original languageEnglish (US)
Pages (from-to)624-648
Number of pages25
JournalProbability Theory and Related Fields
Volume134
Issue number4
StatePublished - Apr 2006
Externally publishedYes

ASJC Scopus subject areas

  • Analysis
  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint

Dive into the research topics of 'Bootstrap percolation on the hypercube'. Together they form a unique fingerprint.

Cite this