Bootstrap percolation on the Hamming torus. (English) Zbl 1308.60109

Gravner, Janko; Hoffman, Christopher; Pfeiffer, James; Sivakoff, David

Ann. Appl. Probab. 25, No. 1, 287-323 (2015).

Summary: The Hamming torus of dimension \(d\) is the graph with vertices \(\{1,\dots,n\}^{d}\) and an edge between any two vertices that differ in a single coordinate. Bootstrap percolation with threshold \(\theta\) starts with a random set of open vertices, to which every vertex belongs independently with probability \(p\), and at each time step the open set grows by adjoining every vertex with at least \(\theta\) open neighbors. We assume that \(n\) is large and that \(p\) scales as \(n^{-\alpha}\) for some \(\alpha >1\), and study the probability that an \(i\)-dimensional subgraph ever becomes open. For large \(\theta\), we prove that the critical exponent \(\alpha\) is about \(1+d/\theta\) for \(i=1\), and about \(1+2/\theta+\Theta (\theta^{-3/2})\) for \(i\geq 2\). Our small \(\theta\) results are mostly limited to \(d=3\), where we identify the critical \(\alpha\) in many cases and, when \(\theta =3\), compute exactly the critical probability that the entire graph is eventually open.

MSC:

60K35

Interacting random processes; statistical mechanics type models; percolation theory

Keywords:

bootstrap percolation; critical exponent; Hamming torus; Poisson convergence

References:

[1]	Adler, J. and Lev, U. (2003). Bootstrap percolation: Visualizations and applications. Braz. J. Phys. 33 641-644.
[2]	Aizenman, M. and Lebowitz, J. L. (1988). Metastability effects in bootstrap percolation. J. Phys. A 21 3801-3813. · Zbl 0656.60106 · doi:10.1088/0305-4470/21/19/017
[3]	Balogh, J. and Bollobás, B. (2006). Bootstrap percolation on the hypercube. Probab. Theory Related Fields 134 624-648. · Zbl 1087.60068 · doi:10.1007/s00440-005-0451-6
[4]	Balogh, J., Bollobás, B. and Morris, R. (2009). Bootstrap percolation in three dimensions. Ann. Probab. 37 1329-1380. · Zbl 1187.60082 · doi:10.1214/08-AOP433
[5]	Balogh, J., Bollobás, B. and Morris, R. (2009). Majority bootstrap percolation on the hypercube. Combin. Probab. Comput. 18 17-51. · Zbl 1198.60041 · doi:10.1017/S0963548308009322
[6]	Balogh, J., Bollobás, B., Duminil-Copin, H. and Morris, R. (2012). The sharp threshold for bootstrap percolation in all dimensions. Trans. Amer. Math. Soc. 364 2667-2701. · Zbl 1238.60108 · doi:10.1090/S0002-9947-2011-05552-2
[7]	Barbour, A. D., Holst, L. and Janson, S. (1992). Poisson Approximation. Oxford Studies in Probability 2 . Oxford Univ. Press, New York. · Zbl 0746.60002
[8]	Borgs, C., Chayes, J. T., van der Hofstad, R., Slade, G. and Spencer, J. (2005). Random subgraphs of finite graphs. II. The lace expansion and the triangle condition. Ann. Probab. 33 1886-1944. · Zbl 1079.05087 · doi:10.1214/009117905000000260
[9]	Cerf, R. and Cirillo, E. N. M. (1999). Finite size scaling in three-dimensional bootstrap percolation. Ann. Probab. 27 1837-1850. · Zbl 0960.60088 · doi:10.1214/aop/1022677550
[10]	Cerf, R. and Manzo, F. (2002). The threshold regime of finite volume bootstrap percolation. Stochastic Process. Appl. 101 69-82. · Zbl 1075.82010 · doi:10.1016/S0304-4149(02)00124-2
[11]	Chalupa, J., Leath, P. L. and Reich, G. R. (1979). Bootstrap percolation on a Bethe lattice. J. Phys. C 12 L31-L35.
[12]	Friedgut, E. and Kalai, G. (1996). Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc. 124 2993-3002. · Zbl 0864.05078 · doi:10.1090/S0002-9939-96-03732-X
[13]	Gravner, J., Holroyd, A. E. and Morris, R. (2012). A sharper threshold for bootstrap percolation in two dimensions. Probab. Theory Related Fields 153 1-23. · Zbl 1254.60092 · doi:10.1007/s00440-010-0338-z
[14]	Holroyd, A. E. (2003). Sharp metastability threshold for two-dimensional bootstrap percolation. Probab. Theory Related Fields 125 195-224. · Zbl 1042.60065 · doi:10.1007/s00440-002-0239-x
[15]	Holroyd, A. E. (2007). Astonishing cellular automata. Bulletin du Centre de Recherches Mathematiques 13 10-13.
[16]	Holroyd, A. E., Liggett, T. M. and Romik, D. (2004). Integrals, partitions, and cellular automata. Trans. Amer. Math. Soc. 356 3349-3368 (electronic). · Zbl 1095.60003 · doi:10.1090/S0002-9947-03-03417-2
[17]	Janson, S., Łuczak, T., Turova, T. and Vallier, T. (2012). Bootstrap percolation on the random graph \(G_{n,p}\). Ann. Appl. Probab. 22 1989-2047. · Zbl 1254.05182 · doi:10.1214/11-AAP822
[18]	Schonmann, R. H. (1992). On the behavior of some cellular automata related to bootstrap percolation. Ann. Probab. 20 174-193. · Zbl 0742.60109 · doi:10.1214/aop/1176989923
[19]	Sivakoff, D. (2014). Site percolation on the \(d\)-dimensional Hamming torus. Combin. Probab. Comput. 23 290-315. · Zbl 1290.05133 · doi:10.1017/S096354831300059X
[20]	Slivken, E. Bootstrap percolation on the hamming torus with threshold 2. Unpublished manuscript.
[21]	van Enter, A. C. D. (1987). Proof of Straley’s argument for bootstrap percolation. J. Stat. Phys. 48 943-945. · Zbl 1084.82548 · doi:10.1007/BF01019705
[22]	van der Hofstad, R. and Luczak, M. J. (2010). Random subgraphs of the 2D Hamming graph: The supercritical phase. Probab. Theory Related Fields 147 1-41. · Zbl 1188.05141 · doi:10.1007/s00440-009-0200-3