Percolation on dense graph sequences (Q2268697)

Arbitrary sequences of dense graphs \(G(n)\) are considered, and \(G(n,p)\) is the random subgraph of \(G(n)\) obtained by keeping each edge independently with probability \(p=p(n)\). Asymptotically almost surely the subgraph has a giant component, The threshold is given as the inverted largest eigenvalue of the adjacency matrix of \(G(n)\), and the sizes of the largest and second largest components of the subgraph are specified. Generalizations to convergent sequences of weighted graphs and interpretations in terms of multi-type branching processes are also given.