Erdős–Rényi Giant Component Phase Transition

Erdős–Rényi G(N,p) Model

Each pair of N nodes is connected independently with probability p. At p_c = 1/N (λ = pN = 1), a phase transition occurs:

• λ < 1: All components are small (O(log N))
• λ = 1: Critical — giant component of size O(N^2/3)
• λ > 1: Giant component of size S ≈ (1 − e^−λ)N

Red nodes belong to the largest component. The phase transition is sharp as N→∞ — one of the most beautiful results in random graph theory (1960).