Bootstrap percolation on the hypercube

被引:85
作者
Balogh, J [1 ]
Bollobás, B
机构
[1] Ohio State Univ, Columbus, OH 43210 USA
[2] Univ Memphis, Dept Math Sci, Memphis, TN 38152 USA
[3] Univ Cambridge Trinity Coll, Cambridge CB2 1TQ, England
关键词
D O I
10.1007/s00440-005-0451-6
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
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.
引用
收藏
页码:624 / 648
页数:25
相关论文
共 28 条
[1]  
Achlioptas D, 1999, RANDOM STRUCT ALGOR, V14, P63, DOI 10.1002/(SICI)1098-2418(1999010)14:1<63::AID-RSA3>3.0.CO
[2]  
2-7
[3]   METASTABILITY EFFECTS IN BOOTSTRAP PERCOLATION [J].
AIZENMAN, M ;
LEBOWITZ, JL .
JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1988, 21 (19) :3801-3813
[4]  
ALLOUCHE JP, 2001, CUBO MAT ED, V3, P213
[5]   CHARACTERISTIC EXPONENTS FOR 2-DIMENSIONAL BOOTSTRAP PERCOLATION [J].
ANDJEL, ED .
ANNALS OF PROBABILITY, 1993, 21 (02) :926-935
[6]  
Balogh J, 1998, RANDOM STRUCT ALGOR, V13, P409, DOI 10.1002/(SICI)1098-2418(199810/12)13:3/4<409::AID-RSA11>3.0.CO
[7]  
2-U
[8]   Sharp thresholds in Bootstrap percolation [J].
Balogh, J ;
Bollobás, B .
PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2003, 326 (3-4) :305-312
[9]  
BALOGH J, 2001, THESIS MEMPHIS
[10]  
Berlekamp ElwynR., 1982, WINNING WAYS YOUR MA, V2