Percolation on finite graphs and isoperimetric inequalities

By Noga Alon, Itai Benjamini, Alan Stacey. 2002

152 citations recorded by the source corpus.

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

Subfields: Condensed Matter Physics, Discrete Mathematics and Combinatorics, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/c43c79f5bc886e13113d0b5fcd5e043fa8f4c404

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Condensed Matter Physics

In Discrete Mathematics and Combinatorics

In Mathematical Physics

Citations in the corpus

Asymptotics of cover times via Gaussian free fields: Bounded-degree graphs and general trees (2011, methodology): “This type of perturbation method was used by Ajtai, Koml´os and Sze-mer´edi [2] in the study of percolation, and found its applications later in that area (see, e.g., [6, 8]).”
Extreme values for two-dimensional discrete Gaussian free field (2012, unknown): “03 46 v3 [ m at h. PR ] 7 A pr”
Percolation on dense graph sequences. (2007, methodology): “See, for example, Borgs, Chayes, van der Hofstad, Slade and Spencer [8, 9] where the window for transitive graphs obeying the so-called triangle condition was analyzed, Frieze, Krivelevich and Martin [17] where the threshold for random subgraphs of a sequence of quasi-random graphs was analyzed, and”
The Lace Expansion and its Applications (2006, background): “Recently, Alon, Benjamini and Stacey [17] gave an alternate and relatively short proof that pc(d) is asymptotic to 1 2d as d → ∞, with an estimate o(d−1) for the error.”
Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges (2009, background): “In the previous section we discussed a random graph model where the typical Laplacian and adjacency matrices had one “special” eigenvalue with multiplicity 1 and n − 1 “trivial” eigenvalues with a special focus the emergence of a giant component [10, 37, 3, 27, 52, 15].”
Probability on Trees and Networks (2017, background): “The first results were by Alon and Milman (1985) and Alon (1986), and the final form was given by Jerrum and Sinclair (1989) and Lawler and Sokal (1988) independently. Analogous inequalities for measure-preserving actions of groups are due to Lyons and Nazarov (2011). For more information on inequal”