The window where the giant is born

The rung about the giant locates the transition at average degree one and describes what happens on either side. Below it the largest piece has a few dozen points however large the graph; above it the largest piece holds a definite share of everything, and the share is the root of an equation.

Neither description applies at the threshold itself, and the question of what happens exactly there is not a detail. It is a third regime with a size of its own, and the size is a power nobody would guess.

Three regimes, not two #

Write the edge probability as $c/n$, so $c$ is the average degree. The three regimes are:

Subcritical, $c < 1$: the largest piece has about $\log n$ points, with a constant depending on $c$ that blows up as $c$ approaches one. The blowing-up is the first sign that the two outer descriptions do not meet: each is stated with a constant, and both constants become infinite at the threshold, so neither formula survives being taken there.

Supercritical, $c > 1$: the largest piece has about $\rho(c)\, n$ points, where $\rho$ is the survival probability of a branching process and is the root of $1 - \rho = e^{-c\rho}$.

Critical, $c = 1$: the largest piece has about $n^{2/3}$ points, and neither formula above gives that. The logarithm is far too small and the linear term is far too large.

The gap between the two is enormous and the critical value sits comfortably inside it. At a thousand points, $\log n$ is about 7 and $n$ is a thousand, while $n^{2/3}$ is a hundred — so the critical component is fourteen times the subcritical answer and a tenth of the supercritical one, which is exactly the sort of intermediate scale that neither of the two outer descriptions can produce. Two thresholds separated by a logarithm is the other place on this ladder where an intermediate scale decides the answer, and it is worth reading the two together.

Why two-thirds #

The exponent has a derivation and it is worth giving, because it explains why the answer is a power at all.

Explore the whole graph in one pass. Start anywhere, reveal that vertex’s neighbours, then the next vertex’s, and so on, keeping a running count of how many vertices are known and not yet explored. That count is a walk: each step reveals a number of new neighbours with mean one — since the average degree is one — and uses up one vertex.

The walk has no drift at first, so after $t$ steps it has wandered a distance of order $\sqrt{t}$. But the vertices get used up. After $t$ steps only $n - t$ remain available, so the expected number of new neighbours has fallen to $1 - t/n$, and the walk acquires a downward drift that accumulates to about $t^2/n$.

The exploration ends when the accumulated drift overwhelms the fluctuation, and the two are equal when

$$\sqrt{t} \;\approx\; \frac{t^2}{n},$$

which rearranges to $t \approx n^{2/3}$.

That is the whole derivation: a square-root fluctuation against a quadratic drift, and the exponent is where they cross. It also gives the window’s width for free — putting the average degree at $1 + \varepsilon$ adds a linear drift $\varepsilon t$, which matters when $\varepsilon t$ is comparable with $\sqrt{t}$ at $t = n^{2/3}$, so at $\varepsilon \approx n^{-1/3}$.

A square root against a square, and a linear term to say how far off-centre one is. Every critical exponent in the subject comes out of a balance of that kind, and the reason the exponents are universal is that the balance does not know what the objects were.

The two exponents together #

The pair $(2/3, 1/3)$ is what a physicist would call the critical exponents of the transition, and having both is what makes the description complete.

Rescale: divide the largest component by $n^{2/3}$ and measure the average degree by $(c-1)n^{1/3}$. Graphs of every size then collapse onto one curve. That collapse is the content of the scaling description, and it says that a graph of a thousand points and one of a million are the same picture at different magnifications, provided both are looked at through the right lens.

The measurement in the first figure is the collapse’s most basic consequence. If the largest component at the critical point were of order $\log n$, dividing by $n^{2/3}$ would give a ratio falling to zero; if it were of order $n$, the ratio would grow without bound. It does neither, and the three columns of the table are that statement performed.

Where the window sits, in numbers #

It helps to put the window on the same scale as the thing it is a window in.

At a thousand points the critical average degree is 1 and the window’s half-width is $n^{-1/3}$, which is a tenth. So the transition occupies average degrees from about 0.9 to about 1.1, and the largest component runs from a few dozen to a few hundred across that range.

At a million points the half-width is a hundredth: the window is average degrees 0.99 to 1.01, and the largest component at the centre is about ten thousand — one per cent of the graph. The window narrows and the critical component grows, both as powers, and the two powers are what the rescaling uses.

That is worth holding because it says how visible the phenomenon is. In a graph of a thousand, the window is a tenth of the parameter and easy to land in by accident. In a graph of a million it is a hundredth, so a simulation stepping the average degree in units of 0.05 will step straight over it and see a clean jump — which is exactly how the transition was described for its first thirty years.

A phenomenon whose width shrinks with the system size is invisible to any experiment that does not know to look for it, and the only way to see it is to rescale, which requires knowing the exponent first.

That is a circularity worth naming rather than glossing. The rescaling that makes the window visible needs $n^{-1/3}$, and the derivation that gives $n^{-1/3}$ needs the exploration walk, which is a piece of theory. A measurement can confirm the exponent and cannot find it from a coarse scan — because a coarse scan does not sample inside the window at all. The theory is what tells the experiment where to look, which is the ordinary relationship in this subject and is the opposite of the one the table at the top of this rung suggests.

What is inside the window #

The critical regime is not merely a size; it has a structure, and the structure is the reason the subject took thirty years after Erdős and Rényi to settle.

Inside the window there is no single largest component in any stable sense. There are many components of order $n^{2/3}$, their sizes fluctuate from one sample to another by a constant factor, and which one is largest changes with the seed. The ordered sequence of component sizes, all divided by $n^{2/3}$, converges to a random object — not to a number.

That is a genuinely different kind of answer from the ones on either side. Subcritically the largest component’s size is concentrated; supercritically it is concentrated; critically it is not, and no amount of increasing $n$ makes it so.

The exploration walk explains that too. Above the window the walk has a positive drift and one excursion runs away, taking a definite share of the graph — a single winner. Below it the drift is negative and every excursion dies quickly — many small pieces and no contest. Inside the window the drift is comparable with the fluctuation, so several excursions get comparably far and which is longest is decided by the noise. A lack of concentration is what a balance between drift and fluctuation looks like, and it is the same balance that fixed the exponent.

The consequence for anybody simulating this is worth stating: at the critical point, averaging over samples measures the mean of a genuinely spread-out quantity, and reporting the mean without the spread hides the phenomenon completely. Outside the window a concentration bound of the ordinary kind applies and the distance from the average is controlled; inside it, no such bound holds, and that failure is a theorem rather than a gap in the analysis.

Reading the table’s other columns #

The two columns the argument discards are worth a moment, because each is the right answer somewhere and neither is right here.

Dividing by $\log n$ gives 4.90, 6.13, 8.60 and 9.97 — a steady climb by a factor of two across the four sizes. That column would be flat if the critical component behaved like a subcritical one, and its climb is the statement that it does not: at the threshold the largest piece is very much bigger than the logarithm a subcritical graph would give.

Dividing by $n$ gives 0.226, 0.163, 0.129 and 0.083 — a steady fall, by a factor of nearly three. That column would be flat if the critical component held a fixed share, and its fall says the share is going to zero: at the threshold there is no giant, however large the graph.

Between a column that climbs and a column that falls there is an exponent that does neither, and the middle column is it. That is the whole of the reasoning, and it is worth noticing that it needs no theory at all — three divisions and four rows.

The same reasoning is how exponents are found in practice, in settings where no derivation is available. Guess a scaling, divide, look at whether the ratio drifts, and adjust. It is crude and it converges, and its weakness is exactly the one the last section names: it locates the exponent within a wide band and never pins it.

A refinement worth knowing: instead of trying candidate exponents one at a time, fit a straight line to the logarithm of the component size against the logarithm of $n$, and read the exponent off the slope. On the four rows here the slope comes out near two-thirds, and the fit’s uncertainty is the same uncertainty the columns show — the method is more elegant and no more precise, because the limitation is in the data rather than in the arithmetic done to it.

Why the exponent is universal #

The two-thirds power is not a fact about random graphs alone, which is the reason it is called an exponent rather than a constant.

The same power appears in the critical behaviour of percolation on many structures, in the sizes of blocks in certain random partitions, and in the multiplicative coalescent — the process in which clusters merge at a rate proportional to the product of their sizes, which is what adding random edges to a graph does. The random graph’s window is one instance of a phenomenon with several appearances.

The link to percolation is the most useful of these, because it is where the language comes from. Percolation asks whether water poured on a lattice reaches the bottom, as a function of how many bonds are open, and it has the same three regimes with the same kind of window. The random graph is percolation on the complete graph — every pair a potential bond — and it is the case where the exponents can be computed, which is why it is the one everybody learns first. The threshold at which a structure appears is the same object in both.

There is a second reason the class is wide, visible in the derivation. Nothing in the balance between $\sqrt{t}$ and $t^2/n$ mentions graphs; it mentions a process whose fluctuation is a square root and whose resource depletes linearly. Any model with those two features has the same exponent, and a great many do — which is what makes universality a statement about arithmetic rather than about the models.

Universality is why an exponent is worth measuring rather than merely deriving. A constant depends on the details of a model; an exponent tends not to, so a measurement of $2/3$ in one setting is evidence about every setting in the same class — and knowing that a model is in the class is often easier than solving it.

What a measurement of an exponent is worth #

The table’s ratios are 1.05, 0.95, 0.95 and 0.77 across sizes doubling from a hundred to eight hundred, which is not flat and is far flatter than either alternative.

That is worth being honest about. A measurement over a range of eight in $n$ can distinguish an exponent of $2/3$ from exponents of $0$ and $1$ comfortably, and cannot distinguish it from $0.6$ or $0.7$. The figure establishes the regime and not the exponent’s exact value.

To distinguish $2/3$ from $0.7$ by measurement alone would need the ratio’s drift to be resolved against the sampling noise, and the noise here is substantial — the critical component’s size fluctuates by a constant factor between samples, which is the very phenomenon the section above describes. So the measurement’s precision is limited by the thing being measured, and no amount of averaging removes it: averaging twelve samples reduces the error in the mean, and the mean is not what a single graph does.

Establishing the exact value takes the derivation above, or the much harder work of proving the scaling limit exists. A measurement of this kind rules out the wrong answers and confirms the right one; it does not find it, and reading it as though it did is the standard error with numerical work on exponents. The same caution applies to every counting argument that establishes existence without producing an object — a colouring nobody has ever seen is the extreme case, where the proof gives a number and no example at all.

What the pictures cannot show #

The measurement runs to eight hundred points, which is where an exhaustive component search over every pair of vertices stays inside a figure’s budget. The asymptotic statements are about $n$ going to infinity.

The scaling collapse is described and not drawn. Drawing it would need graphs at several sizes measured across the whole window, which is a few thousand samples and a plot with the axes rescaled — a good figure, and a slow one.

And the limiting random object — the sequence of rescaled component sizes — is a genuine mathematical object with a description, and no finite sample exhibits it. What a sample shows is that the sizes fluctuate, which is consistent with a random limit and is not evidence for any particular one.

Where the ladder goes next #

Named here as debts. The scaling limit itself, which identifies the limiting object and is the deepest result on this ladder. And the same window for other structures, where the universality claim above would be measured rather than asserted.

Sideways, the giant this is the birth of is the rung below, the second threshold it is not is the rung below that, the counting method that locates thresholds in general is the two-moment argument, and the branching process the derivation runs on is a random walk with no drift.

What is worth carrying away #

A threshold is a window, and the width of the window is a second quantity with its own exponent.

Treating the transition as a point gives two regimes and a boundary. Treating it as a window of width $n^{-1/3}$ gives a third regime, of size $n^{2/3}$, in which neither of the outer descriptions holds and the answer is random rather than concentrated.

The habit worth taking is to ask what happens exactly at a threshold. The behaviour on either side is usually the easy part and usually does not extend to the boundary, and the boundary’s own behaviour is where the exponents are.

The corollary is about measurement. Three candidate scalings and four sizes settled which regime the critical point is in, in a table anybody can read, and the same table is powerless to distinguish two-thirds from seven-tenths. Knowing which question a measurement can answer is most of the value of making one, and a measurement that rules out the alternatives has done its job even when it cannot pin the answer.