Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-329 | 12th November 2026 08:15

A Proof of the Achlioptas-Friedgut Convergence Conjecture

RSS-Feed




TR26-329
Authors: Gaia Carenini
Publication: 22nd November 2026 15:31
Downloads: 32
Keywords: 


Abstract:

For every fixed integer $q\ge3$, we show that the $q$-colourability transition in a sparse random graph takes place at a limiting edge density, thus proving the Achlioptas-Friedgut convergence conjecture. The proof adapts the argument we recently introduced to settle the satisfiability conjecture.



ISSN 1433-8092 | Imprint