Percolation on finite graphs and isoperimetric inequalities

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, Komlos and Szemeredi [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.

Published at http://dx.doi.org/10.1214/009117904000000414 in the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• Phase Transitions on Nonamenable Graphs

Cited by in corpus (12)

• Percolation on dense graph sequences
• Giant vacant component left by a random walk in a random d-regular graph
• Universality for critical heavy-tailed network models: Metric structure of maximal components
• Asymptotics of cover times via Gaussian free fields: Bounded-degree graphs and general trees
• Edge percolation on a random regular graph of low degree
• Metastability of the Potts ferromagnet on random regular graphs
• On the critical parameter of interlacement percolation in high dimension
• Rapid social connectivity
• Sharp threshold for percolation on expanders
• Vertex Percolation on Expander Graphs
• Random subshifts of finite type
• Phase Transition of Degeneracy in Minor-Closed Families