Random graphs — the ladder
-
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.
-
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.
-
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.
-
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.
-
The window where the giant is born
Below the threshold the largest piece is a few dozen points, above it a definite fraction of everything. At the threshold it is neither, and the size it does take — the two-thirds power — is an exponent with no elementary derivation that a measurement finds immediately.
-
Sharp, or merely a threshold
Every monotone property of a random graph has a threshold. Some of them turn on over a range that shrinks relative to the threshold as the graph grows, and some do not — and which kind a property is turns out to be decided by whether it is about a local structure or about the whole graph.