Percolation on finite graphs and isoperimetric inequalities.

*(English)*Zbl 1046.05071This pretty paper deals with the random graph \(G(p)\) obtained by taking a fixed graph \(G\) on \(n\) vertices (\(n\) is to be thought of as large) and then retaining each edge of \(G\) with probability \(p\), independent of all other edges. In the case \(G=K_{n}\) this of course gives the standard Erdős-Rényi random graph \(G(n,p)\). For \(G(n,p)\) it is well known that, given \(c>0\), the probability that there is more than one \` large\' component (i.e. one whose order is at least \(cn\)) tends to zero as \(n\) goes to infinity.

The paper under review aims to extend this fact to more general graphs \(G\). The authors conjecture that if \((G_{n})\), where \(G_{n}=(V_{n},E_{n})\) has \(n\) vertices, is a sequence of connected vertex-transitive graphs, and \(G_{n}\) has degree \(d_{n}\), and \(d_{n}\leq \Delta\) for all \(n\) (where \(\Delta\) is a constant independent of \(n\)), then for \(c>0\) \[ \sup_{p}P(G(p)\text{~has~more~than~one~component~of~order}\geq cn)\rightarrow 0\text{~as~}n\rightarrow \infty \] provided the diameter of \(G_{n}\) is \(o(n/\log(n))\). (Some such condition on the diameter is required.) This conjecture is known to be true not just for \(G_{n}=K_{n}\) but also for many other \(G_{n}\) which \` resemble\' a finite subgraph of the \(d\)-dimensional integer lattice.

The authors can prove such a conjecture for expanders. Recall that for \(A\subseteq V(G)\), we define \(\partial A\) to be all those vertices in \(V(G)\backslash A\) adjacent to at least one vertex of \(A\), and then define the isoperimetric constant \[ \iota(G)=\min_{A\subseteq V(G), 0<| A| | V| /2}\frac{| \partial A |}{| A |}. \] Then a graph \(G\) is a \(b\)-expander if \(\iota(G)\geq b\). The first main result of the paper (Theorem 2.1) is that, if \((G_{n})\) are \(b\)-expanders with maximum degree \(\leq \Delta\), \(0\leq p_{n}\leq 1\) and \(c>0\), then \[ P(G_{n}(p_{n})\text{~has~more~than~one~component~of~order}\geq cn)\rightarrow 0\text{~as~}n\rightarrow \infty. \]

To sketch the proof: first, a fairly simple counting argument shows that the probability of two or more large components is small for large \(n\) if \(p_{n}\) is large: a branching process argument shows that we need not worry about \(p_{n}\) small. The \` hard-core\' case is thus \(p_{n}\in [x,1-x]\) where \(x=\min(1/(2\Delta),1-A)\) where \(e\)=2.718.... and \(\Delta e A^{b}<1\). To deal with this case, given a subgraph \(H\) of \(G\), say that \(e\in E(G_{n})\) is an \(L\)-bridge if \(H_{e}\) (i.e. \(H\) with \(e\) removed) contains two large components, joined by \(e\), and let \(S(e,c,n)\) be the event that \(e\) is an \(L\)-bridge in \(G_{n}(p_{n})\). One then bounds from above the probability of the event \(S'(c,n,r)\) that \(S(e,c,n)\) occurs for an edge in the ball of radius \(r\) about a randomly chosen vertex, using the expanding properties. The proof is then completed by bounding \(P(S'(c,n,r))\) from below in terms of the probability of two or more large components. This simplistic overview conceals a lot of ingenuity.

In fact, the authors can show that not only will large components (in the above sense) usually be unique, but also that there is an \(\omega<1\) such that (in the previous notation) \[ P(G_{n}(p_{n})\text{~has~more~than~one~component~of~order}\geq n^{\omega})\rightarrow 0\text{~as~}n\rightarrow \infty . \] The best possible value of \(\omega\) is not yet clear.

If \(G\) is a \(d\)-regular graph of large enough (in suitable senses) girth and isoperimetric number, the authors show in section 3 that provided \(p=(1+\varepsilon)/(d-1)\) then \(G(p)\) will have a large component with probability tending to 1. The crude idea, already present in M. Ajtai, J. Komlós and E. Szemerédi [Combinatorica 2, 1–7 (1982; Zbl 0489.05053)], is to show many vertices lie in not-too-small components of \(G(p)\) (a branching process argument, using the large girth) and then that adding only a few more edges makes many of these components merge into a large component, this latter step depending on the good expanding properties. An attractive feature is that similar ideas allow the authors to reprove (in section 4) the famous result of H. Kesten [Asymptotics in high dimensions for percolation. Disorder in physical systems, 219–240 (1984; Zbl 0725.60112)] that the critical probability for bond percolation in \({\mathbb Z}^{d}\) is \((1+o(1))/(2d)\), the \(o(1)\) term tending to 0 as \(d\rightarrow\infty\).

The authors close by observing that (in the situation of the first five paragraphs of this review) the (unique) large component of \(G(p)\) should itself have reasonably good expanding properties, sketching a proof of a result in this direction and making a further conjecture.

The paper under review aims to extend this fact to more general graphs \(G\). The authors conjecture that if \((G_{n})\), where \(G_{n}=(V_{n},E_{n})\) has \(n\) vertices, is a sequence of connected vertex-transitive graphs, and \(G_{n}\) has degree \(d_{n}\), and \(d_{n}\leq \Delta\) for all \(n\) (where \(\Delta\) is a constant independent of \(n\)), then for \(c>0\) \[ \sup_{p}P(G(p)\text{~has~more~than~one~component~of~order}\geq cn)\rightarrow 0\text{~as~}n\rightarrow \infty \] provided the diameter of \(G_{n}\) is \(o(n/\log(n))\). (Some such condition on the diameter is required.) This conjecture is known to be true not just for \(G_{n}=K_{n}\) but also for many other \(G_{n}\) which \` resemble\' a finite subgraph of the \(d\)-dimensional integer lattice.

The authors can prove such a conjecture for expanders. Recall that for \(A\subseteq V(G)\), we define \(\partial A\) to be all those vertices in \(V(G)\backslash A\) adjacent to at least one vertex of \(A\), and then define the isoperimetric constant \[ \iota(G)=\min_{A\subseteq V(G), 0<| A| | V| /2}\frac{| \partial A |}{| A |}. \] Then a graph \(G\) is a \(b\)-expander if \(\iota(G)\geq b\). The first main result of the paper (Theorem 2.1) is that, if \((G_{n})\) are \(b\)-expanders with maximum degree \(\leq \Delta\), \(0\leq p_{n}\leq 1\) and \(c>0\), then \[ P(G_{n}(p_{n})\text{~has~more~than~one~component~of~order}\geq cn)\rightarrow 0\text{~as~}n\rightarrow \infty. \]

To sketch the proof: first, a fairly simple counting argument shows that the probability of two or more large components is small for large \(n\) if \(p_{n}\) is large: a branching process argument shows that we need not worry about \(p_{n}\) small. The \` hard-core\' case is thus \(p_{n}\in [x,1-x]\) where \(x=\min(1/(2\Delta),1-A)\) where \(e\)=2.718.... and \(\Delta e A^{b}<1\). To deal with this case, given a subgraph \(H\) of \(G\), say that \(e\in E(G_{n})\) is an \(L\)-bridge if \(H_{e}\) (i.e. \(H\) with \(e\) removed) contains two large components, joined by \(e\), and let \(S(e,c,n)\) be the event that \(e\) is an \(L\)-bridge in \(G_{n}(p_{n})\). One then bounds from above the probability of the event \(S'(c,n,r)\) that \(S(e,c,n)\) occurs for an edge in the ball of radius \(r\) about a randomly chosen vertex, using the expanding properties. The proof is then completed by bounding \(P(S'(c,n,r))\) from below in terms of the probability of two or more large components. This simplistic overview conceals a lot of ingenuity.

In fact, the authors can show that not only will large components (in the above sense) usually be unique, but also that there is an \(\omega<1\) such that (in the previous notation) \[ P(G_{n}(p_{n})\text{~has~more~than~one~component~of~order}\geq n^{\omega})\rightarrow 0\text{~as~}n\rightarrow \infty . \] The best possible value of \(\omega\) is not yet clear.

If \(G\) is a \(d\)-regular graph of large enough (in suitable senses) girth and isoperimetric number, the authors show in section 3 that provided \(p=(1+\varepsilon)/(d-1)\) then \(G(p)\) will have a large component with probability tending to 1. The crude idea, already present in M. Ajtai, J. Komlós and E. Szemerédi [Combinatorica 2, 1–7 (1982; Zbl 0489.05053)], is to show many vertices lie in not-too-small components of \(G(p)\) (a branching process argument, using the large girth) and then that adding only a few more edges makes many of these components merge into a large component, this latter step depending on the good expanding properties. An attractive feature is that similar ideas allow the authors to reprove (in section 4) the famous result of H. Kesten [Asymptotics in high dimensions for percolation. Disorder in physical systems, 219–240 (1984; Zbl 0725.60112)] that the critical probability for bond percolation in \({\mathbb Z}^{d}\) is \((1+o(1))/(2d)\), the \(o(1)\) term tending to 0 as \(d\rightarrow\infty\).

The authors close by observing that (in the situation of the first five paragraphs of this review) the (unique) large component of \(G(p)\) should itself have reasonably good expanding properties, sketching a proof of a result in this direction and making a further conjecture.

Reviewer: David B. Penman (Colchester)

##### MSC:

05C80 | Random graphs (graph-theoretic aspects) |

60K35 | Interacting random processes; statistical mechanics type models; percolation theory |

##### References:

[1] | Ajtai, M., Komlós, J. and Szemerédi, E. (1982). Largest random component of a \(k\)-cube. Combinatorica 2 1–7. · Zbl 0489.05053 · doi:10.1007/BF02579276 |

[2] | Alon, N. (1991). A parallel algorithmic version of the local lemma. Random Structures Algorithms 2 367–378. · Zbl 0768.05086 · doi:10.1002/rsa.3240020403 |

[3] | Alon, N. and Chung, F. R. K. (1988). Explicit construction of linear sized tolerant networks. Discrete Math. 72 15–19. · Zbl 0657.05068 · doi:10.1016/0012-365X(88)90189-6 |

[4] | Alon, N. and Spencer, J. H. (2000). The Probabilistic Method , 2nd ed. Wiley, New York. · Zbl 0996.05001 |

[5] | Babai, L. and Szegedy, M. (1992). Local expansion of symmetrical graphs. Combin. Probab. Comput. 1 1–11. · Zbl 0792.05064 · doi:10.1017/S0963548300000031 |

[6] | Behrends, E. (1999). Introduction to Markov Chains with Special Emphasis on Rapid Mixing . Vieweg, Wiesbaden. · Zbl 0953.60063 |

[7] | Benjamini, I. and Schramm, O. (1996). Percolation beyond \(\mathbbZ^d\), many questions and a few answers. Electron. Comm. Probab. 1 71–82. · Zbl 0890.60091 · emis:journals/EJP-ECP/EcpVol1/paper8.abs.html · eudml:119473 |

[8] | Bollobás, B. (1984). The evolution of random graphs. Trans. Amer. Math. Soc. 286 257–274. · Zbl 0579.05046 · doi:10.2307/1999405 |

[9] | Bollobás, B. (2001). Random Graphs , 2nd ed. Academic Press, London. · Zbl 0979.05003 |

[10] | Bollobás, B. and Kohayakawa, Y. (1994). Percolation in high dimensions. European J. Combin. 15 113–125. · Zbl 0789.60093 · doi:10.1006/eujc.1994.1014 |

[11] | Falconer, K. J. and Grimmett, G. R. (1992). On the geometry of random Cantor sets and fractal percolation. J. Theoret. Probab. 5 465–485. · Zbl 0752.60007 · doi:10.1007/BF01060430 |

[12] | Friedgut, E. and Kalai, G. (1996). Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc. 124 2993–3002. · Zbl 0864.05078 · doi:10.1090/S0002-9939-96-03732-X |

[13] | Gerl, P. (1988). Random walks on graphs with a strong isoperimetric inequality. J. Theoret. Probab. 1 171–187. · Zbl 0639.60072 · doi:10.1007/BF01046933 |

[14] | Grimmett, G. (1989). Percolation . Springer, New York. · Zbl 0691.60089 |

[15] | Hara, T. and Slade, G. (1990). Mean-field critical phenomena for percolation in high dimensions. Comm. Math. Physics 128 333–391. · Zbl 0698.60100 · doi:10.1007/BF02108785 |

[16] | Harris, T. (1963). The Theory of Branching Processes. Springer, Berlin. · Zbl 0117.13002 |

[17] | Janson, S., Łuczak, T. and Rucinski, A. (2000). Random Graphs . Wiley, New York. |

[18] | Kesten, H. (1990). Asymptotics in high dimension for percolation. In Disorder in Physical Systems (G. R. Grimmett and D. J. A. Welsh, eds.) 219–240. Oxford Univ. Press. · Zbl 0725.60112 |

[19] | Liggett, T., Schonmann, R. and Stacey, A. (1997). Domination by product measures. Ann. Probab. 25 71–95. · Zbl 0882.60046 · doi:10.1214/aop/1024404279 |

[20] | Lubotzky, A. (1994). Discrete Groups , Expanding Graphs , and Invariant Measures . Birkhäuser, Basel. · Zbl 0826.22012 |

[21] | Lyons, R. (2000). Phase transitions on nonamenable graphs. Probabilistic techniques in equilibrium and nonequilibrium statistical physics. J. Math. Phys. 41 1099–1126. · Zbl 1034.82014 · doi:10.1063/1.533179 |

[22] | Lyons, R. and Schramm, O. (1999). Indistinguishability of percolation clusters. Ann. Probab. 27 1809–1836. · Zbl 0960.60013 · doi:10.1214/aop/1022677549 |

[23] | Malon, C. and Pak, I. (2002). Percolation on finite Cayley graphs. Lecture Notes in Comput. Sci. 2483 91–104. Springer, Berlin. · Zbl 1030.05057 · link.springer.de |

[24] | Reingold, O., Vadhan, S. and Wigderson, A. (2002). Entropy waves, the zig-zag graph product, and new constant-degree expanders. Ann. of Math. (2) 155 157–187. · Zbl 1008.05101 · doi:10.2307/3062153 |

[25] | Stacey, A. (2001). The contact process on finite trees. Probab. Theory Related Fields 121 551–576. · Zbl 1081.60560 |

[26] | Upfal, E. (1994). Tolerating linear number of faults in networks of bounded degree. Inform. and Comput. 115 312–320. · Zbl 0938.68524 · doi:10.1006/inco.1994.1099 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.