Percolation on finite graphs and isoperimetric inequalities

Details Percolation on finite graphs and isoperimetric inequalities Percolation on finite graphs and isoperimetric inequalities

2002-07-12

arxiv.org/abs/math/0207112v2

Annals of Probability 2004, Vol. 32, No. 3, 1727-1745

Mathematics

Probability

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

Scientific paper

10.1214/009117904000000414

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.

Affiliated with

Also associated with

No associations

Rating

Percolation on finite graphs and isoperimetric inequalities does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Percolation on finite graphs and isoperimetric inequalities, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Percolation on finite graphs and isoperimetric inequalities will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-710256