Sharp threshold for percolation on expanders

2011. január 6. csütörtök 16:15

In this joint work with I. Benjamini, S. Boucheron, and R. Rossignol, we study the appearance of the giant component in random subgraphs of a given finite graph G = (V, E) in which each edge is present independently with probability p. We show that if G is an expander with vertices of bounded degree, then for any c∈(0, 1), the property that the random subgraph contains a giant component of size c|V| has a sharp threshold.