Percolation on finite graphs and isoperimetric inequalities
Open Access
- 1 July 2004
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Probability
- Vol. 32 (3), 1727-1745
- https://doi.org/10.1214/009117904000000414
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.Keywords
Other Versions
This publication has 24 references indexed in Scilit:
- Phase transitions on nonamenable graphsJournal of Mathematical Physics, 2000
- Domination by product measuresThe Annals of Probability, 1997
- Percolation Beyond $Z^d$, Many Questions And a Few AnswersElectronic Communications in Probability, 1996
- Tolerating a Linear Number of Faults in Networks of Bounded DegreeInformation and Computation, 1994
- Percolation in High DimensionsEuropean Journal of Combinatorics, 1994
- On the geometry of random Cantor sets and fractal percolationJournal of Theoretical Probability, 1992
- A parallel algorithmic version of the local lemmaRandom Structures & Algorithms, 1991
- Explicit construction of linear sized tolerant networksDiscrete Mathematics, 1988
- Random walks on graphs with a strong isoperimetric propertyJournal of Theoretical Probability, 1988
- The Evolution of Random GraphsTransactions of the American Mathematical Society, 1984