Bootstrap percolation on the hypercube

• 成果类型: Article
• 署名作者: Balogh, J; Bollobás, B
• 署名单位: University System of Ohio; Ohio State University; University of Memphis; University of Cambridge
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-005-0451-6
• 发表日期: 2006
• 页码: 624-648
• 关键词: cellular automata; sharp thresholds

摘要

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 p(n) >= c(1)/n(2) 2- 2 root n the probability of spanning tends to 1 as n --> infinity, while for p(n) <= c(2)/n(2) 2 (-2)root n the probability tends to 0. Furthermore, we shall show that for each n the transition has a sharp threshold function.