Bootstrap percolation in Ore-type graphs

The $r$-neighbour bootstrap process describes an infection process on a graph, where we start with a set of initially infected vertices and an uninfected vertex becomes infected as soon as it has $r$ infected neighbours. An inital set of infected vertices is called percolating if at the end of the bootstrap process all vertices are infected. We give Ore-type conditions that guarantee the existence of a small percolating set of size $l\le 2r-2$ if the number of vertices $n$ of our graph is sufficiently large: if $l\ge r$ and satisfies $2r\ge l+2\lfloor \sqrt{2(l-r)+0.25}+2.5\rfloor -1$ then there exists a percolating set of size $l$ for every graph in which any two non-adjacent vertices $x$ and $y$ satisfy $deg(x)+deg(y) \geq n+4r-2l-2\lfloor\sqrt{2(l-r)+0.25}+2.5 \rfloor-1$andif$l$islargerwith$l\leq 2r-2$thereexistsapercolatingsetofsize$l$if$deg(x)+deg(y) \geq n+2r-l-2$. Our results extend the work of Gunderson, who showed that a graph with minimum degree $\lfloor n\mathrm{/}2\rfloor +r-3$ has a percolating set of size $r \geq 4$\mathrm{.}Wealsogiveboundsforarbitrarilylarge$l$ in the minimum degree setting.