Percolation on finite graphs and isoperimetric inequalities
Alon, Noga ; Benjamini, Itai ; Stacey, Alan
Ann. Probab., Tome 32 (2004) no. 1A, p. 1727-1745 / Harvested from Project Euclid
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.
Publié le : 2004-07-14
Classification:  Percolation,  random graph,  expander,  giant component,  05C80,  60K35
@article{1089808409,
     author = {Alon, Noga and Benjamini, Itai and Stacey, Alan},
     title = {Percolation on finite graphs and isoperimetric inequalities},
     journal = {Ann. Probab.},
     volume = {32},
     number = {1A},
     year = {2004},
     pages = { 1727-1745},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1089808409}
}
Alon, Noga; Benjamini, Itai; Stacey, Alan. Percolation on finite graphs and isoperimetric inequalities. Ann. Probab., Tome 32 (2004) no. 1A, pp.  1727-1745. http://gdmltest.u-ga.fr/item/1089808409/