Matpic
mathematics, in pictures
Concept

Threshold

The value of a parameter at which a property changes from almost never holding to almost always holding. For a monotone property of a random graph one always exists, and locating it is usually a matter of counting what the property requires.

Named by 4 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 A triangle appears when the count says it should. The measured probability of containing a triangle against the edge chance, on graphs of 200 points, beside the expected number of triangles capped at one.

Finding a threshold with two moments

Every monotone property of a random graph has a threshold, and locating one is nearly always the same two calculations — count what the property needs, and check the count does not concentrate on rare cases. The triangle is where the method is cleanest.

probability · Random graphs

Named alongside it

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

ExpectationRandom graphPhase transitionComponentConnectivityFirst momentIsolated vertexBranching processCounting-two waysCoupon collectorFixed pointLabelled graph

All concepts