Random subgraphs of finite graphs : II. The lace expansion and the triangle condition

By Christian Borgs, Jennifer Tour Chayes, Remco van der Hofstad, Gordon Slade, Joel H. Spencer. 2004

107 citations recorded by the source corpus.

In a previous paper we defined a version of the percolation triangle condition that is suitable for the analysis of bond percolation on a finite connected transitive graph, and showed that this triangle condition implies that the percolation phase transition has many features in common with the phase transition on the complete graph. In this paper we use a new and simplified approach to the lace expansion to prove quite generally that, for finite graphs that are tori, the triangle condition for percolation is implied by a certain triangle condition for simple random walks on the graph. The latter is readily verified for several graphs with vertex set {0, 1, ..., r - 1} n , including the Hamming cube on an alphabet of r letters (the n-cube, for r = 2), the n-dimensional torus with nearest-neighbor bonds and n sufficiently large, and the n-dimensional torus with n > 6 and sufficiently spread-out (long range) bonds. The conclusions of our previous paper thus apply to the percolation phase transition for each of the above examples.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

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

How researchers see this paper

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

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Percolation on dense graph sequences. (2007, methodology): “The study of percolation on finite graphs is much more delicate than that of percolation on infinite graphs; indeed, percolation on finite graphs provides the finite-size scaling behavior of percolation on the corresponding infinite graphs (see, e.g., Borgs, Chayes, Kesten and Spencer [11] for the s”
Random Graphs and Complex Networks (2016, background): “This work has deepened my understanding of the basic properties of random graphs, and many of the proofs presented here have been inspired by our work in [58, 59, 60].”