The moment a giant appears

The anchor’s first rung watches a random graph change as the chance of an edge rises: scattered pairs, then small trees, then suddenly a piece holding most of the points. That is an observation, and the natural questions are where the change happens and how big the piece is.

Both have exact answers, and the second is more surprising than the first.

Following a component out from a point #

The argument that locates the threshold is not about graphs at all. It is about a branching process, and the translation is what makes it work.

Start at a point and look at its neighbours. In a graph of $n$ points with edge chance $p$, a point has about $c = np$ neighbours on average. Each of those has about $c$ neighbours of its own, of which one is where it came from and the rest are new — provided the graph is large enough that repetition is unlikely.

So exploring a component is a branching process with mean offspring $c$, at least while the explored set is small compared with $n$.

The qualification is the whole content of the approximation and is worth stating twice. Once the exploration has reached a constant fraction of the graph, a new neighbour is likely to be somebody already found, so the offspring count falls and the process is not branching any more. That is exactly what stops the giant from swallowing everything, and it is why the equation for its size has a fixed point rather than running away.

The classical fact about a branching process is exactly what is needed. With mean offspring below one it dies out with probability one; with mean above one it survives with positive probability; and at exactly one it dies out, though the time it takes has infinite expectation.

Therefore the threshold is at $c = 1$, which is $p = 1/n$: below it every component is small, above it a point has a positive chance of being in an unbounded one. One neighbour on average is the dividing line, and the reason is that a process replacing each individual with one on average neither grows nor shrinks, and a process that neither grows nor shrinks eventually hits zero and stops.

The size of the giant #

The branching argument gives more than the threshold. It gives the size.

Let $x$ be the chance that a point’s exploration survives — that it lands in the giant component. A point fails to be in the giant exactly when none of its neighbours drags it in, and its neighbour count is roughly Poisson with mean $c$, each neighbour independently failing with probability $1-x$. So

$$1 - x = e^{-cx},$$

which is the extinction equation for a Poisson branching process.

And $x$ is then the share of the whole graph in the giant, because a share of the points is in it and the law of large numbers makes the observed share match the probability.

The equation has $x = 0$ as a root always. For $c \le 1$ that is the only root in $[0,1)$; for $c > 1$ there is a second, positive root, and it is the one that matters. The hero figure solves it numerically and compares against measurement.

Some values are worth having. At $c = 1.5$ the giant holds about $58\%$ of the points; at $c = 2$, about $80\%$; at $c = 3$, about $94\%$. The transition is sharp and the approach to everything is slow, which is the shape of the curve.

The slowness has a clean form. For large $c$ the share missing is $1 - x \approx e^{-c}$, so the leftovers shrink exponentially in the average degree — doubling the degree squares the share left out. That is fast in one sense and slow in another: it never reaches everything, and never reaching everything is exactly what the next rung is about.

Comparing the exact small case with the asymptotic argument is worth doing once, because it shows what the branching approximation is and is not. At four or five points there is no threshold to see: every probability is a polynomial in the edge chance and everything varies smoothly. The threshold is a feature of the limit, produced by many small smooth dependences accumulating, and it is genuinely absent at any fixed small size.

A phase transition is a property of a sequence of systems rather than of any one of them, which is the standard situation in this part of probability and is why the subject’s statements are all asymptotic.

Why the transition is sharp #

A share that is zero below a threshold and positive above it is a phase transition, and the sharpness is worth accounting for rather than accepting.

The branching argument is about the limit of large $n$. For a finite graph nothing is exactly zero: below the threshold the largest component is of size about $\log n$, which is a vanishing share and is not nothing. Above it the largest is of size $xn$, a constant share. At exactly $c = 1$ the largest is of order $n^{2/3}$ — bigger than a logarithm and smaller than a fraction — which is the critical window, and it is a subject of its own.

So the transition is sharp in the share and not in the count, and the three regimes for the largest component’s size are $\log n$, $n^{2/3}$ and a constant times $n$. Erdős and Rényi found the first and third in 1960; the middle one was worked out much later, by Bollobás and others, and it is where the interesting probability lives.

The window has a width. The transition happens over a range of $c$ of order $n^{-1/3}$ around one, so for a graph of a million points it is a range of a hundredth of a per cent — which is why it looks instantaneous at any size a picture shows.

What the second root means #

The equation $1 - x = e^{-cx}$ having two roots for $c > 1$ is worth dwelling on, because the two roots are two genuinely different things.

The root $x = 0$ says the exploration dies out. That is possible for any point, whatever $c$ is — a point with no edges at all has probability $e^{-c}$ and is not rare.

The positive root says the exploration survives. Both are correct statements about a random point, and the probabilities add to one: a point is either in the giant or in a small component, with probabilities $x$ and $1-x$.

So the “two roots” are not an ambiguity; they are the two outcomes, and the graph splits into a giant of share $x$ and a scattering of small pieces holding the rest.

The small pieces are worth knowing about. Above the threshold, the graph outside the giant is itself a random graph with a smaller average degree — the dual branch — and that smaller degree is below one. So the leftovers behave exactly like a subcritical random graph, which is the duality principle and is one of the tidiest facts in the subject.

The dual degree is $c(1-x)$, and it is below one whenever $c$ is above one, which is a small piece of algebra with a large consequence: the graph outside the giant never contains a second giant, and the uniqueness this rung records as unproved is a corollary of the duality once the duality itself is established. That is the usual shape of these arguments — the hard part is making the heuristic exact, and once it is, several results fall out together.

Where else the same transition appears #

The argument uses almost nothing about graphs, so it recurs.

Percolation. Open each edge of a lattice with probability $p$ and ask whether an infinite connected cluster appears. The same branching heuristic locates a threshold; the difference is that a lattice’s geometry makes the exploration revisit itself, so the threshold is not exactly at mean offspring one and is generally not known exactly. Two-dimensional bond percolation on the square lattice has threshold exactly a half, proved by Kesten in 1980, and that is a hard theorem resting on a self-duality of the lattice rather than on any branching computation. In three dimensions the threshold is not known in closed form and is a number obtained by simulation.

Epidemics. The branching parameter is the reproduction number, the threshold at one is why epidemics either die out or grow, and the final size of an epidemic solves the same fixed-point equation. The equation in this rung is the final-size equation of epidemiology, and the giant component is the set of people eventually infected — which is why the fraction infected in a large outbreak is a definite number rather than everybody, and why that number depends on the reproduction number in exactly the way the curve shows.

And nuclear chain reactions, where the mean offspring is the number of neutrons a fission produces that go on to cause another, and criticality is the same threshold — with the practical difference that the system is engineered to sit at it rather than to be on one side.

The commonality is not superficial. All four are the question does a branching process survive, and the answer is decided by one number in all four.

The history, and what was actually proved #

Erdős and Rényi’s 1960 paper is one of the founding documents of the subject and its result is narrower than the modern statement.

They studied the model with a fixed number of edges rather than a fixed edge probability — $m$ edges chosen uniformly among the possible ones — which is nearly equivalent and is the reason the model carries both names. Their theorem identifies the threshold at $m = n/2$, which is average degree one, and establishes the three regimes: components of size $\log n$ below, a component of linear size above, and something in between at the threshold.

What they did not do is compute the giant’s size, which follows from the branching argument and was made rigorous later. The branching heuristic itself is much older — Galton and Watson set it up in 1874, to study the extinction of surnames, and got the criterion right and the conclusion at the threshold wrong, concluding that a critical process survives when it does not.

That error is worth recording. At mean offspring exactly one the process dies out with probability one, and the equation $1 - x = e^{-x}$ has $x=0$ as its only root in $[0,1)$ — which is not obvious, since the process has no drift and looks as though it ought to survive. The critical case is where every branching argument is delicate, and it is where the critical window comes from.

What it costs #

The branching approximation needs the graph to be large and sparse. Exploring a component in a small graph revisits points, so the offspring count is not independent and the process is not a branching process. The figures measure at nine hundred points, where the approximation is good and the finite-size effects are still visible.

And the equation gives the limit, not the fluctuation. The share of the giant in a finite graph is a random quantity, close to $x$ but not equal to it. How close is a further theorem — the fluctuation is of order $n^{-1/2}$, so it is small, and knowing that is a separate calculation.

The Poisson approximation is doing quiet work. The offspring count in the branching process is binomial, and treating it as Poisson is a limit that needs $n$ large and $p$ small with their product fixed. That is the sparse regime, which is where the whole theory lives; at a fixed edge probability the graph is dense, everything is connected, and none of these questions arises.

Nor does it say the giant is unique. It is, above the threshold, and that is a real theorem: there is one component of linear size and the second largest is logarithmic. The branching argument gives the probability of being in a large component and does not by itself rule out two.

The isolated points are worth following because they are the cleanest instance of the duality just described. Above the threshold the graph outside the giant is a subcritical random graph, and in a subcritical random graph most components are single points: the expected number of isolated points is $n(1-p)^{n-1} \approx ne^{-c}$, which at average degree three on a thousand points is about fifty.

Fifty isolated points and a giant holding ninety-four per cent is a perfectly ordinary state for a random graph, and it is the state the next rung is about — because a graph with an isolated point is not connected, however large its giant.

What the pictures cannot show #

The threshold is a limit and the graphs are finite. Every measured point carries a finite-size error, which is largest exactly at the threshold, and the figure shows the disagreement there rather than concealing it. The theorem is about $n$ tending to infinity, which no measurement reaches.

A component is measured and not drawn. At nine hundred points the largest component is a fact about a computation, and no arrangement of nine hundred dots on a page would let a reader check it. The small drawn graphs show the phenomenon and are far below the size at which the theory applies.

The measurement averages over four samples per point. Four is enough to show the curve and is not enough to bound the fluctuation, which is what a serious estimate would require. The figure’s claim is that the measured share matches the prediction to within six per cent, which it checks, and not that the sampling error is small.

And the equation is solved numerically. The root of $1-x = e^{-cx}$ has no closed form in terms of elementary functions — it involves the Lambert function — so the curve is a bisection at every plotted value, and the assertion that it solves the equation is checked at three points rather than displayed.

Where the ladder goes next #

The next rung asks the obvious follow-up: the giant appears at average degree one, so is the graph connected then? It is not, and connectivity has its own and much later threshold.

Named here as debts. The critical window, of width $n^{-1/3}$, where the largest component is of order $n^{2/3}$ and the behaviour is neither of the two regimes. And the uniqueness of the giant, stated above and not argued.

Also unwritten: the exploration process made precise, in which the component is uncovered one vertex at a time and the number of uncovered-but-unexplored vertices is a random walk. That reformulation is what makes every statement above provable rather than heuristic, and it is where the walk that comes home enters the subject properly.

Sideways, the branching process whose survival decides everything is a random walk conditioned to stay positive, the concentration that makes a share of points match a probability is the law of large numbers with a rate, and the observation this rung explains is the anchor’s first.

Sideways: finding a threshold with two moments is the general instrument for locating a transition like this one, and the walk that becomes a curve is the same kind of scaling limit in one dimension.

What is worth carrying away #

A threshold with a sharp transition is usually a branching process in disguise, and the number that decides it is a mean.

Exploring a component is a branching process; a branching process survives exactly when its mean offspring exceeds one; therefore a giant appears exactly when the average degree exceeds one. The size of the giant is then the survival probability, which solves an equation with a Poisson in it because the offspring count is Poisson.

The habit worth taking is to ask what is branching. Whenever a system has a sharp threshold, something in it reproduces, and finding the reproducing thing gives the threshold, the size above it, and — through the same equation — the behaviour of what is left over.