J'ai déjà parlé à plusieurs reprises du problème de Hadwiger-Nelson sur ce blog (ici en général, et ici pour mes malheurs personnels liés à ce problème), et il faut que j'en reparle puisqu'il y a eu un progrès considérable. Le problème de Hadwiger-Nelson a ceci de sympathique que c'est un problème de mathématique de niveau recherche (au sens empirique où il y a, effectivement, des mathématiciens professionnels qui ont fait de la recherche dessus et publié des choses à son sujet) dont un bon élève de primaire peut comprendre l'énoncé, un bon collégien peut comprendre les meilleures bornes connues jusqu'à la semaine dernière, et un bon lycéen peut les trouver lui-même. (Enfin, quelque chose comme ça.) Je rappelle l'énoncé :
Trouver le plus petit nombre χ de couleurs nécessaires pour colorier le plan de manière à ce qu'il n'y ait jamais deux points situés à distance 1 l'un de l'autre et qui aient la même couleur.
Ce χ s'appelle le nombre chromatique du plan
ou nombre [chromatique] de Hadwiger-Nelson
. Jusqu'à la semaine
dernière, tout ce qu'on savait était que 4≤χ≤7.
Le fait que χ≤7, c'est-à-dire que sept couleurs suffisent, est montré par un coloriage explicite (d'un pavage du plan par des hexagones) avec 7 couleurs, coloriage qui est représenté par le dessin ci-contre à droite que je recopie de ma précédente entrée sur le sujet ; l'unité de longueur est figurée par le trait noir dans le coin en haut à gauche de la figure : quel que soit l'endroit où on le place et la manière dont on le tourne, les deux extrémités tombent toujours sur deux couleurs différentes ; et le problème est, donc, de savoir si on peut faire ça avec strictement moins de sept couleurs.
La minoration χ≥4 (c'est-à-dire qu'au moins quatre
couleurs sont nécessaires), elle, est démontrée par un graphe fini
tout à fait explicite, appelé Moser's spindle
(fuseau de Moser
?) : je le recopie lui aussi de mon entrée
précédente (ci-contre à gauche), toutes les arêtes représentées ont la
même longueur (l'unité de longueur), et il n'est pas possible de
colorier ses sommets avec seulement trois couleurs de façon que deux
sommets reliés par une arête ne soient jamais de la même couleur. (En
effet, si on ne dispose que de trois couleurs, chaque triangle
équilatéral de côté 1 [du graphe] doit avoir un sommet de chaque
couleur, du coup, dans le graphe représenté à gauche, chacun des deux
sommets en haut à droite a la même couleur que celui en bas à gauche,
donc ils ont la même couleur l'un que l'autre, or ils sont reliés par
une arête.) Bref, dans tout coloriage du plan avec 3 couleurs, il y
en a deux situés à distance 1 qui ont la même couleur.
Si vous n'aimez pas le fuseau de Moser, vous pouvez aussi utiliser
le graphe de Golomb
, représenté ci-contre à gauche (lui n'était
pas dans l'entrée précédente, il faut bien que je m'embête un peu à
faire du SVG et à calculer que les coordonnées d'un point
valent (1,√11)/6), qui est plus joli et plus symétrique. Comme le
fuseau de Moser, il n'est pas coloriable avec trois couleurs : si on a
seulement trois couleurs, une fois qu'on en donne une au point
central, les six points à distance 1 de lui doivent partager les deux
autres couleurs en alternance, et notamment les trois qui sont reliés
au triangle « oblique » sont de la même couleur, ce qui ne laisse que
deux couleurs pour colorier ce dernier.
Bref, la minoration vient de graphes finis tout à fait explicites.
En fait, on sait à cause d'un théorème de compacité (que les théoriciens des graphes appellent le théorème d'Erdős et de Bruijn, et que les logiciens considèrent comme une conséquence immédiate du théorème de compacité du calcul propositionnel) que toute minoration sur χ s'obtient par un graphe fini, c'est-à-dire que χ est aussi la plus grande valeur possible du nombre de couleurs d'un graphe de ce genre. Donc on peut reformuler le problème de Hadwiger-Nelson de la façon suivante :
Trouver le plus petit nombre χ de couleurs nécessaires pour colorier un nombre fini quelconque de points du plan de manière à ce qu'il n'y ait jamais deux points situés à distance 1 l'un de l'autre et qui aient la même couleur.
(Le « fuseau de Moser » ci-dessus étant à comprendre comme l'ensemble de sept points qui sont les sommets tracés : on ne peut pas colorier cet ensemble de sept points avec trois couleurs donc χ≥4.)
Jusqu'à la semaine dernière, donc, c'est tout ce qu'on savait. Toute recherche sur ce problème a porté sur des analogues ou des généralisations (nombre chromatique de l'espace, nombre chromatique du plan à coordonnées dans ceci-cela, nombre chromatique fractionnaire, ce genre de choses).
•
Voilà que, dimanche, un certain Aubrey (David Nicholas Jasper) de Grey a mis un papier sur l'arXiv prouvant que χ≥5 : i.e., dans tout coloriage du plan avec 4 couleurs, il y en a deux situés à distance 1 qui ont la même couleur. (Je l'ai appris par un commentaire sur ma première entrée au sujet du problème.)
C'est assez sidérant pour plusieurs raisons. D'abord parce que
c'est quand même un problème sur lequel on est restés coincés pendant
environ 50 ou 60 ans (l'histoire du problème est elle-même assez
tarabiscotée, mais il semble que Nelson l'ait imaginé dans les
années '50 et qu'il — le problème — soit devenu célèbre une petite
dizaine d'années plus tard). Mais aussi parce le de Grey auteur du
papier n'est pas mathématicien (ou en tout cas, pour éviter de se
mouiller sur ce que mathématicien
veut dire, il n'est pas
mathématicien de profession, et ne semble pas avoir fait de
contributions aux mathématiques avant ça) ; il est
« biogérontologue », connu pour ses positions contre le
vieillissement, et considéré par certains comme un gourou voire un
crackpot (le fait
qu'il ressemble
à Gandalf doit aider ce genre de préjugés). Il ne faut pas croire
sur parole n'importe quel papier mis sur l'arXiv surtout quand il
annonce un résultat « spectaculaire », mais, en l'occurrence, (1) le
papier est bien écrit (les arguments sont rapides mais clairs et
écrits dans le style habituel dans lequel on écrit les mathématiques),
et de toute façon (2) une fois connu le graphe construit, il est
modérément facile de vérifier le résultat par ordinateur, des gens
ont déjà
vérifié qu'un des graphes décrits par de Grey est réalisable avec
distance 1[#] et (au moyen
d'un SAT-solver)
n'est pas 4-coloriable[#2],
donc le résultat principal est certifié valable (nonobstant
d'éventuelles erreurs très mineures dans la description).
[#] Ici et dans la
suite, j'emploie le terme réalisable avec distance 1
pour dire
que le graphe est réalisable comme un ensemble de points dans le plan
de sorte que toutes les arêtes aient longueur 1. (On peut
éventuellement demander que, réciproquement, chaque paire de points à
distance 1 donne effectivement une arête du graphe ça ne changera rien
puisque ajouter des arêtes ne peut qu'augmenter le nombre
chromatique.)
[#2] Ici et dans la
suite, j'emploie le terme k-coloriage
pour
signifier, bien sûr, un coloriage avec k couleurs de façon
que deux sommets reliés par une arête (i.e. à distance 1) ne soient
jamais de la même couleur ; et k-coloriable
pour
dire qu'un k-coloriage existe.
Mais pour être épatant, ce résultat est aussi un peu frustrant, je vais essayer de dire pourquoi.
Quand j'avais commencé à réfléchir au problème de Hadwiger-Nelson,
ma première intuition était que χ=7 était sans l'ombre d'un
doute la bonne valeur, et qu'il s'agissait juste de trouver de bons
graphes, et que, si on ne les connaissait pas, c'était juste qu'on
n'avait pas cherché assez fort, notamment avec des ordinateurs.
(Cette intuition initiale est donc confirmée par le résultat de
de Grey, mais je ne vais pas dire ha ha, j'avais raison
,
puisque, comme je vais l'expliquer, j'ai ensuite changé d'avis.) En
gros, ce qui fait « marcher » le « fuseau de Moser » représenté
ci-dessus est qu'on a le triangle équilatéral dont les 3-coloriages
sont très peu nombreux, donc suffisamment rigides pour qu'on arrive à
les combiner pour fabriquer un graphe plus gros qui n'est pas
3-coloriable. L'espoir, ensuite, serait que les 4-coloriages du
fuseau (ou du graphe de Golomb) soient assez rigides pour qu'on arrive
à combiner plusieurs fuseaux pour former un graphe qui ne soit pas
4-coloriable. Et qu'on puisse monter encore un coup pour former un
graphe qui ne soit pas 5-coloriable, puis un qui ne soit pas
6-coloriable, ce qui démontrerait χ=7.
Plus tard, j'étais beaucoup moins convaincu de χ=7 : la raison est que j'ai essayé de réfléchir à comment on pourrait construire des graphes réalisable avec distance 1 et qui ne soient pas 4-coloriables, et j'ai eu l'impression de buter contre des problèmes insurmontables. Comme je le dis au paragraphe précédent, on peut essayer de combiner des fuseaux de Moser (ou des graphes de Golomb) et essayer de limiter leurs possibilités de 4-coloriages jusqu'à toutes les tuer. Mais j'ai un peu essayé et je m'y suis salement cassé les dents : tout me semblait suggérer que plus on augmente le nombre de sommets plus les possibilités de 4-coloriages se multiplient, plus vite qu'on arrive à les tuer en ajoutant des arêtes. Pour être un peu moins vague, j'ai eu l'impression que la seule façon exploitable de fabriquer des graphes réalisables avec distance 1 dans le plan est de prendre deux graphes G₁,G₂ déjà réalisés avec distance 1 et utiliser une isométrie plane sur G₂ (en faixant G₁) pour imposer des identifications de sommets ou fabriquer des arêtes, mais pour ça, on n'a que très peu de degrés de liberté (le groupe des isométries planes est de dimension 3), donc, sauf coïncidences, on ne peut ajouter essentiellement que trois arêtes (ou une identification de sommet et une arête) ; j'ai eu l'impression que « sauf coïncidence », tout ceci devrait conduire à une borne sévère sur la dégénérescence des graphes réalisables avec distance 1, donc sur leur nombre chromatique ; en fait, qu'ils devaient être des graphes de Laman — « sauf coïncidence », donc, mais je ne voyais pas comment fabriquer des « coïncidences » intéressantes. Bref, tout ça pour dire que j'ai essayé justement l'approche que de Grey fait marcher, que je n'ai pas du tout réussi à en faire quoi que ce soit, et que je me suis même mis à penser que ça ne pouvait pas marcher « sauf coïncidence » mais que ce serait extraordinairement difficile de prouver l'inexistence de telles « coïncidences » ou, a contrario, d'en fabriquer. Du coup, j'ai commencé à douter que χ=7 soit la bonne valeur (je ne prétends pas que j'étais convaincu que χ=4, mais que ma foi dans le fait que χ=7 s'était envolée jusqu'à ce qu'on me signale la trouvaille de de Grey).
Ajout : Un autre de mes espoirs était qu'on puisse chercher à extraire un graphe de nombre chromatique au moins 5 (voire 6, voire 7) comme un sous-graphe de l'analogue de Hadwiger-Nelson sur un corps fini, disons le graphe (ℤ/pℤ)² avec une arête entre (x₁,y₁) et (x₂,y₂) lorsque (x₂−x₁)² − (y₂−y₁)² = 1. (La motivation étant que si un graphe plan est réalisable avec distance 1, il est aussi réalisable à coordonnées algébriques, ces coordonnées de scindent modulo un ensemble de densité >0 de nombres premiers p, donc imposent la même inégalité sur les nombres chromatiques des (ℤ/pℤ)² pour la relation que je viens de dire.) Évidemment, cet espoir était naïf — mais vu que les coordonnées du graphe calculé par de Grey sont dans des extensions assez petites de ℚ comme je le soupçonnais, ce n'était pas complètement stupide non plus.
C'est dire que je suis surpris par le tour de force. La lecture du papier lui-même est un peu décevante, cependant : il y a un mélange de raisonnements « à la main » sur les 4-coloriages de graphes de plus en plus grands réalisables avec distance 1, et de vérifications par ordinateur (avec différentes astuces pour rendre la vérification plus gérable), mais au final je ne suis pas vraiment Éclairé sur la manière dont il arrive à obtenir suffisamment d'arêtes eu égart au nombre de sommets (le graphe réalisable avec distance 1 et non 4-coloriable dont Dustin Mixon publie le fichier de données sur son blog — revoici le lien — a 1585 sommets et 7909 arêtes), ou sur la raison pour laquelle je m'étais trompé en pensant qu'il était très difficile d'obtenir une grande dégénérescence.
Ce qui est frustrant, c'est que ce progrès rend le problème de Hadwiger-Nelson beaucoup moins intéressant. Peut-être que la presse généraliste va s'en emparer (et raconter des conneries), et il va sans doute y avoir des efforts renouvelés pour construire des graphes plus simples prouvant χ≥5 (cf. ici) ou pour pousser jusqu'à χ≥6 voire χ=7, mais mathématiquement, le problème a un peu perdu de sa beauté. Pourquoi ? Déjà parce qu'on ne peut plus donner ça comme un exemple de problème où l'état de l'art correspond à ce qu'un lycéen peut trouver tout seul. Mais surtout je suis maintenant revenu à mon intuition première, et complètement convaincu d'une part que χ=7 et d'autre part que des graphes le démontrant peuvent se construire avec des techniques de type « dupliquer et identifier » et des recherches sur ordinateur (à supposer qu'ils ne soient pas trop grands). Il aurait été beaucoup plus intéressant de chercher à montrer que certains graphes ne peuvent pas exister que de chercher à les exhiber.
Après, on peut s'intéresser à toutes sortes de problèmes adjacents. Je soumets notamment la question suivante, ou problème de Hadwiger-Nelson lorentzien (que j'espérais rendre publique via cette note, mais comme cette dernière est partie à la poubelle, personne n'est au courant de ce problème) [ajout : cf. cette question sur MathOverflow] :
Trouver le plus petit nombre χL de couleurs nécessaires (ou bien ∞ si aucun nombre fini ne suffit) pour colorier le plan de manière à ce qu'il n'y ait jamais deux points (t₁,x₁) et (t₂,x₂) situés à intervalle de Lorentz 1 l'un de l'autre, c'est-à-dire (t₂−t₁)² − (x₂−x₁)² = 1, et qui aient la même couleur.
(Autrement dit, on remplace les cercles de rayon 1 — translatés de {x²+y²=1} — dans le problème de Hadwiger-Nelson par des hyperboles translatées de {t²−x²=1}, représentant, si on veut, un intervalle d'espace-temps. Il y a beaucoup de similarités, parce que le groupe des isométries lorentziennes, comme le groupe des isométries euclidiennes, et de dimension 3. À la différence du problème de Hadwiger-Nelson euclidien, dans le problème lorentzien les graphes réalisables avec intervalle 1 sont naturellement orientés, par la valeur de la coordonnée t ; et on peut se convaincre qu'il n'existe pas de triangle ; comme il existe néanmoins des cycles d'ordre impair, on a quand même χL≥3.)
Je conjecture que χL=∞ (en tout cas, je ne sais montrer aucune borne supérieure sur χL). Le problème semble plus dur que Hadwiger-Nelson euclidien, car il ne semble pas exister de coloriage évident avec un nombre fini de couleurs, mais a contrario, si on veut prouver χL=∞, il faudra construire toute une famille de graphes finis.
Ajout : Je devrais mentionner qu'une des raisons de s'intéresser à χL est que l'analogue complexe du nombre de Hadwiger-Nelson, c'est-à-dire le nombre chromatique χC du graphe ℂ² avec une arête entre (x₁,y₁) et (x₂,y₂) lorsque (x₂−x₁)² − (y₂−y₁)² = 1, majore à la fois χ (euclidien) et χL (lorentzien), et qu'il est lui-même majoré par le χ de ℝ⁴ pour la métrique de signature indéfinie (++−−) (c'est-à-dire le nombre chromatique du graphe ℝ⁴ avec des arêtes définies par des hyperboloïdes translatés de {t²+u²−v²−w²=1}). Je conjecture à plus forte raison que χC=∞, et en fait c'est surtout ça que je trouve intéressant (parce que c'est un problème purement algébrique).