Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Improved bounds on metastability thresholds and probabilities for generalized bootstrap percolation

Authors: Kathrin Bringmann and Karl Mahlburg
Journal: Trans. Amer. Math. Soc. 364 (2012), 3829-3859
MSC (2010): Primary 05A17, 11P82, 26A06, 60C05, 60K35
Published electronically: March 1, 2012
MathSciNet review: 2901236
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. J. Adler, D. Stauffer, and A. Aharony, Comparison of bootstrap percolation models, J. Phys. (A) 22 (1989), L297-L301.
  • 2. M. Aizenman and J. Lebowitz, Metastability effects in bootstrap percolation, J. Phys. (A) 21 (1988), 3801-3813. MR 968311 (90e:82047)
  • 3. G. Andrews, Partitions with short sequences and mock theta functions, Proc. Nat. Acad. Sci. 102 (2005), 4666-4671. MR 2139704 (2006a:11131)
  • 4. G. Andrews, The theory of partitions, Cambridge University Press, Cambridge, 1998. MR 1634067 (99c:11126)
  • 5. G. Andrews, H. Eriksson, F. Petrov, and D. Romik, Integrals, partitions and MacMahon's theorem, J. Comb. Theory (A) 114 (2007), 545-554. MR 2310749 (2008j:05035)
  • 6. J. Balogh, B. Bollobás, and R. Morris, Bootstrap percolation in high dimensions, Combin. Probab. Comput. 19 (2010), no. 5-6, 643-692. MR 2726074
  • 7. J. Balogh, B. Bollobás, and R. Morris, Bootstrap percolation in three dimensions, Ann. Probab. 37 (2009), no. 4, 1329-1380. MR 2546747 (2011d:60278)
  • 8. 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.
  • 9. K. Froböse, Finite-size effects in a cellular automaton for diffusion, J. Stat. Phys. 55 (1989), 1285-1292. MR 1002492 (90c:82004)
  • 10. J. Gravner and A. Holroyd, Local bootstrap percolation, Electronic Journal of Probability 14 (2009), 385-399. MR 2480546 (2010c:60292)
  • 11. J. Gravner and A. Holroyd, Slow convergence in bootstrap percolation, The Annals of Applied Probability 18 (2008), 909-928. MR 2418233 (2009d:60325)
  • 12. J. Gravner, A. Holroyd, and R. Morris, A sharper threshold for bootstrap percolation in two dimensions, to appear in Prob. Theory and Related Fields.
  • 13. G. Grimmett, Percolation, Springer-Verlag, second edition, 1999. MR 1707339 (2001a:60114)
  • 14. A. Holroyd, Sharp metastability threshold for two-dimensional bootstrap percolation, Probability Theory and Related Fields 125 (2003), 195-224. MR 1961342 (2003k:60257)
  • 15. A. Holroyd, The metastability threshold for modified bootstrap percolation in d dimensions, Electronic Journal of Probability 11 (2006), 418-433. MR 2223042 (2007a:82023)
  • 16. A. Holroyd, T. Liggett, and D. Romik, Integrals, partitions, and cellular automata, Trans. of the AMS 356 (2004), 3349-3368. MR 2052953 (2005b:60018)
  • 17. R. Schonmann, On the behavior of some cellular automata related to bootstrap percolation, Ann. Prob. 20 (1992), 174-193. MR 1143417 (93b:60231)
  • 18. A. van Enter, Proof of Straley's argument for bootstrap percolation, J. Statist. Phys. 48 (1987), no. 3-4, 943-945. MR 914911 (88j:82024)
  • 19. G. Watson, The final problem: An account of the mock theta functions, J. London Math. Soc. 11 (1936), 55-80. MR 1862757

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05A17, 11P82, 26A06, 60C05, 60K35

Retrieve articles in all journals with MSC (2010): 05A17, 11P82, 26A06, 60C05, 60K35

Additional Information

Kathrin Bringmann
Affiliation: Mathematical Institute, University of Cologne, Weyertal 86-90, 50931 Cologne, Germany

Karl Mahlburg
Affiliation: Department of Mathematics, Princeton University, Princeton, New Jersey 08544

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.
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society