Matpic
mathematics, in pictures
Concept

Phase transition

A qualitative change in a system's behaviour produced by a small change in a parameter. In a random structure it is a property whose probability moves from near zero to near one over a vanishing range, and the sharpness is a fact about the limit rather than about any finite case.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

The chance of being connected, against the chance of an edge. Curves of the exact probability that a random graph on three to six labelled points is connected, plotted against the probability of each individual edge.

The moment everything joins up

Add edges to a set of points one chance at a time and the graph goes from dust to a single piece — not gradually, but over a window that narrows as the point count grows. The last obstacle is almost always a single point with no edge at all, and that is what fixes where the change happens.

probability · Random graphs The moment a giant piece appears. The largest component's share of 900 points plotted against the average degree, with the measured values as dots and the predicted curve behind them. The curve is flat at zero below an average degree of one and rises steeply above it.

The moment a giant appears

Raise the chance of an edge slowly and a random graph does nothing for a long time, then in a narrow window acquires a component holding a definite fraction of everything. The fraction is the root of an equation, and the equation says why the transition is where it is.

probability · Random graphs One piece, and connected, are different thresholds. Two curves against the average degree for graphs of 400 points: the largest component's share, rising from an average degree of one, and the probability of connectivity, rising only near the logarithm of the point count.

Two thresholds, not one

A random graph acquires a piece holding most of its points at average degree one, and is still not connected. Connectivity waits until the average degree reaches the logarithm of the size, and what holds it up is the very last isolated point.

probability · Random graphs

Named alongside it

The objects these essays reach for when they reach for this one.

ExpectationRandom graphThresholdComponentConnectivityIsolated vertexBranching processCoupon collectorFirst momentFixed pointLabelled graphPercolation

All concepts