Percolation on finite graphs and isoperimetric inequalities

Simple item page
dc.creatorAlon, Noga
dc.creatorBenjamini, Itai
dc.creatorStacey, Alan
dc.date2002-07-12
dc.date2005-03-30
dc.date.accessioned2026-07-07T04:49:39Z
dc.date.available2026-07-07T04:49:39Z
dc.descriptionConsider 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.
dc.descriptionPublished 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)
dc.identifierhttps://arxiv.org/abs/math/0207112
dc.identifierhttp://arxiv.org/abs/math/0207112
dc.identifierAnnals of Probability 2004, Vol. 32, No. 3, 1727-1745
dc.identifierdoi:10.1214/009117904000000414
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/64506
dc.subjectProbability
dc.subjectCombinatorics
dc.subject05C80, 60K35 (Primary)
dc.titlePercolation on finite graphs and isoperimetric inequalities
dc.typetext

Files

Collections

arXiv