Contagious sets in a degree‐proportional bootstrap percolation process. Issue 4 (29th October 2018)

• Record Type: Journal Article
• Authors: Garbe, Frederik; Mycroft, Richard; McDowell, Andrew
• Is Part Of: Random structures & algorithms. Volume 53:Issue 4(2018)
• Page Start: 638
• Page End: 651
• Publication Date: 2018-10-29
• Subjects: bootstrap percolation -- contagious sets -- irreversible dynamic monopolies; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20818
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : We study the following bootstrap percolation process: given a connected graph G, a constant ρ ∈ [0, 1] and an initial set A ⊆ V ( G ) of infected vertices, at each step a vertex v becomes infected if at least a ρ ‐proportion of its neighbors are already infected (once infected, a vertex remains infected forever). Our focus is on the size h ρ ( G ) of a smallest initial set which is 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 ρ ( G ) < 2 ρn or h ρ ( G ) = 1 (note that allowing the latter possibility is necessary because of the case ρ ≤ 1 2 n, as every contagious set has size at least one). This is the best‐possible 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 ρ, which is asymptotically best‐possible.