Connectivity
Named by 5 essays across 3 fields — each of them below, with the objects they name alongside it.
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.
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.
The distance a sentence can see
A first-order sentence with three quantifiers cannot notice anything about a graph beyond a fixed distance from the points it names. That single limitation is why it cannot say connected, and why the failure survives every attempt to add more quantifiers.
The piece that cannot pair off
Take the sides away and the obstruction to a matching changes character completely. It is no longer a shortage of partners; it is a parity, and the quantity that measures it counts pieces of odd size rather than vertices of any size.
Every point at the average of its neighbours
A planar graph can be drawn without crossings, but finding such a drawing looks like a search. Tutte found in 1963 that it is not: pin one face to a convex polygon, put every other point at the average of its neighbours, and the drawing that results has straight edges, convex faces and no crossings at all — provided no two points can cut the graph apart. It is the position a network of equal springs settles into, and it is also where a random walk expects to leave.
Named alongside it
The objects these essays reach for when they reach for this one.
Existence proofExpectationIsolated vertexPhase transitionRandom graphThresholdComponentConvexityCounting argumentCoupon collectorDeficiencyElementary equivalence