Bootstrap Percolation in High Dimensions

Combinatorics Probability and Computing - Tập 19 Số 5-6 - Trang 643-692 - 2010
József Balogh1, Béla Bollobás2, Robert Morris3
1Department of mathematics, university of illinois, 1409 w. green street, urbana, il 61801 and department of mathematics, university of california, san diego, la jolla, ca 92093 (e-mail: [email protected] ...#TAB#
2Trinity college, cambridge cb2 1tq, england and department of mathematical sciences, the university of memphis, memphis, tn 38152, usa (e-mail: [email protected])#TAB#
3Impa, estrada dona castorina 110, jardim botânico, rio de janeiro, rj, brasil (e-mail: [email protected])#TAB#

Tóm tắt

Inr-neighbour bootstrap percolation on a graphG, a set of initially infected verticesA⊂V(G) is chosen independently at random, with densityp, and new vertices are subsequently infected if they have at leastrinfected neighbours. The setAis said to percolate if eventually all vertices are infected. Our aim is to understand this process on the grid, [n]d, for arbitrary functionsn=n(t),d=d(t) andr=r(t), ast→ ∞. The main question is to determine the critical probabilitypc([n]d,r) at which percolation becomes likely, and to give bounds on the size of the critical window. In this paper we study this problem whenr= 2, for all functionsnanddsatisfyingd≫ logn.The bootstrap process has been extensively studied on [n]dwhendis a fixed constant and 2 ⩽r⩽d, and in these casespc([n]d,r) has recently been determined up to a factor of 1 +o(1) asn→ ∞. At the other end of the scale, Balogh and Bollobás determinedpc([2]d, 2) up to a constant factor, and Balogh, Bollobás and Morris determinedpc([n]d,d) asymptotically ifd≥ (log logn)2+ϵ, and gave much sharper bounds for the hypercube.Here we prove the following result. Let λ be the smallest positive root of the equationso λ ≈ 1.166. Thenifdis sufficiently large, and moreoverasd→ ∞, for every functionn=n(d) withd≫ logn.

Từ khóa


Tài liệu tham khảo

10.1002/rsa.20158

10.1017/S0963548308009322

10.1590/S0103-97332003000300031

[23] Gravner J. , Holroyd A. and Morris R. A sharper threshold for bootstrap percolation in two dimensions. Submitted.

10.1007/s00440-005-0451-6

10.1007/BF02579276

10.1214/aop/1022874817

10.1214/08-AOP433

10.1017/CBO9780511814068

10.2307/3213860

10.1088/0305-4470/21/19/017

10.1017/S0963548306007619

10.1016/0898-1221(81)90137-1

[8] Balogh J. , Bollobás B. and Morris R. Bootstrap percolation in high dimensions. Manuscript: arXiv:0907.3097.

10.1007/s00493-006-0022-1

10.1016/S0304-4149(02)00124-2

10.1088/0022-3719/12/1/008

Erdős, 1963, On a limit theorem in combinatorial analysis., Publ. Math. Debrecen, 10, 10, 10.5486/PMD.1963.10.1-4.02

10.1007/s10955-008-9583-2

10.1007/s002200200658

10.1002/rsa.20074

10.1017/S0963548306007498

10.1007/s00440-002-0239-x

10.1214/EJP.v14-603

10.1090/trans2/198/13

10.1016/S0378-4371(99)00511-7

[18] Duminil-Copin H. and Holroyd A. Sharp metastability for threshold growth models. In preparation.

[31] Pete G. (1998) Disease processes and bootstrap percolation. Thesis for Diploma at the Bolyai Institute, József Attila University, Szeged, Hungary.

10.1016/S0195-6698(85)80023-8

10.1214/aop/1176989923

[5] Balogh J. , Bollobás B. , Duminil-Copin H. and Morris R. The sharp threshold for bootstrap percolation in all dimensions. In preparation.

[28] Morris R. Zero-temperature Glauber dynamics on ℤ d . Probab. Theory Rel. Fields, to appear.

10.1002/rsa.3240030106

Thông tin
Thông tin xuất bản

Combinatorics Probability and Computing

Tập 19 Số 5-6

643-692

Thông tin tác giả