Improved bounds on metastability thresholds and probabilities for generalized bootstrap percolation
Authors:
Kathrin Bringmann and Karl Mahlburg
Journal:
Trans. Amer. Math. Soc. 364 (2012), 38293859
MSC (2010):
Primary 05A17, 11P82, 26A06, 60C05, 60K35
Published electronically:
March 1, 2012
MathSciNet review:
2901236
Fulltext 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 twodimensional 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), L297L301.
 2.
M.
Aizenman and J.
L. Lebowitz, Metastability effects in bootstrap percolation,
J. Phys. A 21 (1988), no. 19, 3801–3813. MR 968311
(90e:82047)
 3.
George
E. Andrews, Partitions with short sequences and mock theta
functions, Proc. Natl. Acad. Sci. USA 102 (2005),
no. 13, 4666–4671. MR 2139704
(2006a:11131), 10.1073/pnas.0500218102
 4.
George
E. Andrews, The theory of partitions, Cambridge Mathematical
Library, Cambridge University Press, Cambridge, 1998. Reprint of the 1976
original. MR
1634067 (99c:11126)
 5.
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
(2008j:05035), 10.1016/j.jcta.2006.06.010
 6.
József
Balogh, Béla
Bollobás, and Robert
Morris, Bootstrap percolation in high dimensions, Combin.
Probab. Comput. 19 (2010), no. 56, 643–692. MR 2726074
(2012a:60266), 10.1017/S0963548310000271
 7.
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
(2011d:60278), 10.1214/08AOP433
 8.
K. Bringmann and K. Mahlburg, An extension of the HardyRamanujan circle method and applications to partitions without sequences, to appear in Amer. J. of Math.
 9.
K.
Froböse, Finitesize effects in a cellular automaton for
diffusion, J. Statist. Phys. 55 (1989), no. 56,
1285–1292. MR 1002492
(90c:82004), 10.1007/BF01041088
 10.
Janko
Gravner and Alexander
E. Holroyd, Local bootstrap percolation, Electron. J. Probab.
14 (2009), no. 14, 385–399. MR 2480546
(2010c:60292), 10.1214/EJP.v14607
 11.
Janko
Gravner and Alexander
E. Holroyd, Slow convergence in bootstrap percolation, Ann.
Appl. Probab. 18 (2008), no. 3, 909–928. MR 2418233
(2009d:60325), 10.1214/07AAP473
 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.
Geoffrey
Grimmett, Percolation, 2nd ed., Grundlehren der Mathematischen
Wissenschaften [Fundamental Principles of Mathematical Sciences],
vol. 321, SpringerVerlag, Berlin, 1999. MR 1707339
(2001a:60114)
 14.
Alexander
E. Holroyd, Sharp metastability threshold for twodimensional
bootstrap percolation, Probab. Theory Related Fields
125 (2003), no. 2, 195–224. MR 1961342
(2003k:60257), 10.1007/s004400020239x
 15.
Alexander
E. Holroyd, The metastability threshold for modified bootstrap
percolation in 𝑑 dimensions, Electron. J. Probab.
11 (2006), no. 17, 418–433 (electronic). MR 2223042
(2007a:82023), 10.1214/EJP.v11326
 16.
Alexander
E. Holroyd, Thomas
M. Liggett, and Dan
Romik, Integrals, partitions, and cellular
automata, Trans. Amer. Math. Soc.
356 (2004), no. 8,
3349–3368 (electronic). MR 2052953
(2005b:60018), 10.1090/S0002994703034172
 17.
Roberto
H. Schonmann, On the behavior of some cellular automata related to
bootstrap percolation, Ann. Probab. 20 (1992),
no. 1, 174–193. MR 1143417
(93b:60231)
 18.
Aernout
C. D. van Enter, Proof of Straley’s argument for bootstrap
percolation, J. Statist. Phys. 48 (1987),
no. 34, 943–945. MR 914911
(88j:82024), 10.1007/BF01019705
 19.
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
 1.
 J. Adler, D. Stauffer, and A. Aharony, Comparison of bootstrap percolation models, J. Phys. (A) 22 (1989), L297L301.
 2.
 M. Aizenman and J. Lebowitz, Metastability effects in bootstrap percolation, J. Phys. (A) 21 (1988), 38013813. MR 968311 (90e:82047)
 3.
 G. Andrews, Partitions with short sequences and mock theta functions, Proc. Nat. Acad. Sci. 102 (2005), 46664671. 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), 545554. MR 2310749 (2008j:05035)
 6.
 J. Balogh, B. Bollobás, and R. Morris, Bootstrap percolation in high dimensions, Combin. Probab. Comput. 19 (2010), no. 56, 643692. MR 2726074
 7.
 J. Balogh, B. Bollobás, and R. Morris, Bootstrap percolation in three dimensions, Ann. Probab. 37 (2009), no. 4, 13291380. MR 2546747 (2011d:60278)
 8.
 K. Bringmann and K. Mahlburg, An extension of the HardyRamanujan circle method and applications to partitions without sequences, to appear in Amer. J. of Math.
 9.
 K. Froböse, Finitesize effects in a cellular automaton for diffusion, J. Stat. Phys. 55 (1989), 12851292. MR 1002492 (90c:82004)
 10.
 J. Gravner and A. Holroyd, Local bootstrap percolation, Electronic Journal of Probability 14 (2009), 385399. MR 2480546 (2010c:60292)
 11.
 J. Gravner and A. Holroyd, Slow convergence in bootstrap percolation, The Annals of Applied Probability 18 (2008), 909928. 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, SpringerVerlag, second edition, 1999. MR 1707339 (2001a:60114)
 14.
 A. Holroyd, Sharp metastability threshold for twodimensional bootstrap percolation, Probability Theory and Related Fields 125 (2003), 195224. MR 1961342 (2003k:60257)
 15.
 A. Holroyd, The metastability threshold for modified bootstrap percolation in d dimensions, Electronic Journal of Probability 11 (2006), 418433. MR 2223042 (2007a:82023)
 16.
 A. Holroyd, T. Liggett, and D. Romik, Integrals, partitions, and cellular automata, Trans. of the AMS 356 (2004), 33493368. MR 2052953 (2005b:60018)
 17.
 R. Schonmann, On the behavior of some cellular automata related to bootstrap percolation, Ann. Prob. 20 (1992), 174193. MR 1143417 (93b:60231)
 18.
 A. van Enter, Proof of Straley's argument for bootstrap percolation, J. Statist. Phys. 48 (1987), no. 34, 943945. MR 914911 (88j:82024)
 19.
 G. Watson, The final problem: An account of the mock theta functions, J. London Math. Soc. 11 (1936), 5580. 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 8690, 50931 Cologne, Germany
Email:
kbringma@math.unikoeln.de
Karl Mahlburg
Affiliation:
Department of Mathematics, Princeton University, Princeton, New Jersey 08544
Email:
mahlburg@math.princeton.edu
DOI:
http://dx.doi.org/10.1090/S000299472012056108
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 DMS0757907 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 DMS0441170.
Article copyright:
© Copyright 2012
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
