Explosive appearance of cores and bootstrap percolation on lattices
Open Access
- 27 April 2026
- journal article
- research article
- Published by Springer Nature in Combinatorica
- Vol. 46 (3) , 17
Abstract
Consider the process where the n vertices of a square 2-dimensional torus appear consecutively in a random order. We show that typically the size of the 3-core of the corresponding induced unit-distance graph transitions from 0 to $$n-o(n)$$ within a single step. Equivalently, by infecting the vertices of the torus in a random order, under two-neighbour bootstrap percolation, the size of the infected set transitions instantaneously from o ( n ) to n . This hitting time result answers a question of Benjamini. We also study the much more challenging and general setting of bootstrap percolation on two-dimensional lattices for a variety of finite-range infection rules. In this case, powerful but fragile bootstrap percolation tools such as the rectangles process and the Aizenman–Lebowitz lemma become unavailable. We develop a new method complementing and replacing these standard techniques, thus allowing us to prove the above hitting time result for a wide family of threshold bootstrap percolation rules on the 2-dimensional square lattice, including neighbourhoods given by large $$\ell ^p$$ balls for $$p\in [1,\infty ]$$ .
Keywords
All Related Versions
Funding Information
- TU Wien
This publication has 25 references indexed in Scilit:
- Sharp metastability transition for two-dimensional bootstrap percolation with symmetric isotropic threshold rulesProbability Theory and Related Fields, 2024
- -core: Theories and applicationsPhysics Reports, 2019
- Hamiltonicity in random graphs is born resilientJournal of Combinatorial Theory, Series B, 2019
- The stripping process can be slow: Part IRandom Structures & Algorithms, 2018
- Bootstrap Percolation on Infinite Trees and Non-Amenable GroupsCombinatorics, Probability and Computing, 2006
- Sharp thresholds in Bootstrap percolationPhysica A: Statistical Mechanics and its Applications, 2003
- Random Graphs2000
- Sudden Emergence of a Giantk-Core in a Random GraphJournal of Combinatorial Theory, Series B, 1996
- Size and connectivity of the k-core of a random graphDiscrete Mathematics, 1991
- On the method of bounded differences1989