The sharp threshold for percolation on expander graphs

Year, pages: 2013, 1141 - 1152

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\in(0,1)$ satisfying $c_n\gg 1/\sqrt{\ln n}$ and $\limsup_{n\rightarrow∞}c_n<1$, the property that the random subgraph contains a giant component of order $c_n|V_n|$ has a sharp threshold.

Shang, Y. 2013. The sharp threshold for percolation on expander graphs. In Mathematica Slovaca, vol. 63, no.5, pp. 1141-1152. 0139-9918. DOI: https://doi.org/10.2478/s12175-013-0161-y

Shang, Y. (2013). The sharp threshold for percolation on expander graphs. Mathematica Slovaca, 63(5), 1141-1152. 0139-9918. DOI: https://doi.org/10.2478/s12175-013-0161-y