Phase transitions
p = c/n: at c = 1, giant component emerges. Below: all components O(log n). Above: giant component size ~n.
Advertisement
Connectivity threshold
p = log(n)/n: graph connected w.h.p. Just below: many isolated vertices.
Advertisement
Diameter
Above connectivity threshold: diameter ≈ log(n) / log(np). Small-world.
Alternative model
G(n, M): fix M edges, uniformly random. Equivalent for many purposes as p·(n choose 2) ≈ M.