Sharp, or merely a threshold

The two-moment method locates a threshold: a value of the edge probability below which a property is unlikely and above which it is likely. Every monotone property has one, and the method finds it for most of the properties anybody asks about.

It says nothing about how quickly the property turns on, and that second quantity turns out to divide the properties into two kinds.

What the width is #

Fix a property and a size. Find the edge probability at which the property has chance a tenth, and the one at which it has chance nine-tenths. The gap between them is the width of the transition, and the quantity that matters is the width divided by the threshold itself.

A threshold is sharp when that relative width goes to zero as the graph grows: the transition, measured as a fraction of where it happens, gets narrower and narrower until the property looks like a step function. It is coarse when the relative width does not go to zero.

Both kinds exist and the figure exhibits one of each. Connectivity’s relative width falls across the three sizes drawn; containing a triangle’s does not.

The choice of a tenth and nine-tenths is arbitrary and does not matter, which is worth saying once. Replacing them by a hundredth and ninety-nine hundredths changes every width by a constant factor and changes nothing about whether the relative width tends to zero — so sharpness is a property of the sequence rather than of the convention, and any two choices give the same classification.

Which properties are which #

Friedgut’s theorem, from 1999, says what decides it, and the statement is a dichotomy rather than a criterion.

A monotone property has a coarse threshold only if it is approximated by the appearance of a bounded local structure. Containing a triangle is exactly that: a triangle is three vertices and three edges, its size does not grow with $n$, and the property holds as soon as one appears anywhere. Any property of that shape has a coarse threshold, and every property not approximable that way has a sharp one.

Connectivity is not of that shape. It is not the appearance of any bounded structure; it is the absence of one — an isolated vertex — and an absence of a structure whose expected count is falling is a global condition.

So the dichotomy is between a property that wants something to appear and one that wants everything to be in order, and the second is sharp because it is a conjunction of a great many conditions rather than a disjunction of a few.

The counting behind that sentence is worth doing. A triangle can appear in any of about $n^3$ places, and at the threshold the expected number present is a constant — so the property is a disjunction of $n^3$ nearly-independent events each of chance about $n^{-3}$, and the number present is Poisson. Doubling $p$ multiplies the expected count by eight and the chance of at least one moves smoothly.

Connectivity fails through isolated vertices, of which there are only $n$ possible, and at its threshold the expected number present is again a constant — but the parameter has to be much larger to get there, because an isolated vertex needs all $n-1$ of its potential edges to be absent. That is a conjunction of $n-1$ conditions, its probability falls exponentially in $p n$, and an exponentially sensitive quantity crosses its threshold over an exponentially narrow range of $pn$. The sharpness is the exponential, and the reason connectivity’s sharpening is only logarithmic is that the threshold itself grows like a logarithm.

Why the local case is coarse #

The mechanism is one line and is worth having, because it explains the shape as well as the classification.

The number of triangles at edge probability $c/n$ is approximately Poisson with mean $c^3/6$, which is the second-moment calculation of the rung below run to its conclusion rather than stopped at the threshold. So the chance of at least one is $1 - e^{-c^3/6}$, which is a function of $c$ alone — no $n$ in it anywhere.

That single fact is coarseness. Moving $c$ from 1 to 2 moves the chance from about 15 per cent to about 74 per cent, at every size, forever. The transition occupies the same range of $c$ however large the graph, so measured relative to the threshold $1/n$ its width is a constant.

A property whose probability depends only on the expected count of a bounded structure cannot have a sharp threshold, because the expected count is a smooth function of the parameter and its Poisson consequence is a smooth curve.

That also says which direction the theorem runs. Friedgut’s result is that coarseness implies local approximability — the harder direction, since it has to produce a structure from an assumption about a curve. The easy direction is the paragraph above: a local property is visibly coarse, by the Poisson calculation. An implication whose easy direction is a calculation and whose hard direction is a theorem is usually stated in the hard direction, which is why the theorem is quoted as a dichotomy rather than as a sufficient condition.

Why the global case is sharp #

Connectivity behaves differently and the reason is that what obstructs it is a count of rare events rather than a single one.

At $p = (\log n + \lambda)/n$ the number of isolated vertices is approximately Poisson with mean $e^{-\lambda}$ — which is the calculation that separates the two thresholds — so the chance of connectedness is about $e^{-e^{-\lambda}}$ — again a function of one variable, but that variable is $\lambda$, which measures $p$ in units of $1/n$ rather than as a multiple of the threshold.

The threshold is $\log n/n$, and the window is a range of $\lambda$ of constant size, so a range of $p$ of size about $1/n$. Divide the second by the first and the relative width is about $1/\log n$, which goes to zero — slowly, which is why the figure’s narrowing is visible and modest.

The numbers the figure produces #

The relative widths are worth writing out, because the two rows are the whole of the classification and they are not dramatic.

Connectivity, across the three sizes: 0.618, 0.639, 0.514. Containing a triangle: 0.982, 1.053, 1.130.

Two things are visible. The triangle’s row is around one and drifting upward slightly; connectivity’s is around six tenths and drifting downward. And neither row is doing anything fast.

The theorem says the first row tends to zero like $1/\log n$ and the second tends to a positive constant. Both are consistent with what is measured and neither is demonstrated by it — the sizes span a factor of a little over two, over which $1/\log n$ falls by about a fifth, and the sampling noise at sixty graphs per point is of that order.

The value of the measurement is that the two rows are on opposite sides of each other and stay there. A row near one and a row near a half, with the second the one the theorem calls sharp, is the right qualitative picture; asking a small experiment for more than that is asking it for the theorem.

There is one more reading, about the triangle’s slight upward drift. It is not evidence against coarseness — the limiting curve is $1 - e^{-c^3/6}$ and the relative width computed from it is a fixed number a little above one, so a row creeping towards that number from below is exactly what a finite-size correction looks like.

Reading the measurement honestly #

The figure measures three sizes, which is enough to see a trend and not enough to see a limit.

Connectivity’s relative width falls across them, as $1/\log n$ predicts, and $1/\log n$ falls very slowly: from a graph of forty points to one of ninety it improves by about a fifth. A sharp threshold whose sharpening is logarithmic looks almost identical to a coarse one over any range a figure can carry, and the honest report is that the measurement is consistent with the theorem rather than a demonstration of it.

The triangle’s relative width does not fall at all, which is the easier half to see: a quantity that stays put across three sizes is more convincing than one that falls by a fifth.

That asymmetry is worth generalising. Distinguishing “goes to zero” from “stays constant” needs the going-to-zero to be fast; when it is logarithmic, no experiment settles it and the classification has to come from the theorem. A dichotomy proved by mathematics and invisible to measurement is the normal situation, and it is a reason to have both.

What sharpness buys #

The classification is not an aesthetic one. A sharp threshold means a property is essentially deterministic once the parameter is known to a small relative accuracy, and that is what makes a threshold usable.

For connectivity, knowing $p$ to within a factor of $1 + 1/\log n$ determines the answer with high probability. For a triangle, knowing $p$ to any relative accuracy determines nothing better than a probability strictly between zero and one — the answer is genuinely random, and no amount of pinning down the parameter removes the randomness.

There is a third way to put the same distinction, in terms of what a single graph settles. For a sharp property, one sample at a known $p$ is almost certainly representative: the answer is the same for nearly every graph at that $p$. For a coarse one it is not, and a study reporting that one graph generated at this density contained a triangle has reported the outcome of a coin toss and nothing about the density at all.

So sharpness is the difference between a threshold that predicts and one that only describes. A designer choosing an edge probability to guarantee connectivity has a usable target; one choosing it to guarantee a triangle does not, and has to accept a chance instead.

Every property has one #

Before the dichotomy there is a prior theorem, which is worth stating because it is what makes “the threshold” a phrase at all.

Bollobás and Thomason, 1987: every monotone property of graphs has a threshold. There is always a function $p^*(n)$ such that below any fixed multiple of it the property is unlikely and above any fixed multiple it is likely. No monotone property turns on gradually across the whole range of $p$, and none turns on in two separate places.

That is not obvious. A property could in principle be likely at $p = 0.1$, unlikely at $p = 0.2$ and likely again at $0.3$ — except that monotonicity forbids the middle step, and monotonicity is doing all the work. Adding edges never destroys a property in this class, so its probability is non-decreasing in $p$, and a non-decreasing function from zero to one has one place where it climbs.

The theorem’s content is that the climb is confined: the ratio of the point where the chance is nine-tenths to the point where it is a tenth is bounded, for every monotone property, by a quantity that does not depend on the property.

So a threshold always exists and its width is bounded, and the dichotomy is about whether the bound can be improved to zero. Reading the two theorems in that order makes the second one’s shape clear: it is not asking whether there is a transition, it is asking how good the general bound can be made for a particular property.

Where the dichotomy is used #

The theorem’s real value is in settings where the threshold’s location is unknown and its sharpness is not.

The satisfiability threshold for random formulas is the standard example. Nobody knows the exact density at which a random formula with three literals per clause stops being satisfiable — the best bounds still differ — and the sharpness of that threshold was proved before its location was known, by exactly this route. That is a strange order in which to learn things and a useful one: sharpness alone justifies speaking of “the” threshold, which every experimental paper on the subject had been doing for a decade without warrant.

There is a fourth field where the same reasoning applies and is worth naming, because it is the one most people meet first. A percolation model of a physical material — will current flow, will a crack propagate — has a threshold, and whether that threshold is sharp decides whether a manufacturing tolerance is meaningful. A sharp threshold means a specification can be written; a coarse one means the answer is a yield rather than a guarantee, however precisely the process is controlled. The critical window is the same statement for the one property where the exponents are known exactly.

The same pattern recurs wherever a property is studied numerically before it is understood. A measurement shows a steep transition; the dichotomy says whether the steepness is real or an artefact of the range measured; and only then is it worth trying to locate the point.

What the pictures cannot show #

Three sizes, sixty samples per setting and twenty-seven settings of $p$ each. That is a small experiment, chosen so the exhaustive triangle search and the component walk stay inside a figure’s budget, and its error bars are of the same order as the effect it measures for connectivity.

Friedgut’s theorem is stated and not proved. Its proof uses a Fourier analysis of Boolean functions and is one of the harder results quoted anywhere on this ladder; the object it analyses is the property read as a function on the cube of edge-sets, and the sharpness of the threshold turns out to be a statement about how that function’s Fourier weight is distributed.

And the satisfiability example is described. It lives over random formulas rather than random graphs, and nothing here computes with it.

Where the ladder goes next #

This rung closes the ladder: the transition observed, the giant located, the second threshold separated, the general method, the critical window, and now the width.

Named here as debts. Friedgut’s proof, which is a piece of harmonic analysis on the cube and would need its own foundation. And the satisfiability threshold, whose location is still open and which is where the two-moment method has been pushed hardest.

Sideways, the method that locates a threshold is the rung below, the two thresholds this compares are the rung below that, the window at the giant’s birth is the rung between, and the isolated vertex that obstructs connectivity is what the last edge has to reach.

What is worth carrying away #

Locating a transition and measuring its width are different questions, and the second is the one that decides whether the first is useful.

Every monotone property has a threshold. Only some have a threshold sharp enough that knowing the parameter determines the answer, and which ones is decided by whether the property is the appearance of a bounded structure — a disjunction over many chances — or a condition on everything at once.

The habit worth taking is to ask what a transition’s width is, in units of where it happens. A width that is a constant fraction of the threshold means the property stays random however large the system; a width that shrinks means it becomes deterministic, and the difference is what an engineer needs and a probabilist usually does not state.

The corollary is about reading a steep curve. A transition looks sharp in every picture, because a picture is drawn over whatever range makes it look interesting. Sharpness is a statement about a sequence of sizes, not about any one of them — so a single steep curve is evidence of nothing, and the only informative plot is several sizes on the same rescaled axis.