Nearly always, or nearly never

Build a graph by tossing a fair coin for each pair of points: heads, an edge; tails, none. Then ask a question about the result — does it contain a triangle, is some point joined to nothing, does every pair of points have a common neighbour — and the answer is a probability, a number between zero and one that depends on how many points there are.

Let the number of points grow, and watch the probability. For some questions it settles on a number in the middle. For others it runs to an end and stays there. The first rung’s game decides which questions do which, and the answer is startlingly clean: if the question can be put as a first-order sentence about the graph, the probability runs to zero or to one. There is no first-order question whose answer is probably.

The last of those four is the whole point of the figure. Its share does not settle on zero or on one, because it is exactly a half at every size and not merely near one. So by the law, no first-order sentence says the number of edges is even — a statement about every sentence in an infinite language, established by a plot with four lines on it and a bijection anyone can verify.

The three first-order curves are worth reading individually, because they leave the middle in different directions and at different speeds. Some point is joined to nothing holds in about a third of graphs on four points and in none of the sampled graphs by fourteen: an isolated point needs every one of the other coin tosses to come up tails, and that becomes hopeless quickly. Some three points are all joined runs the other way, from about a third at four points to all but one of the sampled graphs by eight, because the number of candidate triples grows as the cube while the chance that a given one fails stays fixed. Every pair has a common neighbour is the slowest of the three, still holding in under a quarter of graphs at fourteen points, in three fifths at twenty-two, and in almost all of them at thirty-four — and it is the slow one because it is a demand about every pair at once rather than about the existence of a single configuration somewhere. A property asking for one thing to exist is settled by the first candidate that works; a property asking something of every pair has to survive all of them.

What the law says, precisely #

For each property $P$ and each number of points $m$, let $\mu_m(P)$ be the share of graphs on $m$ labelled points having $P$, where every one of the $2^{\binom{m}{2}}$ graphs is equally likely. That is the same thing as the coin-tossing description, and it is easier to count with.

The zero-one law. If $P$ is expressible by a first-order sentence in the language with one relation for adjacency, then $\mu_m(P)$ converges, and its limit is $0$ or $1$.

Three things about the statement are worth pinning down before the proof.

It is about the limit, not about any particular size. At six points the share having a triangle is around a third; the law says nothing about that number, only that the sequence goes to one.

It is about first-order sentences: finitely many quantifiers over points, adjacency, equality, and the usual connectives. Not about properties defined by counting, or by limits, or by quantifying over sets of points.

And it is not a claim that every property behaves this way. Parity of the edge count is a perfectly good property with limit one half, and connectivity thresholds in the sparser random graphs produce limits at every value between zero and one as the edge probability is tuned. The law is a statement about a language, and its content is exactly the properties it excludes.

The strategy needs a supply of witnesses #

The proof is the game from the first rung, and the whole of the work is finding the Duplicator a strategy that works between two random graphs.

Consider what Duplicator needs. Spoiler points at a point in one graph; Duplicator must answer in the other with a point that stands in the same relation to everything chosen so far. After a few rounds the chosen points impose a demand of the form: find a point joined to these and not joined to those. If such a point can always be found, Duplicator never runs out of answers.

That family of demands is called the extension property, and the figure measures the simplest case of it. The measured curve and the predicted one are computed by routes that share nothing: one samples graphs and tests every ordered pair, the other counts the expected number of pairs with no witness and turns it into a probability by treating the failures as independent. They agree, which is the check worth having, since the argument below is entirely about the rate at which this property arrives.

The rate is what makes the theorem work. A specific pair of points has no witness only if every one of the other $m - 2$ points fails to be one, and each fails with probability $3/4$ — it must either miss the first point or hit the second. So the expected number of failed pairs is about $m^2 (3/4)^m$, and that goes to zero, fast. Squares grow polynomially and three-quarters to the power of $m$ shrinks geometrically, and geometric beats polynomial.

The property the strategy actually needs is the version for sets rather than for single points: for every pair of disjoint sets of at most $k - 1$ points, some further point is joined to all of the first set and none of the second. A game of $k$ rounds never asks for more than that, because after $j$ moves the points already chosen number $j$, and the demand Duplicator faces is exactly to extend a set of that size. So one family of statements, indexed by the size of the sets, supplies every answer the strategy will ever need.

Each level of the family arrives later than the last, and the arithmetic says how much later. For sets of total size $s$ the chance that a given point fails to be a witness is $1 - 2^{-s}$, so a specific demand goes unmet with probability $(1 - 2^{-s})^{m - s}$, and the number of demands is about $m^{s}$. The product still goes to zero — the exponential in $m$ beats the polynomial for every fixed $s$ — but the size at which it does so climbs with $s$. That climb is the same one the games below display, and it is the reason the theorem cannot be stated at any fixed number of points.

Two random graphs, and a game neither loses #

Now put two independent random graphs side by side and play.

The figure is the mechanism of the proof rather than an illustration of it. Duplicator’s strategy is: answer each move with a witness supplied by the extension property. If both graphs have the property for sets up to the size the game will reach, the strategy never fails, and Duplicator survives all $k$ rounds. Two graphs on which Duplicator survives $k$ rounds agree on every sentence of quantifier depth $k$.

So fix a sentence $\varphi$ of depth $k$. From some size upwards, almost every pair of random graphs is $k$-equivalent, and therefore almost every pair agrees about $\varphi$. A property that almost every graph agrees with almost every other graph about cannot hold in half of them: if the share were near a half, two graphs drawn independently would disagree about $\varphi$ a good fraction of the time, and Duplicator would be losing games that the figure shows are not lost.

Said carefully: for a sentence of depth $k$, the share of graphs satisfying it must approach either zero or one, because otherwise two independent draws would disagree about it with probability bounded away from zero, and disagreement is precisely what the figure shows becomes impossible. The step is a small computation — if the share is $q$, two independent graphs disagree with probability $2q(1 - q)$, which is bounded below unless $q$ is near zero or near one — and it is the only place probability enters the proof at all. Everything else is the game.

That is a shape worth noticing, because it is how most uses of this game go. The game itself converts a statement about infinitely many sentences into a search over finitely many moves, and the surrounding argument then only has to supply the structures. Here the structures arrive by chance and the supply is the extension property; on chains they are chosen by hand; in the modal case the same reduction is done by collapsing a model rather than by playing, and the finiteness comes from the formula instead of from the size.

Watch the two curves separately, though, because the shape of the argument is in the gap between them. The deeper game gives way later. A sentence with three quantifiers needs graphs of about forty points before it stops being able to tell two of them apart, where a sentence with two needs only ten. Every depth eventually gives way, and no depth gives way at every size — which is exactly why the theorem is about the limit and cannot be about any particular size.

What a play looks like #

The chains are worth revisiting here because they show the shape of a strategy in a case where the reader can check every move, and because they show what its failure looks like. On chains a strategy is a bisection: Duplicator answers a Spoiler move by matching the proportion of the chain on each side, and the strategy fails only when a gap becomes small enough to count exactly.

The threshold $2^k - 1$ in that table is the chain version of the size at which the random-graph game becomes unlosable. In both cases a fixed depth of sentence has a size beyond which it is blind, and in both cases the size grows with the depth. The difference is what the growth costs: on chains it is exponential in the depth, and on random graphs it is roughly the size at which the extension property for $k$-sets arrives.

That logarithm is the reason the chain case is not a zero-one law. On chains, Spoiler’s requirement grows so slowly that a sentence of modest depth distinguishes structures of very different sizes. On random graphs the requirement grows the other way, and Spoiler is defeated by size rather than helped by it.

What the law rules out #

The useful direction of the theorem is the contrapositive: a property whose limiting share is anything other than zero or one is not first-order. That turns a fact about coin tosses into a proof of inexpressibility, and the proofs are short.

An even number of edges. Its share is exactly one half at every size above one, by the flipping bijection, so the limit is a half and no sentence says it. This is the property the opening figure measures, and the enumeration in the figure’s own check confirms the bijection at the smallest size drawn by counting every graph.

An even number of points. The same conclusion by an easier route: the share is one for even $m$ and zero for odd, so it does not converge at all.

Connectivity. Here the law is no help at all, and the reason is worth stating because it is the commonest misreading of the theorem. Almost every dense random graph is connected — the share goes to one — so connectivity is perfectly consistent with the law and the law cannot exclude it. It is nonetheless not first-order, and proving that needs a pair of structures chosen by hand rather than a pair drawn at random. A limit of zero or one is necessary for a first-order property and nowhere near sufficient.

Compare that with what the game gave on chains. There, inexpressibility results are proved by exhibiting a pair of structures a sentence cannot separate, and each proof needs its own pair. Here one theorem does the work for every property at once, and the pair of structures has been replaced by a pair drawn at random.

Both are the same instrument. The game measures how much a quantifier depth can see, and the zero-one law is what that measurement says when the structures are chosen by chance instead of by hand.

The edge probability matters, and the law is fragile #

The law above is for a fair coin. Nothing in the proof needs the coin to be fair — any fixed probability strictly between zero and one gives the same extension property and the same conclusion, since the failure probability per pair becomes $(1 - p^2)^{m}$ or thereabouts and still decays geometrically.

What breaks the law is letting the probability depend on the size, which is the regime where the giant component appears and where the interesting thresholds live. At $p = m^{-\alpha}$ the law holds for irrational $\alpha$ and fails for rational $\alpha$, where properties like containing a particular small subgraph have limiting shares strictly between zero and one — which is exactly what a threshold with a bounded window looks like.

So the law is not a general fact about randomness and logic. It is a fact about the dense regime, where the extension property arrives quickly enough that every fixed depth of sentence is eventually blinded. Slow down the arrival and the theorem goes with it.

What this does not settle #

The law says a first-order property’s share converges to zero or to one. It does not say which, and it does not say when.

Deciding which is a separate question with a satisfying answer: the limit is one exactly when the sentence follows from the extension axioms, and those axioms have a complete first-order theory, so the question is decidable. Deciding when — at what size the share is within a given distance of its limit — is not answered by the argument at all, and the figures show why it would be awkward: the two-round game becomes unlosable at ten points and the three-round game at forty, and nothing here predicts either number in advance.

The law also says nothing about properties outside the language. Connectivity, having an even number of edges, and containing a Hamiltonian path are all excluded from the first-order language, and each is settled by a different method: the game played on a pair chosen by hand for the first, a counting bijection for the second, and threshold arguments belonging to the theory of random graphs for the third.

There is also nothing here about how many sentences are involved. The law quantifies over an infinite language, and the proof handles it by depth: every sentence has a finite depth, and the argument is uniform in that depth. It is the same device that makes the game worth playing at all — a question about every sentence answered by a search over moves — and it is why a single figure showing two depths can stand for a statement about all of them.

And the whole apparatus is about finite structures. The extension property in the limit describes a single infinite object — the random graph, unique up to isomorphism, in which every finite extension demand can be met — and every first-order sentence true of it is true of almost every finite random graph. That is the cleanest statement of the law, and it hands the question to model theory: a property is almost surely true exactly when that one infinite graph satisfies it. The coin tosses were only ever a way of asking about a structure that was there all along.