×

Percolation in general graphs. (English) Zbl 1238.05244

Summary: 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 \(\tilde {d}\) to be \(\tilde {d} = \sum_v d^2_v/(\sum_v d_v)\), where \(d_v\) denotes the degree of \(v\).
We prove that for any \(\epsilon > 0\), if \(p > (1 + \epsilon)/\overline{d}\), then asymptotically almost surely, the percolated subgraph \(G_p\) has a giant component. In the other direction, if \(p < (1 - \epsilon)/\tilde {d}\), then almost surely, the percolated subgraph \(G_p\) contains no giant component. An extended abstract of this paper appeared in [the authors, “The giant component in a random subgraph of a given graph”, Lect. Notes Comput. Sci. 5427, 38–49 (2009; Zbl 1207.05177)]. The main theorems are strengthened with much weaker assumptions.

MSC:

05C80 Random graphs (graph-theoretic aspects)

Citations:

Zbl 1207.05177