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.