The Giant Component in a Random Subgraph of a Given Graph

摘要

We consider a random subgraph G_p of a host graph G formed by retaining each edge of G with probability p. We address the question of determining the critical value p (as a function of G) for which a giant component emerges. Suppose G satisfies some (mild) conditions depending on its spectral gap and higher moments of its degree sequence. We define the second order average degree d to be d = Σ_v d_v~2/(Σ_v d_v) where d_v denotes the degree of v. We prove that for any ∈ > 0, if p > (1 + ∈)/d then asymptotically almost surely the percolated subgraph G_p has a giant component. In the other direction, if p < (1 - ∈)/d then almost surely the percolated subgraph G_p contains no giant component.