The emergence of a giant component in random subgraphs of pseudo‐random graphs

Let G be a d‐regular graph G on n vertices. Suppose that the adjacency matrix of G is such that the eigenvalue λ which is second largest in absolute value satisfies λ = o(d). Let G_p with p = α/d be obtained from G by including each edge of G independently with probability p. We show that if α < 1, then whp the maximum component size of G_p is O(log n) and if α > 1, then G_p contains a unique giant component of size Ω(n), with all other components of size O(log n). © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2004