### 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

## Fingerprint Dive into the research topics of 'Percolation on finite graphs and isoperimetric inequalities'. Together they form a unique fingerprint.

## Cite this

*Annals of Probability*,

*32*(3 A), 1727-1745. https://doi.org/10.1214/009117904000000414