Sharp threshold for percolation on expanders

Abstract

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 in ]0,1[, the property that the random subgraph contains a giant component of size c|V| has a sharp threshold.

Published in at http://dx.doi.org/10.1214/10-AOP610 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (3)

• Percolation on finite graphs and isoperimetric inequalities
• Threshold for monotone symmetric properties through a logarithmic Sobolev inequality
• Edge percolation on a random regular graph of low degree