Percolation on finite graphs and isoperimetric inequalities

• Noga Alon ^[1] ; Itai Benjamini ^[2] ; Alan Stacey ^[3]
  1. [1] Tel Aviv University

     Tel Aviv University

     Israel

     
  2. [2] Microsof Research and Weizmann Institute
  3. [3] Centre for Mathematical Sciences

  Mostrar afiliaciones +
• Localización: Annals of probability: An official journal of the Institute of Mathematical Statistics, ISSN 0091-1798, Vol. 32, Nº. 3, 1, 2004, págs. 1727-1745
• Idioma: inglés
• DOI: 10.1214/009117904000000414
• Texto completo no disponible (Saber más ...)
• Resumen

  • 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.