In this paper we fill in a fundamental gap in the extremal bootstrap percolation literature, by providing the first proof of the fact that for all $d \geq 1$, the size of the smallest percolating sets in $d$-neighbour bootstrap percolation on $[n]^d$, the $d$-dimensional grid of size $n$, is $n^{d-1}$. Additionally, we prove that such sets percolate in time at most $c_d n^2$, for some constant $c_d >0 $ depending on $d$ only.
@article{10_37236_9582,
author = {Micha{\l} Przykucki and Thomas Shelton},
title = {Smallest percolating sets in bootstrap percolation on grids},
journal = {The electronic journal of combinatorics},
year = {2020},
volume = {27},
number = {4},
doi = {10.37236/9582},
zbl = {1456.60264},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9582/}
}
TY - JOUR
AU - Michał Przykucki
AU - Thomas Shelton
TI - Smallest percolating sets in bootstrap percolation on grids
JO - The electronic journal of combinatorics
PY - 2020
VL - 27
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/9582/
DO - 10.37236/9582
ID - 10_37236_9582
ER -
%0 Journal Article
%A Michał Przykucki
%A Thomas Shelton
%T Smallest percolating sets in bootstrap percolation on grids
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/9582/
%R 10.37236/9582
%F 10_37236_9582
Michał Przykucki; Thomas Shelton. Smallest percolating sets in bootstrap percolation on grids. The electronic journal of combinatorics, Tome 27 (2020) no. 4. doi: 10.37236/9582
