Matpic
mathematics, in pictures
Concept

Isolated vertex

A point of a graph with no edges. In a random graph their expected number is the point count times e to the minus the average degree, and their disappearance is exactly when the graph becomes connected.

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 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.

ConnectivityExpectationPhase transitionRandom graphThresholdComponentCoupon collectorFirst momentLabelled graph

All concepts