the Erdos-Renyi random graph

The Erdos-Renyi random graph is the foundational object of the whole field: a graph on n labelled vertices generated by pure chance. There are two closely related versions. In G(n,p), each of the C(n,2) possible edges is included independently with probability p, so the graph is a product of independent coin flips. In G(n,m), one chooses uniformly at random one graph out of all those with exactly m edges. The question the model answers is: what does a 'typical' large graph look like, and how do its global features (is it connected? does it contain a triangle? what is its largest cluster?) depend on how dense it is?

The power of the model is that almost every interesting property obeys a zero-one law as n grows: for a fixed kind of question, the probability that G(n,p) has the property tends either to 0 or to 1, with the switch happening as p crosses a threshold. The two models are essentially interchangeable when m is about p times C(n,2): G(n,m) is G(n,p) conditioned on the number of edges, and since the edge count is sharply concentrated (it is a sum of independent indicators, mean p C(n,2)), results transfer between them for any reasonable property. The natural scaling is to write p = p(n) as a function of n; the regime p = c/n (constant average degree c) is where the dramatic structural transitions live, while p = (log n)/n is the scale of connectivity. The phrase 'with high probability' (whp) means with probability tending to 1 as n tends to infinity, and almost all theorems in the field are whp statements.

Erdos and Renyi introduced this in 1959-1960 and discovered that random graphs are not amorphous but pass through sharply defined stages as edges are added — the birth of a giant component, the swallowing-up of isolated vertices, the onset of connectivity — each at its own threshold. This is why the model matters far beyond combinatorics: it is the null model against which real networks are compared, the testbed for the probabilistic method, and the simplest setting in which a phase transition can be proved with bare hands. An honest caveat: real-world networks are almost never well described by G(n,p) — their degree distributions are heavy-tailed, they have many triangles and community structure — so G(n,p) is best seen as a baseline and a source of techniques, not a realistic model, which is exactly why the configuration model, preferential attachment, and block models were later developed.