Thresholds for contagious sets in random graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2016
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914159125331968 |
|---|---|
| author | Angel, Omer Kolesnik, Brett |
| author_facet | Angel, Omer Kolesnik, Brett |
| contents | For fixed $r\geq 2$, we consider bootstrap percolation with threshold $r$ on the Erdős-Rényi graph ${\cal G}_{n,p}$. We identify a threshold for $p$ above which there is with high probability a set of size $r$ which can infect the entire graph. This improves a result of Feige, Krivelevich and Reichman, which gives bounds for this threshold, up to multiplicative constants.
As an application of our results, we also obtain an upper bound for the threshold for $K_4$-bootstrap percolation on ${\cal G}_{n,p}$, as studied by Balogh, Bollobás and Morris. We conjecture that our bound is asymptotically sharp.
These thresholds are closely related to the survival probabilities of certain time-varying branching processes, and we derive asymptotic formulae for these survival probabilities which are of interest in their own right. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1611_10167 |
| institution | arXiv |
| publishDate | 2016 |
| record_format | arxiv |
| spellingShingle | Thresholds for contagious sets in random graphs Angel, Omer Kolesnik, Brett Probability Combinatorics 05C80, 60K35, 37B15, 60J85, 82B26 For fixed $r\geq 2$, we consider bootstrap percolation with threshold $r$ on the Erdős-Rényi graph ${\cal G}_{n,p}$. We identify a threshold for $p$ above which there is with high probability a set of size $r$ which can infect the entire graph. This improves a result of Feige, Krivelevich and Reichman, which gives bounds for this threshold, up to multiplicative constants. As an application of our results, we also obtain an upper bound for the threshold for $K_4$-bootstrap percolation on ${\cal G}_{n,p}$, as studied by Balogh, Bollobás and Morris. We conjecture that our bound is asymptotically sharp. These thresholds are closely related to the survival probabilities of certain time-varying branching processes, and we derive asymptotic formulae for these survival probabilities which are of interest in their own right. |
| title | Thresholds for contagious sets in random graphs |
| topic | Probability Combinatorics 05C80, 60K35, 37B15, 60J85, 82B26 |
| url | https://arxiv.org/abs/1611.10167 |