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?)

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