the random-graph phase transition

The random-graph phase transition is the abrupt change in global structure that G(n,p) undergoes as the average degree np passes through 1. It is the analogue, in the world of discrete networks, of the freezing of water or the onset of magnetization, and it is the reason random graph theory occupies a place in mathematical physics. The question it answers is: what exactly happens to the size and number of the connected components as edges are added, right around the critical density?

Write p = c/n. There are three regimes. Subcritical (c < 1): all components are O(log n), each almost a tree, and the largest is of size about (log n)/(c - 1 - log c). Critical (c = 1, more precisely p = 1/n): the largest components are of order n^(2/3), there are many of them at this scale, and they have a nontrivial random structure with surplus edges. Supercritical (c > 1): a unique giant of linear size rho(c) n emerges, with the second-largest back to O(log n). The transition is continuous (the giant fraction rho(c) rises continuously from 0), but the historical name 'double jump' comes from looking at it through G(n,m): as m increases past n/2 edges the largest component jumps from O(log n) to n^(2/3) (at the critical point) and then to linear size, two qualitative jumps. The fine structure near c = 1 is the critical window p = (1 + lambda n^(-1/3))/n for fixed real lambda, where the rescaled component sizes converge (Aldous) to the excursion lengths of a Brownian motion with a parabolic drift — a beautiful link to the continuum.

This is the canonical example of an emergent collective phenomenon proved rigorously from first principles, and the template for understanding phase transitions in percolation, the Ising model, satisfiability thresholds, and epidemic models. It matters because it shows that microscopic, independent randomness can produce a sharp macroscopic transition with universal scaling exponents (the n^(2/3) component size, the n^(-1/3) window width). An honest caveat: the exact constants and the continuum limit depend on the model being mean-field (Erdos-Renyi has no geometry); on a lattice the analogous percolation transition has different, dimension-dependent exponents, and the critical window picture above is special to the mean-field, geometry-free setting.