MathematicsPreprintTheory3 min read

RANDOM NETWORKS STOP BEING COLOURABLE AT A FIXED DENSITY

Take a graph — dots joined by links — and a box of colours. A proper colouring with q colours gives every dot one of q colours so that two linked dots never share one. With few links, that is easy. With many, it becomes impossible.

Now build the graph at random: n dots, each pair linked independently with a small probability, so that a dot has d neighbours on average. As d grows, the random graph passes from “almost surely colourable with q colours” to “almost surely not”. Where exactly does the switch happen? That question, for any fixed number of colours q from three up, is the subject of a new paper by Gaia Carenini, at the University of Cambridge.

A switch that might wobble

In a paper from 1999 listed in the bibliography, Achlioptas and Friedgut proved that the transition is sharp: for every size n, there is a critical average degree d_q(n) such that slightly below it, the graph is almost surely colourable, and slightly above it, almost surely not. The window in which the switch happens shrinks to nothing.

But that left a loophole. Nothing prevented the critical value itself from oscillating as graphs got bigger — sitting at one place for graphs of one size, slightly elsewhere for bigger ones, and never settling. The Achlioptas–Friedgut convergence conjecture states that this does not happen: for each q, there is a single constant d_q, below which random graphs are colourable and above which they are not.

What physicists predicted

Statistical physics had a picture of what goes on. As links are added, the valid colourings group into clusters: colourings within a cluster resemble each other, while two clusters differ on many dots. Then, at a stage called condensation, a handful of large clusters hold a substantial share of all colourings — and only later does the set of colourings become empty. That organisation explains why counting arguments struggle near the threshold.

For many colours, previous work had already pinned the threshold into a narrow range: it lies between about 2q log q − log q − 2 log 2 and 2q log q − log q − 1, a gap of width 2 log 2 − 1 as q grows. But “narrow” is not “fixed”, and for small numbers of colours such as three, the question remained open.

A twin problem, tackled first

Colouring has a twin: satisfiability, the problem of choosing true or false values for variables so that a list of random logical constraints all hold. There too, a sharp threshold was known to exist without proof that it settles. In a report from 2026 cited in the paper, Carenini announced a proof that it does, for every constraint length from three up, by showing that the transition window is very narrow. The new paper adapts that argument to colouring.

Pairs that are frozen together

The proof proceeds through a chain of reductions. Adding random links one by one, let H be the moment the graph stops being colourable. If H varies little from one random graph to another — within a window of about n/(log n)² links — then the threshold must settle. A classical inequality turns that into a question about the last colourable graph: on average, how many fresh random links does it survive?

Here comes the key notion: frozen pairs. Two dots form a frozen pair when every valid colouring gives them the same colour. A fresh link is fatal exactly when it joins such a pair. Single dots cannot be frozen to one particular colour, since swapping the colours around always gives another valid colouring; what gets forced is a relation between two dots. Carenini tracks how these frozen classes grow as links are added, by deleting a link or a whole dot and looking at the choices that reappear. The estimates show that the last colourable graph cannot survive long, which narrows the window enough to prove the conjecture.

What remains unknown

The theorem says that the threshold d_q exists for every q ≥ 3. It does not say where it is: the paper gives no value for it, even for three colours. The paper is a preprint with a single author and has not been peer-reviewed. It ends with a short statement that none of its mathematical arguments was generated by a large language model.