LES RÉSEAUX ALÉATOIRES CESSENT D'ÊTRE COLORIABLES À UNE DENSITÉ FIXE
Prenez un graphe — des points reliés par des liens — et une boîte de couleurs. Un coloriage propre avec q couleurs donne à chaque point l’une des q couleurs, de sorte que deux points reliés n’aient jamais la même. Avec peu de liens, c’est facile. Avec beaucoup, cela devient impossible.
Construisons maintenant le graphe au hasard : n points, chaque paire reliée indépendamment avec une petite probabilité, de sorte qu’un point a en moyenne d voisins. Quand d augmente, le graphe aléatoire passe de « presque sûrement coloriable avec q couleurs » à « presque sûrement pas ». Où se fait exactement la bascule ? Cette question, pour tout nombre fixé de couleurs q à partir de trois, est le sujet d’un nouvel article de Gaia Carenini, de l’université de Cambridge.
Une bascule qui pourrait osciller
Dans un article de 1999 cité en bibliographie, Achlioptas et Friedgut ont démontré que la transition est abrupte : pour chaque taille n, il existe un degré moyen critique d_q(n) tel que, juste en dessous, le graphe est presque sûrement coloriable et, juste au-dessus, presque sûrement pas. La fenêtre dans laquelle se fait la bascule se réduit à rien.
Mais il restait une faille. Rien n’empêchait la valeur critique elle-même d’osciller quand les graphes grossissent — à un endroit pour des graphes d’une certaine taille, un peu ailleurs pour de plus grands, sans jamais se fixer. La conjecture de convergence d’Achlioptas-Friedgut affirme que cela n’arrive pas : pour chaque q, il existe une seule constante d_q, en dessous de laquelle les graphes aléatoires sont coloriables et au-dessus de laquelle ils ne le sont pas.
Ce que prédisait la physique
La physique statistique avait une image de ce qui se passe. À mesure qu’on ajoute des liens, les coloriages valides se regroupent en amas : à l’intérieur d’un amas, les coloriages se ressemblent, tandis que deux amas diffèrent sur beaucoup de points. Puis, à une étape appelée condensation, une poignée de grands amas rassemblent une part substantielle de tous les coloriages — et ce n’est que plus tard que l’ensemble des coloriages devient vide. Cette organisation explique pourquoi les arguments de comptage peinent près du seuil.
Pour un grand nombre de couleurs, des travaux antérieurs avaient déjà coincé le seuil dans une plage étroite : entre environ 2q log q − log q − 2 log 2 et 2q log q − log q − 1, un écart de largeur 2 log 2 − 1 quand q grandit. Mais « étroit » ne veut pas dire « fixe », et pour de petits nombres de couleurs comme trois, la question restait ouverte.
Un problème jumeau, attaqué d’abord
Le coloriage a un jumeau : la satisfiabilité, le problème de choisir des valeurs vrai ou faux pour des variables de sorte qu’une liste de contraintes logiques aléatoires soient toutes respectées. Là aussi, on savait qu’un seuil abrupt existe, sans preuve qu’il se fixe. Dans un rapport de 2026 cité par l’article, Carenini a annoncé une preuve que c’est le cas, pour toute longueur de contrainte à partir de trois, en montrant que la fenêtre de transition est très étroite. Le nouvel article adapte cet argument au coloriage.
Des paires gelées ensemble
La preuve procède par une chaîne de réductions. En ajoutant des liens au hasard un par un, notons H le moment où le graphe cesse d’être coloriable. Si H varie peu d’un graphe aléatoire à l’autre — dans une fenêtre d’environ n/(log n)² liens —, alors le seuil doit se fixer. Une inégalité classique transforme cela en une question sur le dernier graphe coloriable : combien de nouveaux liens aléatoires survit-il, en moyenne ?
C’est là qu’intervient la notion clé : les paires gelées. Deux points forment une paire gelée quand tout coloriage valide leur donne la même couleur. Un nouveau lien est fatal exactement quand il relie une telle paire. Un point seul ne peut pas être gelé sur une couleur particulière, puisqu’en permutant les couleurs on obtient toujours un autre coloriage valide ; ce qui est forcé, c’est une relation entre deux points. Carenini suit la croissance de ces classes gelées à mesure qu’on ajoute des liens, en supprimant un lien ou un point entier et en regardant les choix qui réapparaissent. Les estimations montrent que le dernier graphe coloriable ne peut pas survivre longtemps, ce qui resserre assez la fenêtre pour démontrer la conjecture.
Ce qui reste inconnu
Le théorème dit que le seuil d_q existe pour tout q ≥ 3. Il ne dit pas où il se trouve : l’article ne lui donne aucune valeur, même pour trois couleurs. Il s’agit d’une prépublication sans coauteur, qui n’a pas été relue par des pairs. Elle se termine par une courte déclaration : aucun de ses arguments mathématiques n’a été produit par un grand modèle de langage.
