Site percolation on pseudo-random graphs

In the site percolation model, a random induced subgraph G[R] of a given graph G is formed by putting every vertex v of G into a random subset R with probability p and independently. One then researches typical properties of G[R], like the sizes of its connected components.

 Here we study site percolation on pseudo-random graphs, specifically on (n,d,\lambda)-graphs, which are d-regular graphs on n vertices with all eigenvalues but the first (trivial) one bounded in absolute values by \lambda. It is well known that, assuming that the eigenvalue ratio \lambda/d is small, the edge distribution of an (n,d,\lambda)-graph resembles closely that of a truly random graph G(n,p) with the same expected density p=d/n. 

 We focus on the so-called supercritical regime p=(1+\epsilon)/d, for a positive constant \epsilon>0. In this range, we establish the asymptotic order of the giant component (a component of size proportional to |R|) in G[R] and show that it is typically unique. We also discuss further properties of the giant.

 A joint work with Michael Krivelevich.