Minimum degree conditions for small percolating sets in bootstrap percolation

Karen Gunderson¹

¹University of Manitoba

The electronic journal of combinatorics, Tome 27 (2020) no. 2

Résumé

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.

Détail

DOI : 10.37236/6937

Classification : 60K35, 05C35
Mots-clés : bootstrap percolation, percolating sets