The phase transition in site percolation on pseudo-random graphs

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, λ)-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 λ in their absolute values. Form a random subset R of V by putting every vertex v ∈ V into R independently with probability p. Then for any small enough constant > 0, if p = 1−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 = 1+d, if the eigenvalue ratio λ/d is small enough as a function of , then typically R contains a connected component of size at least nd and a path of length proportional to 2n d. 1 Introduction and main results Let G = (V,E) be a d-regular graph on n vertices. Form a random vertex subset R ⊆ V by putting every vertex v ∈ V into R independently with probability p. What can be said about the properties of the random subgraph of G induced by R? How large a connected component does it typicall