Mathematics

Carenini proves the Achlioptas-Friedgut conjecture on random graph colouring

For every fixed \(q \ge 3\), the threshold at which a sparse random graph stops being \(q\)-colourable converges to a limiting edge density, according to a new paper by Gaia Carenini.

Filed under Mathematics, Probability

A sparse random graph on \(n\) vertices with a fixed average degree is, with high probability, colourable with \(q\) colours when the edge density is low and not colourable when it is high. The Achlioptas-Friedgut conjecture asserts that this transition happens at a single limiting edge density as \(n \to \infty\), rather than at a threshold that might keep moving with \(n\).

Carenini’s paper proves the conjecture for every fixed \(q \ge 3\). The proof adapts the argument she recently used to settle the satisfiability conjecture for random \(k\)-SAT, a result also obtained shortly afterwards by an OpenAI model. The paper has not yet been peer reviewed.