Explosive appearance of cores and bootstrap percolation on lattices

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)$$ 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$$ ℓ p balls for $$p\in [1,\infty ]$$ p ∈ [ 1 , ∞ ] .