The moment everything joins up

Take $n$ points and decide each of the $\binom{n}{2}$ possible edges independently, each present with probability $p$. At $p = 0$ the result is dust; at $p = 1$ it is the complete graph. Somewhere in between it stops being in pieces and becomes one thing.

The interesting claim is that “somewhere in between” is much sharper than it sounds. As $n$ grows, the range of $p$ over which the graph is sometimes connected and sometimes not shrinks relative to the value of $p$ itself, so the change looks less like a gradual filling-in and more like a switch.

Everything in this essay is computed exactly. Nothing is sampled, nothing is estimated, and the drawn graphs later on are illustrations with their seed printed rather than evidence of anything.

Counting the connected graphs #

For up to six points every graph can be examined, which is 32,768 of them at $n = 6$. Sorting them by edge count and keeping the connected ones gives a polynomial:

$$P_n(p) = \sum_m c_{n,m}\, p^m (1-p)^{\binom{n}{2} - m},$$

where $c_{n,m}$ counts connected graphs on $n$ labelled points with $m$ edges. Evaluating that polynomial at any $p$ gives the exact probability.

The enumeration is easy to get wrong in a way that produces a plausible curve, so it is checked against a second computation that shares no code. Split every graph on $n$ points by the component containing point 1: if that component has $k$ points, there are $\binom{n-1}{k-1}$ ways to choose the rest of it, $c_k$ connected graphs on it, and $2^{\binom{n-k}{2}}$ arbitrary graphs on what is left. Summing over $k$ from 1 to $n-1$ and subtracting from $2^{\binom{n}{2}}$ gives $c_n$, the total count of connected graphs.

The recurrence and the enumeration agree at every $n$ up to six: 1, 1, 4, 38, 728, 26704. A bug in one would have to be matched by the same bug in the other, which is the standing reason this site computes things twice.

The curve is also checked for the one qualitative property it must have: it rises. Adding an edge to a connected graph leaves it connected, so the probability cannot fall as $p$ grows, and that is asserted at two hundred points along each curve.

What actually goes wrong #

A graph can fail to be connected in many ways — two large halves with nothing between them, a piece of three hanging off, a single point left out. The question is which of these is the obstacle in practice.

Being connected implies having no isolated point, so one curve is under the other everywhere; that much is forced. The content is that the gap is narrow, and that it narrows further as $n$ grows.

The reason is a comparison of counts. For a graph to fail because a single point is isolated costs $(1-p)^{n-1}$ per point, and there are $n$ points. For it to fail by splitting into a piece of size $k$ and a piece of size $n-k$ with $k \ge 2$ costs $(1-p)^{k(n-k)}$, and $k(n-k)$ is at least $2(n-2)$, which is nearly twice as large an exponent. At the relevant $p$ the second is negligible against the first.

So the question “when does the graph become connected?” reduces to “when does the last isolated point disappear?” — and that is a question with a clean answer.

Where the threshold is #

The expected number of isolated points is $n(1-p)^{n-1}$, which is a product of one factor growing and one shrinking. Setting it to 1 and taking logarithms gives $p \approx \ln n / n$.

That is the threshold, and its form deserves a moment. The number of edges at that $p$ is about $\binom{n}{2} \cdot \ln n / n \approx \tfrac{1}{2} n \ln n$ — so a random graph needs about $\tfrac{1}{2}n\ln n$ edges to be connected, against the $n - 1$ a tree needs. The factor of $\ln n$ is the price of not being allowed to choose where the edges go.

The $\ln n$ is the same $\ln n$ that appears in how long until every one turns up, and for the same reason: both are asking how long until the last of $n$ independent-ish waits finishes, and the last of $n$ waits is a factor of $\ln n$ longer than the typical one. A collector needs $n \ln n$ draws to see every coupon; a random graph needs $\tfrac12 n \ln n$ edges to give every point at least one. The threshold is a coupon-collector problem wearing a graph.

Erdős and Rényi proved the sharp form in 1959: writing $p = (\ln n + c)/n$, the probability of connectedness tends to $e^{-e^{-c}}$. So the transition happens over a window of width about $1/n$ around $\ln n / n$, which is a vanishing fraction of the threshold itself. That is what makes it a threshold rather than a trend.

What the small cases can and cannot say #

The exact curves stop at six points, which is where enumeration stops. Six points is not large, and the honest position is that these figures illustrate a phenomenon whose statement is asymptotic.

What they do establish is real. The curves genuinely steepen; the even-chance crossing genuinely tracks $\ln n / n$ from 0.50 down to 0.36 as $\ln n/n$ goes from 0.37 to 0.30; the gap between connectedness and no-isolated-point is genuinely small at every $p$ and every $n$ computed. Those are facts about the drawn cases.

What they cannot establish is the limit. Four data points of a sequence do not determine its behaviour, and a reader who concluded from the figure that the threshold is exactly where the curve crosses a half would be extrapolating from sizes at which the correction terms are as large as the leading one.

That distinction is worth being pedantic about. Three drawn graphs looking like dust, fragments and a single piece is an illustration of a claim proved elsewhere; run with a different seed they might have looked otherwise, and nothing in the drawing says how much otherwise.

The other threshold, which is different #

Connectivity is not the first thing that happens as $p$ rises, and the earlier event is more famous.

At $p$ around $1/n$ — much smaller than $\ln n / n$ — the graph acquires a giant component: a single piece containing a constant fraction of all the points, where before there were only pieces of size $O(\log n)$. The change is abrupt in the same technical sense, and it is the event usually meant by “the phase transition in random graphs”.

Between $1/n$ and $\ln n / n$ the graph is in an intermediate state that is easy to picture and easy to get wrong: one enormous piece, plus a scattering of isolated points and tiny fragments. It looks connected if the small pieces are overlooked. The second threshold is the moment those last stragglers are absorbed.

So there are two distinct events with different answers, and both are called phase transitions:

• $p \approx 1/n$: a giant piece appears. About $n/2$ edges.
• $p \approx \ln n / n$: the last isolated point vanishes and the graph becomes connected. About $\tfrac12 n \ln n$ edges.

The ratio between them is $\ln n$, which is small for any $n$ anybody draws and unbounded in the limit — a good example of an asymptotic separation that no picture can show.

Every property of this kind has a threshold #

Connectivity is not special. A graph property is monotone if adding edges never destroys it — being connected, containing a triangle, having a Hamiltonian cycle, having chromatic number at least 5. Bollobás and Thomason proved in 1987 that every monotone property has a threshold: a function $p^*(n)$ such that the property holds with probability tending to 0 below it and to 1 above it, whenever the ratio to $p^*$ tends to 0 or infinity.

That is a strong statement and it says nothing about where. Locating the threshold for a particular property is the work, and the answers are a catalogue rather than a formula:

• a triangle appears at $p \approx 1/n$;
• a giant component at $1/n$;
• every point has an edge, and the graph becomes connected, at $\ln n/n$;
• a Hamiltonian cycle at $\ln n/n$ as well — the same threshold as connectivity, which is a genuinely surprising coincidence and not one anybody guessed;
• a complete graph on four points at $n^{-2/3}$.

The pattern in most of them is the one this essay’s threshold follows: find the expected number of the smallest obstruction, set it to 1, and solve. For a triangle the expected count is $\binom{n}{3}p^3$, which passes 1 at $p \approx 1/n$; for an isolated point it is $n(1-p)^{n-1}$. The method is called the first moment method and it gives an upper bound honestly and a lower bound only with more work, because an expectation of 1 is consistent with the count being 0 nearly always and enormous occasionally.

The other half of the argument #

The first moment method gives one direction and the essay has been careful to say so. The other direction — that below the threshold the obstruction really is present, rather than merely expected — needs a second calculation, and the calculation is short enough to give.

The problem is that an expectation is not a probability. A count with mean $1{,}000$ could be $1{,}000$ almost always, or zero almost always with a rare enormous spike; the mean cannot tell the two apart, and only the second case leaves the graph connected. What separates them is the variance.

Write $X$ for the number of isolated points. Then $X$ is a sum of $n$ indicators, one per point, and

$$\operatorname{Var}(X) = \sum_i \operatorname{Var}(X_i) + \sum_{i \ne j} \operatorname{Cov}(X_i, X_j).$$

The individual variances are at most the individual means, so the first sum is at most $\mathbb{E}[X]$. The covariances are the interesting part: two points are both isolated when neither has any edge, which requires $2(n-2)+1$ specific edges to be absent rather than $2(n-1)$, so the joint probability slightly exceeds the product — the events are positively correlated, because the edge between the two points counts once instead of twice. The excess works out to a factor of $1/(1-p)$, which at $p \approx \ln n/n$ is $1$ plus a vanishing amount.

So the variance is $\mathbb{E}[X]$ plus a term that is a vanishing fraction of $\mathbb{E}[X]^2$, and Chebyshev’s inequality finishes it: the chance that $X$ is zero is at most $\operatorname{Var}(X)/\mathbb{E}[X]^2$, which tends to zero whenever $\mathbb{E}[X]$ tends to infinity. Below the threshold there really are isolated points, with probability tending to one, and the graph really is disconnected.

That completes the picture and it is worth naming the shape of it, because the pair of arguments is the standard tool for every threshold in the subject.

Above the threshold, the expected number of obstructions tends to zero, so the chance of even one is small — Markov’s inequality, and nothing else is needed.

Below the threshold, the expected number tends to infinity, which proves nothing on its own; the variance has to be shown small relative to the square of the mean, and then Chebyshev converts an expectation into a near-certainty.

The two together are the first and second moment methods, and the asymmetry between them is real. The upper bound is free and the lower bound is work, because many on average and many usually are different statements — and it is exactly that gap that makes the threshold a theorem rather than a heuristic.

The other use of the same object #

Random graphs began as a proof technique rather than as a subject, and the technique is worth stating because it explains why anybody was counting connected graphs in the first place.

To show that a graph with some property exists, put a probability distribution on graphs and show the property has positive probability. No graph is ever exhibited; the argument is entirely about counting, and the conclusion is existence.

The founding example is a lower bound for Ramsey numbers. Six people at a party shows that six points force a monochromatic triangle. How many points force a monochromatic complete graph on $k$ points? Erdős’s 1947 argument: colour the edges of the complete graph on $n$ points at random, and count the expected number of monochromatic complete subgraphs on $k$ points. It is $\binom{n}{k}2^{1-\binom{k}{2}}$, and if that is less than 1 then some colouring has none — so $n$ points do not force one. The bound this gives is exponential in $k$, it is essentially the best known eighty years later, and no explicit colouring achieving anything like it has ever been constructed.

That is the pattern the probabilistic method is famous for: it proves objects exist while remaining silent about what they look like. Nobody gets their own hat is a counting argument of the ordinary kind by contrast — it produces a number, and the number is about every permutation rather than about a lucky one.

Where the model came from, and what it is not #

Erdős and Rényi introduced the model in 1959, and Gilbert independently in the same year with the $p$-per-edge version used here; Erdős and Rényi’s own version fixes the number of edges rather than the probability, and the two agree for most purposes.

The motivation was not to model anything. Erdős had been using random constructions for a decade to prove that graphs with stated properties exist — the probabilistic method, which proves existence by showing the probability is positive and never exhibits the object. The random graph became a subject in its own right when it turned out that its properties appear in a strict order as $p$ rises, each at its own threshold, with the order itself being the theorem.

What this model is not is a model of any real network. Real networks have degree distributions nothing like the binomial one, and the fact was noticed loudly enough in the 1990s to launch a separate field. The value of the Erdős–Rényi graph is as a null object — the thing a network is compared against — and as the setting in which thresholds were first understood.

What the pictures cannot show #

The enumeration stops at six points because $2^{15}$ graphs can be examined and $2^{21}$ takes long enough to be a nuisance. Every exact statement here is therefore about $n \le 6$, and every asymptotic statement is quoted rather than computed.

The threshold $\ln n / n$ is marked on the isolated-point figure as a vertical line, and at $n = 6$ that line is at 0.299 while the connectivity curve crosses a half at 0.36. The two do not coincide and there is no reason they should: the threshold is where the expected number of isolated points passes 1, and expectation passing 1 is not the same as probability passing a half except in the limit.

And the drawn graphs use a circular layout, which makes every component look like a chord diagram rather than like a cluster. A drawing that placed connected points near each other would look far more like the intuitive picture of a graph coming together and would be a picture of the layout algorithm as much as of the graph.

The ladder from here #

Below: how long until every one turns up, where the same $\ln n$ appears for the same reason, and sixteen trees on four points, which counts labelled graphs of a particular shape. Sideways: the edge that forces a triangle, where the number of edges decides what a graph must contain rather than what it probably does; a bell curve assembled out of coin flips, the concentration that makes thresholds sharp; and how far from the average a thing can be, which is the tool that turns an expectation into a statement about what usually happens. Above: the giant component and its exact size, the second moment method, thresholds for containing a fixed subgraph, and the general theorem that every monotone graph property has one.

What is worth carrying away #

A property that a graph either has or does not appears, as the density rises, not gradually but at a place — and finding the place is usually a matter of finding the last obstacle rather than reasoning about the property directly.

For connectivity the last obstacle is a single point with no edges, which is a much simpler object than a disconnection. Once that is noticed, the threshold is an expectation calculation of two lines, and the hard work is only in showing that nothing else matters. The pattern generalises: a threshold is usually located by identifying the cheapest way for the property to fail, and confirmed by showing every other way is cheaper still to avoid.