Projects per year
Abstract
We study the following bootstrap percolation process: given a connected graph $G$, a constant $\rho \in [0, 1]$ and an initial set $A \subseteq V(G)$ of \emph{infected} vertices, at each step a vertex~$v$ becomes infected if at least a $\rho$proportion of its neighbours are already infected (once infected, a vertex remains infected forever). Our focus is on the size $h_\rho(G)$ of a smallest initial set which is \emph{contagious}, meaning that this process results in the infection of every vertex of $G$.
Our main result states that every connected graph $G$ on $n$ vertices has $h_\rho(G) < 2\rho n$ or $h_\rho(G) = 1$ (note that allowing the latter possibility is necessary because of the case $\rho\leq\tfrac{1}{2n}$, as every contagious set has size at least one). This is the bestpossible bound of this form, and improves on previous results of Chang and Lyuu and of Gentner and Rautenbach. We also provide a stronger bound for graphs of girth at least five and sufficiently small $\rho$, which is asymptotically bestpossible.
Original language  English 

Pages (fromto)  638651 
Journal  Random Structures and Algorithms 
Volume  53 
Issue number  4 
Early online date  29 Oct 2018 
DOIs  
Publication status  Published  29 Oct 2018 
Bibliographical note
14 pages, 1 figureKeywords
 bootstrap percolation
 contagious sets
 irreversible dynamic monopolies
Fingerprint
Dive into the research topics of 'Contagious sets in a degreeproportional bootstrap percolation process'. Together they form a unique fingerprint.Projects
 1 Finished

Embeddings in hypergraphs
Engineering & Physical Science Research Council
30/03/15 → 29/03/17
Project: Research Councils