Scaling and inverse scaling in anisotropic bootstrap percolation. (English) Zbl 1402.37023
Louis, Pierre-Yves (ed.) et al., Probabilistic cellular automata. Theory, applications and future perspectives. Cham: Springer (ISBN 978-3-319-65556-7/hbk; 978-3-319-65558-1/ebook). Emergence, Complexity and Computation 27, 69-77 (2018).
Summary: In bootstrap percolation, it is known that the critical percolation threshold tends to converge slowly to zero with increasing system size, or, inversely, the critical size diverges fast when the percolation probability goes to zero. To obtain higher-order terms (i.e. sharp and sharper thresholds) for the percolation threshold in general is a hard question. In the case of two-dimensional anisotropic models, sometimes such correction terms can be obtained from inversion in a relatively simple manner.
For the entire collection see [Zbl 1401.68010].
For the entire collection see [Zbl 1401.68010].
MSC:
| 37B15 | Dynamical aspects of cellular automata |
| 60K35 | Interacting random processes; statistical mechanics type models; percolation theory |
| 82B43 | Percolation |
References:
| [1] | Harris, A.B., Schwarz, J.M.: \(\( \frac{1}{d}\)\) expansion for \(\(k\)\)-core percolation. Phys. Rev. E 72, 046123 (2005) · doi:10.1103/PhysRevE.72.046123 |
| [2] | Kozma, R.: Neuropercolation. http://www.scholarpedia.org/article/Neuropercolation |
| [3] | Kozma, R., Puljic, M., Balister, P., Bollobas, B., Freeman, W.J.: Phase transitions in the neuropercolation model of neural populations with mixed local and non-local interactions. Biol. Cybern. 92, 367-379 (2005) · Zbl 1112.92011 · doi:10.1007/s00422-005-0565-z |
| [4] | Toninelli, C.: Bootstrap and jamming percolation. In: Bouchaud, J.P., Mézard, M., Dalibard, J. (eds.) Les Houches school on Complex Systems, Session LXXXV, pp. 289-308 (2006) |
| [5] | Eckman, J.P., Moses, E., Stetter, E., Tlusty, T., Zbinden, C.: Leaders of neural cultures in a quorum percolation model. Front. Comput. Neurosci. 4, 132 (2010) |
| [6] | Adler, J., Aharony, A.: Diffusion percolation: infinite time limit and bootstrap percolation. J. Phys. A 21, 1387-1404 (1988) · doi:10.1088/0305-4470/21/6/015 |
| [7] | Aizenman, M., Lebowitz, J.L.: Metastability effects in bootstrap percolation. J. Phys. A 21, 3801-3813 (1988) · Zbl 0656.60106 · doi:10.1088/0305-4470/21/19/017 |
| [8] | Adler, J.: Bootstrap percolation. Phys. A 171, 452-470 (1991) · doi:10.1016/0378-4371(91)90295-N |
| [9] | Lenormand, R., Zarcone, C.: Growth of clusters during imbibition in a network of capillaries. In: Family, F., Landau, D.P. (eds.) Kinetics of Aggregation and Gelation, pp. 177-180. Elsevier, Amsterdam (1984) · doi:10.1016/B978-0-444-86912-8.50042-0 |
| [10] | Amini, H.: Bootstrap percolation in living neural networks. J. Stat. Phys. 141, 459-475 (2010) · Zbl 1207.82037 · doi:10.1007/s10955-010-0056-z |
| [11] | Eckman, J.P., Tlusty, T.: Remarks on bootstrap percolation in metric networks. J. Phys. A Math. Theor. 42, 205004 (2009) · Zbl 1168.82014 · doi:10.1088/1751-8113/42/20/205004 |
| [12] | Connelly, R., Rybnikov, K., Volkov, S.: Percolation of the loss of tension in an infinite triangular lattice. J. Stat. Phys. 105, 143-171 (2001) · Zbl 1051.82012 · doi:10.1023/A:1012282026916 |
| [13] | Lee, I.H., Valentiniy, A.: Noisy contagion without mutation. Rev. Econ. Stud. 67, 47-67 (2000) · Zbl 0956.91026 · doi:10.1111/1467-937X.00120 |
| [14] | Bollobas, B.: The Art of mathematics: Coffee Time in Memphis, Problems 34 and 35. Cambridge University Press, Cambridge (2006) · Zbl 1238.00002 |
| [15] | New York Times Wordplay Blog (8 July 2013). http://wordplay.blogs.nytimes.com/2013/07/08/bollobas/ |
| [16] | Winkler, P.: Mathematical Puzzles. A.K. Peters Ltd, p. 79 (2004) · Zbl 1094.00003 |
| [17] | Winkler, P.: Mathematical Mindbenders, A.K. Peters Ltd, p. 91 (2007) · Zbl 1135.00005 |
| [18] | van Enter, A.C.D.: Proof of Straley’s argument for bootstrap percolation. J. Stat. Phys. 48, 943-945 (1987) · Zbl 1084.82548 · doi:10.1007/BF01019705 |
| [19] | Schonmann, R.H.: On the behavior of some cellular automata related to bootstrap percolation. Ann. Probab. 20, 174-193 (1992) · Zbl 0742.60109 · doi:10.1214/aop/1176989923 |
| [20] | Cerf, R., Cirillo, E.: Finite size scaling in three-dimensional bootstrap percolation. Ann. Prob. 27(4), 1837-1850 (1999) · Zbl 0960.60088 · doi:10.1214/aop/1022874817 |
| [21] | Cerf, R., Manzo, F.: The threshold regime of finite volume bootstrap percolation. Stoch. Process. Appl. 101, 69-82 (2002) · Zbl 1075.82010 · doi:10.1016/S0304-4149(02)00124-2 |
| [22] | Balogh, J., Bollobas, B., Morris, R.: Bootstrap percolation in three dimensions. Ann. Probab. 37, 1329-1380 (2009) · Zbl 1187.60082 · doi:10.1214/08-AOP433 |
| [23] | Balogh, J., Bollobas, B., Duminil-Copin, H., Morris, R.: The sharp threshold for bootstrap percolation in all dimensions. Trans. Am. Math. Soc. 364, 2667-2701 (2012) · Zbl 1238.60108 · doi:10.1090/S0002-9947-2011-05552-2 |
| [24] | Holroyd, A.E.: Sharp metastability threshold for two-dimensional bootstrap percolation. Probab. Theory Relat. Fields 125, 195-224 (2003) · Zbl 1042.60065 · doi:10.1007/s00440-002-0239-x |
| [25] | Holroyd, A.E.: The metastability threshold for modified bootstrap percolation in d dimensions. Electron. J. Probab. 11(17), 418-433 (2006) · Zbl 1112.60080 · doi:10.1214/EJP.v11-326 |
| [26] | Morris, R.: The second term for bootstrap percolation in two dimensions. Manuscript in preparation. http://w3.impa.br/ rob/index.html |
| [27] | Gravner, J., Holroyd, A.E.: Slow convergence in bootstrap percolation. Ann. Appl. Probab. 18, 909-928 (2008) · Zbl 1141.60062 · doi:10.1214/07-AAP473 |
| [28] | Gravner, J., Holroyd, A.E., Morris, R.: A sharper threshold for bootstrap percolation in two dimensions. Probab. Theory Relat. Fields 153, 1-23 (2012) · Zbl 1254.60092 · doi:10.1007/s00440-010-0338-z |
| [29] | Uzzell, A.E.: An improved upper bound for bootstrap percolation in all dimensions (2012). arXiv:1204.3190 |
| [30] | Adler, J., Lev, U.: Bootstrap percolation: visualisations and applications. Braz. J. Phys. 33, 641-644 (2003) · doi:10.1590/S0103-97332003000300031 |
| [31] | de Gregorio, P., Lawlor, A., Bradley, P., Dawson, K.A.: Clarification of the bootstrap percolation paradox. Phys. Rev. Lett. 93, 025501 (2004) · Zbl 1116.82327 · doi:10.1103/PhysRevLett.93.025501 |
| [32] | Balogh, J., Bollobas, B.: Sharp thresholds in bootstrap percolation. Phys. A 326, 305-312 (2003) · Zbl 1025.60042 · doi:10.1016/S0378-4371(03)00364-9 |
| [33] | Duminil-Copin, H., Holroyd, A.E.: Finite volume bootstrap percolation with balanced threshold rules on \(\({\mathbb{Z}}^2\)\). Preprint (2012). http://www.unige.ch/duminil/ |
| [34] | Gravner, J., Griffeath, D.: First passage times for threshold growth dynamics on \(\(\mathbb{Z}^2\)\). Ann. Probab. 24, 1752-1778 (1996) · Zbl 0872.60077 · doi:10.1214/aop/1041903205 |
| [35] | Bollobás, B., Duminil-Copin, H., Morris, R., Smith, P.: The sharp threshold for the Duarte model. Ann. Probab. To appear (2016). arXiv:1603.05237 · Zbl 1454.60141 |
| [36] | van Enter, A.C.D., Fey, A.: Metastability thresholds for anisotropic bootstrap percolation in three dimensions. J. Stat. Phys. 147, 97-112 (2012) · Zbl 1243.82038 · doi:10.1007/s10955-012-0455-4 |
| [37] | Duarte, J.A.M.S.: Simulation of a cellular automaton with an oriented bootstrap rule. Phys. A 157, 1075-1079 (1989) · doi:10.1016/0378-4371(89)90033-2 |
| [38] | Adler, J., Duarte, J.A.M.S., van Enter, A.C.D.: Finite-size effects for some bootstrap percolation models. J. Stat. Phys. 60, 323-332 (1990); Addendum. J. Stat. Phys. 62, 505-506 (1991) |
| [39] | Mountford, T.S.: Critical lengths for semi-oriented bootstrap percolation. Stoch. Proc. Appl. 95, 185-205 (1995) · Zbl 0821.60092 · doi:10.1016/0304-4149(94)00061-W |
| [40] | Schonmann, R.H.: Critical points of 2-dimensional bootstrap percolation-like cellular automata. J. Stat. Phys. 58, 1239-1244 (1990) · Zbl 0712.68071 · doi:10.1007/BF01026574 |
| [41] | van Enter, A.C.D., Hulshof, W.J.T.: Finite-size effects for anisotropic bootstrap percolation: logarithmic corrections. J. Stat. Phys. 128, 1383-1389 (2007) · Zbl 1206.82049 · doi:10.1007/s10955-007-9377-y |
| [42] | Duminil-Copin, H., van Enter, A.C.D., Hulshof, W.J.T.: Higher order corrections for anisotropic bootstrap percolation. Prob. Th. Rel. Fields. arXiv:1611.03294 (2016) · Zbl 1404.60149 |
| [43] | Duminil-Copin, H., van Enter, A.C.D.: Sharp metastability threshold for an anisotropic bootstrap percolation model. Ann. Prob. 41, 1218-1242 (2013) · Zbl 1356.60166 · doi:10.1214/11-AOP722 |
| [44] | Boerma-Klooster, S.: A sharp threshold for an anisotropic bootstrap percolation model. Groningen bachelor thesis (2011) |
| [45] | Gray, L.: A mathematician looks at Wolfram’s new kind of science. Not. Am. Math. Soc. 50, 200-211 (2003) · Zbl 1136.37300 |
| [46] | Bringmann, K., Mahlburg, K.: Improved bounds on metastability thresholds and probabilities for generalized bootstrap percolation. Trans. Am. Math. Soc. 364, 3829-2859 (2012) · Zbl 1268.05020 · doi:10.1090/S0002-9947-2012-05610-8 |
| [47] | Bringmann, K., Mahlburg, K., Mellit, A.: Convolution bootstrap percolation models, Markov-type stochastic processes, and mock theta functions. Int. Math. Res. Not. 2013, 971-1013 (2013) · Zbl 1317.60127 · doi:10.1093/imrn/rns008 |
| [48] | Froböse, K.: Finite-size effects in a cellular automaton for diffusion. J. Stat. Phys. 55, 1285-1292 (1989) · doi:10.1007/BF01041088 |
| [49] | Holroyd, A.E., Liggett, T.M., Romik, D.: Integrals, partitions and cellular automata. Trans. Am. Math. Soc. 356, 3349-3368 (2004) · Zbl 1095.60003 · doi:10.1090/S0002-9947-03-03417-2 |
| [50] | Bollobás, B., Smith, P., Uzzell, A.: Monotone cellular automata in a random environment. Comb. Probab. Comput. 24(4), 687-722 (2015) · Zbl 1371.60170 · doi:10.1017/S0963548315000012 |
| [51] | Balogh, J., Bollobas, B., Pete, G.: Bootstrap percolation on infinite trees and non-amenable groups. Comb. Probab. Comput. 15, 715-730 (2006) · Zbl 1102.60086 · doi:10.1017/S0963548306007619 |
| [52] | Bollobás, B., Gunderson, K., Holmgren, C., Janson, S., Przykucki, M.: Bootstrap percolation on Galton-Watson trees El. J. Prob. 19, 13 (2014) · Zbl 1290.05058 |
| [53] | Chalupa, J., Leath, P.L., Reich, G.R.: Bootstrap percolation on a Bethe lattice. J. Phys. C 12, L31 (1979) · doi:10.1088/0022-3719/12/1/008 |
| [54] | Schwarz, J.M., Liu, A.J., Chayes, L.Q.: The onset of jamming as the sudden emergence of an infinite k-core cluster. Europhys. Lett. 73, 560-566 (2006) · doi:10.1209/epl/i2005-10421-7 |
| [55] | Balogh, J., Pittel, B.G.: Bootstrap percolation on the random regular graph. Random Struct. Algorithms 30, 257-286 (2007) · Zbl 1106.60076 · doi:10.1002/rsa.20158 |
| [56] | Pittel, B., Spencer, J., Wormald, N.: Sudden emergence of a giant k-core. J. Comb. Theory B 67, 111-151 (1996) · Zbl 0860.05065 · doi:10.1006/jctb.1996.0036 |
| [57] | Sausset, F., Toninelli, C., Biroli, G., Tarjus, G.: Bootstrap percolation and kinetically constrained models on hyperbolic lattices. J. Stat. Phys. 138, 411-430 (2010) · Zbl 1187.82029 · doi:10.1007/s10955-009-9903-1 |
| [58] | Bouchaud, J.P., Cipelletti, L., van Saarloos, W.: In: Berthier, L. (ed.) Dynamic Heterogeneities in glasses, Colloids, and Granular Media. Oxford University Press, Oxford (2011) |
| [59] | Jeng, M., Schwarz, J.M.: On the study of jamming percolation. J. Stat. Phys. 131, 575-595 (2008) · Zbl 1151.82358 · doi:10.1007/s10955-008-9514-2 |
| [60] | Toninelli, C., Biroli, G.: A new class of cellular automata with a discontinuous glass transition. J. Stat. Phys. 130, 83-112 (2008) · Zbl 1134.82018 · doi:10.1007/s10955-007-9420-z |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
