Percolation on finite graphs and isoperimetric inequalities

Noga Alon, Itai Benjamin, Alan Stacey

Research output: Contribution to journalArticle

68 Scopus citations

Abstract

Consider a uniform expanders family Gn with a uniform bound on the degrees. It is shown that for any p and c > 0, a random subgraph of Gn obtained by retaining each edge, randomly and independently, with probability p, will have at most one cluster of size at least c|Gn|, 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 languageEnglish (US)
Pages (from-to)1727-1745
Number of pages19
JournalAnnals of Probability
Volume32
Issue number3 A
DOIs
StatePublished - Jul 1 2004
Externally publishedYes

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