SHARP THRESHOLD FOR PERCOLATION ON EXPANDERS

• 成果类型: Article
• 署名作者: Benjamini, Itai; Boucheron, Stephane; Lugosi, Gabor; Rossignol, Raphael
• 署名单位: Weizmann Institute of Science; Pompeu Fabra University; ICREA; Pompeu Fabra University; Sorbonne Universite; Universite Paris Cite; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite Paris Saclay; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite Paris Saclay
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/10-AOP610
• 发表日期: 2012
• 页码: 130-145
• 关键词: isoperimetric-inequalities; variance; graphs

摘要

We study the appearance of the giant component in random subgraphs of a given large finite graph G = (V, E) in which each edge is present independently with probability p. We show that if G is an expander with vertices of bounded degree, then for any c is an element of ]0, 1[, the property that the random sub-graph contains a giant component of size c vertical bar V vertical bar has a sharp threshold.