Bootstrap Percolation on Degenerate Graphs

In this paper we focus on r-neighbor bootstrap percolation on finite graphs, which is a process on a graph evolving in discrete rounds where, initially, a set $$A_0$$ of vertices gets infected. Now, subsequently, an uninfected vertex becomes infected if it is adjacent to at least r infected vertices. Call $$A_f$$ the set of vertices that are infected after the process stops. More formally, we let $${A_t:=A_{t-1}\cup \{v\in V: |N(v)\cap A_{t-1}|\ge r\}}$$ , where N(v) is the neighborhood of some vertex v. Then $$A_f=\bigcup _{t>0} A_t$$ . We are mainly interested in the size of the final set $$A_f$$ . We present a theorem which bounds the size of the final infected set for degenerate graphs in terms of $$\vert A_0\vert ,d$$ and r. To be more precise, for a d-degenerate graph, if $$r\ge d+1$$ , the size of $$A_f$$ is bounded from above by $$(1+\tfrac{d}{r-d})|A_0|$$ .