Matpic
mathematics, in pictures
Concept

Component

A maximal set of points of a graph reachable from each other. A sparse random graph has all of them small; past a threshold it has one holding a definite fraction of everything and all the rest still small.

Named by 2 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

Named alongside it

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

ExpectationPhase transitionRandom graphThresholdBranching processConnectivityFixed pointIsolated vertexLabelled graphPercolation

All concepts