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

DOI:
https://doi.org/10.1090/S0002-9947-2012-05610-8

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 -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 -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 ``-gap'' patterns, which interpolates the general Markov chain solution that arises in the case that all of the probabilities are equal.

**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**

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

Email:
kbringma@math.uni-koeln.de

**Karl Mahlburg**

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

Email:
mahlburg@math.princeton.edu

DOI:
https://doi.org/10.1090/S0002-9947-2012-05610-8

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.