SHARP THRESHOLDS FOR CONTAGIOUS SETS IN RANDOM GRAPHS

• 成果类型: Article
• 署名作者: Angel, Omer; Kolesnik, Brett
• 署名单位: University of British Columbia; University of California System; University of California Berkeley
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/17-AAP1325
• 发表日期: 2018
• 页码: 1052-1098
• 关键词: bootstrap percolation; epidemic model; size; trees

摘要

For fixed r >= 2, we consider bootstrap percolation with threshold r on the Erdos-Renyi graph G(n,p). We identify a threshold for p above which there is with high probability a set of size r that 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 obtain an upper bound for the threshold for K-4-percolation on G(n,p), as studied by Balogh, Bollobas and Morris. This bound is shown to be asymptotically sharp in subsequent work. 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.