CONTAGIOUS SETS IN RANDOM GRAPHS

• 成果类型: Article
• 署名作者: Feige, Uriel; Krivelevich, Michael; Reichman, Daniel
• 署名单位: Weizmann Institute of Science; Tel Aviv University; University of California System; University of California Berkeley
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/16-AAP1254
• 发表日期: 2017
• 页码: 2675-2697
• 关键词: bootstrap percolation; threshold; PROOF

摘要

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 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 := d/n and 1 << d << (nloglogn/log(2)n )(r-1/r). Assuming r > 1 to be a constant that does not depend on n, we prove that m(G, r) = Theta(n/d(r/r-1) logd), with high probability. We also show that the threshold probility for m(G, r) = r to hold is p* = Theta(1/nlog(r-1)n)(1/r).