Improved bounds on metastability thresholds and probabilities for generalized bootstrap percolation
HTML articles powered by AMS MathViewer
- by Kathrin Bringmann and Karl Mahlburg PDF
- Trans. Amer. Math. Soc. 364 (2012), 3829-3859 Request permission
Abstract:
We generalize and improve results of Andrews, Gravner, Holroyd, Liggett, and Romik on metastability thresholds for generalized two-dimensional bootstrap percolation models, and answer several of their open problems and conjectures. Specifically, we prove slow convergence and localization bounds for Holroyd, Liggett, and Romik’s $k$-percolation models, and in the process provide a unified and improved treatment of existing results for bootstrap, modified bootstrap, and Froböse percolation. Furthermore, we prove improved asymptotic bounds for the generating functions of partitions without $k$-gaps, which are also related to certain infinite probability processes relevant to these percolation models.
One of our key technical probability results is also of independent interest. We prove new upper and lower bounds for the probability that a sequence of independent events with monotonically increasing probabilities contains no “$k$-gap” patterns, which interpolates the general Markov chain solution that arises in the case that all of the probabilities are equal.
References
- J. Adler, D. Stauffer, and A. Aharony, Comparison of bootstrap percolation models, J. Phys. (A) 22 (1989), L297–L301.
- M. Aizenman and J. L. Lebowitz, Metastability effects in bootstrap percolation, J. Phys. A 21 (1988), no. 19, 3801–3813. MR 968311
- George E. Andrews, Partitions with short sequences and mock theta functions, Proc. Natl. Acad. Sci. USA 102 (2005), no. 13, 4666–4671. MR 2139704, DOI 10.1073/pnas.0500218102
- George E. Andrews, The theory of partitions, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1998. Reprint of the 1976 original. MR 1634067
- George Andrews, Henrik Eriksson, Fedor Petrov, and Dan Romik, Integrals, partitions and MacMahon’s theorem, J. Combin. Theory Ser. A 114 (2007), no. 3, 545–554. MR 2310749, DOI 10.1016/j.jcta.2006.06.010
- József Balogh, Béla Bollobás, and Robert Morris, Bootstrap percolation in high dimensions, Combin. Probab. Comput. 19 (2010), no. 5-6, 643–692. MR 2726074, DOI 10.1017/S0963548310000271
- József Balogh, Béla Bollobás, and Robert Morris, Bootstrap percolation in three dimensions, Ann. Probab. 37 (2009), no. 4, 1329–1380. MR 2546747, DOI 10.1214/08-AOP433
- K. Bringmann and K. Mahlburg, An extension of the Hardy-Ramanujan circle method and applications to partitions without sequences, to appear in Amer. J. of Math.
- K. Froböse, Finite-size effects in a cellular automaton for diffusion, J. Statist. Phys. 55 (1989), no. 5-6, 1285–1292. MR 1002492, DOI 10.1007/BF01041088
- Janko Gravner and Alexander E. Holroyd, Local bootstrap percolation, Electron. J. Probab. 14 (2009), no. 14, 385–399. MR 2480546, DOI 10.1214/EJP.v14-607
- Janko Gravner and Alexander E. Holroyd, Slow convergence in bootstrap percolation, Ann. Appl. Probab. 18 (2008), no. 3, 909–928. MR 2418233, DOI 10.1214/07-AAP473
- J. Gravner, A. Holroyd, and R. Morris, A sharper threshold for bootstrap percolation in two dimensions, to appear in Prob. Theory and Related Fields.
- Geoffrey Grimmett, Percolation, 2nd ed., Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 321, Springer-Verlag, Berlin, 1999. MR 1707339, DOI 10.1007/978-3-662-03981-6
- Alexander E. Holroyd, Sharp metastability threshold for two-dimensional bootstrap percolation, Probab. Theory Related Fields 125 (2003), no. 2, 195–224. MR 1961342, DOI 10.1007/s00440-002-0239-x
- Alexander E. Holroyd, The metastability threshold for modified bootstrap percolation in $d$ dimensions, Electron. J. Probab. 11 (2006), no. 17, 418–433. MR 2223042, DOI 10.1214/EJP.v11-326
- Alexander E. Holroyd, Thomas M. Liggett, and Dan Romik, Integrals, partitions, and cellular automata, Trans. Amer. Math. Soc. 356 (2004), no. 8, 3349–3368. MR 2052953, DOI 10.1090/S0002-9947-03-03417-2
- Roberto H. Schonmann, On the behavior of some cellular automata related to bootstrap percolation, Ann. Probab. 20 (1992), no. 1, 174–193. MR 1143417
- Aernout C. D. van Enter, Proof of Straley’s argument for bootstrap percolation, J. Statist. Phys. 48 (1987), no. 3-4, 943–945. MR 914911, DOI 10.1007/BF01019705
- G. N. Watson, The final problem: an account of the mock theta functions, Ramanujan: essays and surveys, Hist. Math., vol. 22, Amer. Math. Soc., Providence, RI, 2001, pp. 325–347. MR 1862757
Additional Information
- Kathrin Bringmann
- Affiliation: Mathematical Institute, University of Cologne, Weyertal 86-90, 50931 Cologne, Germany
- MR Author ID: 774752
- Email: kbringma@math.uni-koeln.de
- Karl Mahlburg
- Affiliation: Department of Mathematics, Princeton University, Princeton, New Jersey 08544
- MR Author ID: 664593
- Email: mahlburg@math.princeton.edu
- Received by editor(s): June 13, 2010
- Received by editor(s) in revised form: February 1, 2011
- Published electronically: March 1, 2012
- Additional Notes: The authors thank the Mathematisches Forschungsinstitut Oberwolfach for hosting this research through the Research in Pairs Program. The first author was partially supported by NSF grant DMS-0757907 and by the Alfried Krupp Prize for Young University Teachers of the Krupp Foundation. The second author was supported by an NSF Postdoctoral Fellowship administered by the Mathematical Sciences Research Institute through its core grant DMS-0441170.
- © Copyright 2012
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 364 (2012), 3829-3859
- MSC (2010): Primary 05A17, 11P82, 26A06, 60C05, 60K35
- DOI: https://doi.org/10.1090/S0002-9947-2012-05610-8
- MathSciNet review: 2901236