## Abstract

Consider a uniform expanders family G_{n} with a uniform bound on the degrees. It is shown that for any p and c > 0, a random subgraph of G_{n} obtained by retaining each edge, randomly and independently, with probability p, will have at most one cluster of size at least c|G_{n}|, with probability going to one, uniformly in p. The method from Ajtai, Komlós and Szemerédi [Combinatorica 2 (1982) 1-7] is applied to obtain some new results about the critical probability for the emergence of a giant component in random subgraphs of finite regular expanding graphs of high girth, as well as a simple proof of a result of Kesten about the critical probability for bond percolation in high dimensions. Several problems and conjectures regarding percolation on finite transitive graphs are presented.

Original language | English (US) |
---|---|

Pages (from-to) | 1727-1745 |

Number of pages | 19 |

Journal | Annals of Probability |

Volume | 32 |

Issue number | 3 A |

DOIs | |

State | Published - Jul 1 2004 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Statistics and Probability
- Statistics, Probability and Uncertainty

## Keywords

- Expander
- Giant component
- Percolation
- Random graph