Minimum degree conditions for small percolating sets in bootstrap percolation

Abstract

The $r$-neighbour bootstrap process is an update rule for the states of vertices in which `uninfected' vertices with at least $r$ `infected' neighbours become infected and a set of initially infected vertices is said to \emph{percolate} if eventually all vertices are infected. For every $r\ge 3$, a sharp condition is given for the minimum degree of a sufficiently large graph that guarantees the existence of a percolating set of size $r$. In the case $r=3$, for $n$ large enough, any graph on $n$ vertices with minimum degree $\lfloor n/2\rfloor +1$ has a percolating set of size $3$ and for $r\ge 4$ and $n$ large enough (in terms of $r$), every graph on $n$ vertices with minimum degree $\lfloor n/2\rfloor +(r-3)$ has a percolating set of size $r$. A class of examples are given to show the sharpness of these results.

20 pages, 7 figures