Contagious sets in random graphs

DOI10.1214/16-AAP1254zbMATH Open1387.05233arXiv1602.01751MaRDI QIDQ1688015FDOQ1688015

Uriel Feige, Michael Krivelevich, Daniel Reichman

Publication date: 4 January 2018

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: We consider the following activation process in undirected graphs: a vertex is active either if it belongs to a set of initially activated vertices or if at some point it has at least $r$ active neighbors. A emph{contagious set} is a set whose activation results with the entire graph being active. Given a graph $G$, let $m(G,r)$ be the minimal size of a contagious set. We study this process on the binomial random graph $G:=G(n,p)$ with $p:=fracdn$ and $1lldllleft(fracnloglognlo{g}^{2}night{)}^{fracr-1r}$. Assuming $r>1$ to be a constant that does not depend on $n$, we prove that ${\displaystyle }$m(G,r) = Thetaleft(frac{n}{d^{frac{r}{r-1}}log d} ight),${\displaystyle }$ with high probability. We also show that the threshold probability for $m(G,r)=r$ to hold is $p^{*}=Thetaleft(frac1(nlo{g}^{r-1}n{)}^{1/r}ight)$.

Full work available at URL: https://arxiv.org/abs/1602.01751

Recommendations

• Contagious sets in dense graphs
• Contagious sets in dense graphs
• Contagious sets in expanders
• New bounds for contagious sets
• Sharp thresholds for contagious sets in random graphs

zbMATH Keywords

random graphsbootstrap percolationcontagious setsminimum contagious set

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05)

Cited In (16)

• Dynamic monopolies in two-way bootstrap percolation
• Percolating sets in bootstrap percolation on the Hamming graphs and triangular graphs
• Minimum degree conditions for small percolating sets in bootstrap percolation
• Bootstrap percolation with inhibition
• Sharp thresholds for contagious sets in random graphs
• Large deviations for subcritical bootstrap percolation on the Erdős-Rényi graph
• Bootstrap percolation on the stochastic block model
• Rumor spreading: A trigger for proliferation or fading away
• Contagious sets in dense graphs
• Deterministic bootstrap percolation on trees
• On the spread of influence in graphs
• The Maximum Label Propagation Algorithm on Sparse Random Graphs
• Smallest percolating sets in bootstrap percolation on grids
• New ordering methods to construct contagious sets and induced degenerate subgraphs
• Containing viral spread on sparse random graphs: bounds, algorithms, and experiments
• Threshold behavior of bootstrap percolation

This page was built for publication: Contagious sets in random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1688015)