Minimum degree conditions for small percolating sets in bootstrap percolation (Q2185227)

Summary: 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 percolate if eventually all vertices are infected. For every \(r \geq 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 \geq 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.