The sharp threshold for percolation on expander graphs

Mathematica Slovaca

Yilun Shang¹ 

关键词: percolation;    expander graph;    sharp threshold;    random graph;   

DOI  :  10.2478/s12175-013-0161-y

学科分类：数学（综合）

来源: Slovenska Akademia Vied * Matematicky Ustav / Slovak Academy of Sciences, Mathematical Institute

【 摘 要 】

We consider a random subgraph G n(p) of a finite graph family G n = (V n, E n) formed by retaining each edge of G n independently with probability p. We show that if G n is an expander graph with vertices of bounded degree, then for any c n ∈ (0, 1) satisfying $$c_n gg {1 mathord{left/ {vphantom {1 {sqrt {ln n} }}} ight. kern-ulldelimiterspace} {sqrt {ln n} }}$$ and $$mathop {lim sup }limits_{n o infty } c_n < 1$$, the property that the random subgraph contains a giant component of order c n|V n| has a sharp threshold.

【 授权许可】

Unknown