Two thresholds, not one

The previous rung locates the moment a random graph acquires a giant component: average degree one. It is easy to read that as the moment the graph “joins up”, and it is not.

At average degree two the giant holds about eighty per cent of the points, at three about ninety-four, and at neither is the graph connected. The share missing shrinks exponentially and never reaches zero, and connectivity requires it to — which is the difference between a statement about a proportion and a statement about every member, and the whole of this rung.

The last obstruction #

What stops a graph with a ninety-four per cent giant from being connected is not a second large piece — the previous rung’s duality rules that out. It is the small pieces, and overwhelmingly the smallest possible: single points with no edges at all.

The expected number of them is easy. A given point is isolated when all $n-1$ of its possible edges are absent, which has probability $(1-p)^{n-1}$. With $p = c/n$ that is approximately $e^{-c}$, so the expected count is

$$n \, e^{-c}.$$

That is the whole calculation, and everything follows from setting it against one.

At $c = 3$ and $n = 1000$ the expected count is about fifty — fifty isolated points, and a graph with even one is not connected. To bring the expectation below one requires $e^{-c} < 1/n$, that is $c > \log n$, which at a thousand points is about seven.

So the connectivity threshold is at $c = \log n$, seven times further along than the giant’s, and the two thresholds are not close. At a million points the factor is fourteen; at a billion, twenty-one. The gap grows without limit, which is the sharpest statement of how different the two properties are: no fixed amount of extra connectivity ever suffices, because the requirement grows with the size and the giant’s does not.

Why the expectation is enough #

Turning an expected count into a probability needs two arguments, one easy and one less so, and they are the standard pair.

If the expectation is small, the probability is small. That is Markov’s inequality: a non-negative count with expectation $\mu$ is at least one with probability at most $\mu$. So above $c = \log n + \omega$ for any growing $\omega$, the chance of an isolated point tends to zero.

If the expectation is large, the probability is large — but only with a second-moment argument, because a large expectation is compatible with the count being zero almost always and enormous occasionally. A lottery has a large expected payout and pays nothing almost always. Here the isolated points are nearly independent, the variance is close to the mean, and Chebyshev’s inequality gives what is wanted: the count is within a constant factor of its mean with probability tending to one, so a mean above one forces a positive count.

Both directions are needed and only the first is free. The pattern — first moment for the upper bound, second moment for the lower — is the standard method for locating a threshold, and it works here because the events are nearly independent.

There is one further step. Ruling out isolated points does not by itself give connectivity: a graph could split into two large pieces without any isolated point. That it does not is the substantive part of the theorem, and it is proved by counting the ways a graph can split — the expected number of splits into pieces of size $k$ and $n-k$ is small for every $k$ once $c$ exceeds $\log n$.

The count is worth a sentence because it is where the argument could have failed. There are $\binom{n}{k}$ ways to choose the smaller side, and each requires all $k(n-k)$ edges between the sides to be absent, with probability $(1-p)^{k(n-k)}$. Multiplying and summing over $k$ from one to $n/2$, the terms are largest at $k = 1$ — which is the isolated points — and fall away rapidly. The binding case is the smallest one, and that is why the isolated points decide the threshold.

So isolated points are the binding obstruction rather than the only conceivable one, which is why the threshold is exactly where they vanish.

The coupon collector, arriving again #

The appearance of a logarithm should be recognised, because it is the same logarithm as in a much more familiar problem.

Collecting $n$ kinds of coupon, one at a time uniformly at random, takes about $n \log n$ draws to get them all — the coupon collector’s answer — and the reason is that the last few kinds are individually unlikely and there are many of them. The expected number of kinds still missing after $m$ draws is $n(1-1/n)^m \approx ne^{-m/n}$, which reaches one at $m = n\log n$.

That is the same expression with the same reasoning. A random graph’s isolated points are the coupons not yet collected; each edge is a draw that covers two of them; and the threshold is where the expected number missing reaches one.

The general principle is worth stating: a threshold at $\log n$ is a signature of “the last of many independent rare events”, and wherever it appears the underlying calculation is $n$ times a small probability set against one.

That also explains the sharpness. The number of isolated points near the threshold is approximately Poisson, so the probability of connectivity is approximately $e^{-\mu}$ where $\mu$ is the expected count — a smooth function of $c$ that moves from nearly zero to nearly one over a range of $c$ of order one around the threshold, which is a vanishing fraction of $\log n$. The transition is sharp relative to where it happens, which is the sense in which every threshold in this subject is sharp.

The Poisson approximation there is worth trusting for a specific reason: isolated points are a collection of rare, nearly independent events, and a count of such events is Poisson by the standard limit. That gives more than a threshold — it gives the whole curve, $\exp(-ne^{-c})$, which is the shape the connectivity measurement traces.

Reading the two measurements together is the rung in one gesture. At average degree three, ninety-four per cent of the points are in one piece and the probability of connectivity is essentially nought. Both statements are about the same graphs and both are correct, and anybody who had only the first would conclude the graph was connected.

That is a general hazard of summary statistics. “The largest component holds most of the graph” is a fact about the bulk and says nothing about the tail, and connectivity is entirely a fact about the tail.

The hitting-time version, which is the sharpest statement #

There is a way of stating the result that is stronger than either threshold and is the reason this is one of the prettiest theorems in the subject.

Add edges one at a time in a uniformly random order and watch two moments: the moment the last isolated point acquires an edge, and the moment the graph becomes connected.

They are the same moment, with probability tending to one.

That is Bollobás and Thomason’s hitting-time theorem, and it says the obstruction is not merely the binding one asymptotically — it is the only one, in the strongest sense. The graph is disconnected because of an isolated point, right up to the instant it is not.

Its proof is the counting argument above sharpened: every other way of being disconnected has expected count tending to zero at the moment the last isolated point disappears, so nothing else can be responsible.

Stating it as a coupling of two moments rather than as a coincidence of two thresholds is worth the effort because the two are genuinely different claims. Two thresholds coinciding says the probabilities cross at the same place; two hitting times coinciding says that in almost every single realisation, the same edge does both jobs. The second implies the first and the first does not imply the second, and results of the stronger kind are what a subject produces once it understands its objects rather than only their statistics.

A result of that form is worth recognising as a type. It replaces “these two thresholds coincide” with “these two events coincide”, which is a statement about a single random object rather than about two probabilities, and it is much stronger.

Checking the formula at five points and applying it at a thousand is the ordinary relationship between an exact small case and an asymptotic argument, and it is worth being clear about which part is being checked. The expectation $n(1-p)^{n-1}$ is exact at every size — it is a sum over points of a probability, and expectations add whatever the dependence. What is asymptotic is the approximation of that by $ne^{-c}$, and the deduction from the expectation to the probability.

The expectation is exact and its consequences are asymptotic, which is the usual division of labour in a first-moment argument.

Where the gap matters #

The distance between the two thresholds is not a curiosity; it is the reason several practical questions have the answers they do.

A network can be well connected and unreliable. A communication network at average degree three has almost everything in one piece and a scattering of unreachable nodes. Designing for “most of the network works” and designing for “every node is reachable” are different problems with different costs, and the ratio between them is $\log n$.

Redundancy is cheap in the middle and expensive at the end. Going from average degree one to three takes the giant from nothing to ninety-four per cent; going from three to seven buys the last six per cent and connectivity. In edge counts that is a doubling of the network’s cost to gain the last sliver, and at larger sizes the ratio is worse. Most of the cost is spent on the last few points, which is a general feature of coverage problems and is why guarantees of the form “every one” are so much more expensive than “almost all”.

A guarantee of connectivity has to be paid for in the worst place. The nodes that are hard to connect are the ones with few opportunities, and adding edges uniformly is the least efficient way to reach them. Any design that can direct its edges — connect the isolated nodes deliberately — beats the random model by the whole factor of $\log n$, which is the practical reason real networks are not built at random.

And random graphs are a poor model where the last points matter. Real networks have degree distributions with heavy tails, so isolated points are much rarer than the random model predicts, and the connectivity threshold in a heavy-tailed network is much earlier. Using the random model to price reliability would be pessimistic by a large factor.

The same shape in three other places #

A threshold at $\log n$ produced by “the last of many rare events” is common enough to be worth recognising on sight.

Covering a set by random subsets. Throwing random subsets of a given density at an $n$-element set until every element is covered takes $\log n$ times as many as coverage of a constant fraction does, for the identical reason: the last elements are individually unlikely and there are many of them.

Every bin occupied. Throwing balls into $n$ bins until none is empty takes $n\log n$ balls, which is the coupon collector exactly. The related question of the fullest bin has a different and stranger answer, of order $\log n / \log\log n$, which is the same calculation run at the other tail.

And the birthday problem, inverted. The famous version asks when a collision becomes likely, which happens at $\sqrt{n}$ draws; asking when every value has been seen is the coupon collector at $n\log n$. The same $n$ objects give a threshold at the square root for one question and at $n \log n$ for another, and the gap between them is the difference between a first collision and a last omission.

The unifying calculation is the same throughout: set $n$ times a small probability against one, and the threshold is where the small probability is $1/n$. Whenever that is the structure, a logarithm appears and the interesting behaviour is entirely at the tail.

What the pictures cannot show #

Four hundred points is a small graph, and the two thresholds are close there for exactly that reason. The two thresholds are at one and about six, so the gap is a factor of six; at a million points it is a factor of fourteen; and the statement being illustrated is that the ratio grows without limit. A figure at any single size shows a gap and not a growing one.

The connectivity curve is a probability estimated from samples. Each point is a proportion over a handful of graphs, so the curve is noisy where it is steep — which is precisely where it matters. The count of isolated points is the smoother and more informative quantity, and the figure checks it against $ne^{-c}$ at every value where the approximation applies, which is a stronger statement than the connectivity curve makes.

The isolated-point count is exact and the connectivity is sampled, and the two are drawn at different sizes. That is deliberate — the count is smooth and the probability is noisy — and it means the two figures cannot be laid over each other, so the claim that the count reaching zero is what makes the graph connected has to be taken from the prose.

And the hitting-time theorem has no figure at all. It is a statement about two random moments in a single evolving graph being equal, which would need a picture of one graph over time with two marked instants, and the instants coincide — so the picture would show one mark and would not display that it is two.

Where the ladder goes next #

The next rung asks the general question these two thresholds are instances of: given any property, where is its threshold, and how is one found? The method is two moments, and the triangle is the example on which it is cleanest.

Named here as debts. The hitting-time theorem’s proof, described above and not given. And the connectivity of random graphs with prescribed degrees, which is the model that fits real networks and where the isolated-point calculation is replaced by a different one.

Sideways, the logarithm is the coupon collector’s, the concentration that turns an expectation into a probability is the deviation bound, the giant whose appearance is the earlier threshold is the previous rung’s, and the original observation is the anchor’s first.

Sideways: how long until every one turns up is the coupon-collector count this threshold is built from, and more things than boxes is the counting principle underneath the first-moment half of the argument.

What is worth carrying away #

Two properties that seem to be the same property can have thresholds a factor of $\log n$ apart, and the gap is where the interesting engineering lives.

“Mostly joined up” happens at average degree one and “entirely joined up” at $\log n$, and in between sits a graph that is ninety-something per cent one piece with a dust of isolated points. Nothing about the informal description distinguishes the two, and the calculation that separates them is one line: the expected number of isolated points is $ne^{-c}$.

The habit worth taking is to ask what the last obstruction is. A property holding for almost everything and a property holding for everything differ by whatever is hardest to include, and identifying that thing usually gives the threshold immediately.

The same reading applies well beyond this graph model. Whenever a system is described as working almost everywhere, the question worth asking is what the last few failures have in common; the answer is usually a single small structure, and its expected count is the threshold. Isolated points here, uncovered cells elsewhere — the arithmetic is the same and so is the conclusion.