The phase transition in site percolation on pseudo-random graphs (Q907264): Difference between revisions

Summary: We establish the existence of the phase transition in site percolation on pseudo-random \(d\)-regular graphs. Let \(G=(V,E)\) be an \((n,d,\lambda)\)-graph, that is, a \(d\)-regular graph on \(n\) vertices in which all eigenvalues of the adjacency matrix, but the first one, are at most \(\lambda\) in their absolute values. Form a random subset \(R\) of \(V\) by putting every vertex \(v\in V\) into \(R\) independently with probability \(p\). Then for any small enough constant \(\epsilon>0\), if \(p=\frac{1-\epsilon}{d}\), then with high probability all connected components of the subgraph of \(G\) induced by \(R\) are of size at most logarithmic in \(n\), while for \(p=\frac{1+\epsilon}{d}\), if the eigenvalue ratio \(\lambda/d\) is small enough as a function of \(\epsilon\), then typically \(R\) contains a connected component of size at least \(\frac{\epsilon n}{d}\) and a path of length proportional to \(\frac{\epsilon^2n}{d}\).