A Sharp Threshold for Network Reliability
Michael Krivelevich, Benny Sudakov, Van H. Vu · Combinatorics Probability Computing · 2002
Given a graph G on n vertices with average degree d, form a random subgraph Gp by choosing each edge of G independently with probability p. Strengthening a classical result of Margulis we prove that, if the edge connectivity k(G) satisfies k(G) [Gt ] d/log n, then the connectivity threshold in Gp is sharp. This result is asymptotically tight.