Percolation on finite graphs and isoperimetric inequalities. (Q1878979): Difference between revisions

This 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 \textit{M. Ajtai}, \textit{J. Komlós} and \textit{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 \textit{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.