Rediffusion d’un article publié le 23 septembre 2018
Le Problème des Six Couleurs
Que vaut le nombre chromatique du plan : cinq, six ou sept ?
Piste bleue Le 10 octobre 2021 Voir les commentaires (2)
Cet article fait partie de notre dossier À lire et relire cet été.
Rediffusion.
Introduction
Les mathématiques discrètes regorgent de problèmes de coloriages : on cherche à colorier des objets mathématiques en satisfaisant certaines contraintes tout en utilisant le moins de couleurs possible. D’apparence anodine, ces problèmes ont tendance à être très difficiles et à rester ouverts pendant des décennies, voire beaucoup plus.
Le présent article concerne un tel problème, formulé en 1950 par Edward Nelson, alors jeune étudiant en mathématiques au fameux MIT, le Massachusetts Institute of Technology à Boston. En l’occurrence, les objets à colorier sont tous les points du plan. Quant à la contrainte imposée aux coloriages que l’on voudra déclarer admissibles... patience, patience. Commençons plutôt par revisiter un grand classique.
Colorions les cartes
Prenons une carte géographique, donnons-nous une palette de quelques couleurs, et attribuons à chaque pays une couleur à choix dans la palette. Comme pour une règle de jeu, imposons aux coloriages admissibles la contrainte suivante :
Contrainte. Deux pays voisins quelconques doivent avoir des couleurs distinctes.
Le problème est le suivant : combien de couleurs faut-il au minimum pour pouvoir colorier notre carte sous cette contrainte ?
On l’aura reconnu, il s’agit ici du fameux Problème des Quatre Couleurs, formulé au milieu du 19e siècle [1] et résolu par ordinateur dans les années 1970. Il était en effet conjecturé que quatre couleurs suffiraient pour n’importe quelle carte géographique.
Cela s’est révélé vrai, mais il a fallu attendre plus d’un siècle pour en avoir la confirmation. Et encore, l’histoire n’est pas finie : toutes les preuves connues font un appel massif à l’ordinateur. Or soyons réalistes, l’absence actuelle d’une preuve entièrement conceptuelle, sans recours à l’ordinateur, révèle de profondes lacunes à combler dans notre compréhension collective de ce problème.
Colorions tout ce qui bouge
Le site Images des Mathématiques offre déjà, dans cette même rubrique, plusieurs articles sur ce type de problèmes, qu’ils concernent le coloriage d’entiers naturels, de graphes, de carrés dans une grille rectangulaire, etc. Petit échantillon :
- Pythagore et mixité ;
- Les extraordinaires prédictions du Révérend Walker ;
- Les nombres de Schur, des centenaires pleins d’avenir ;
- Du Théorème de Ramsey à la Conjecture d’Erdős ;
- Matrices intercalaires et conjecture de Yuzvinsky.
Colorions les points du plan
Dans le présent problème, les objets mathématiques à colorier, ce sont tous les points du plan. Quant à la contrainte imposée comme règle du jeu, la voici.
Contrainte. Deux points quelconques à distance $1$ doivent avoir des couleurs distinctes.
Acceptons une mini-dose de terminologie, histoire d’éviter de trop longues phrases. On appellera coloriage admissible du plan tout coloriage des points du plan satisfaisant cette contrainte.
Le problème qui nous occupe ici peut maintenant se formuler ainsi.
Problème. Quel est le plus petit nombre possible de couleurs requis par un coloriage admissible du plan ?
Deux couleurs suffisent-elles ?
Non, bien sûr. Le plan regorge de triangles équilatéraux de côté $1$. Autrement dit, de triplets de points $A,B,C$ mutuellement à distance $1$ l’un de l’autre.
Donc, tout coloriage admissible du plan doit attribuer à $A,B,C$ des couleurs deux à deux distinctes. Bref, un tel coloriage requiert au moins trois couleurs.
Trois couleurs suffisent-elles ?
Contrairement à l’argument précédent, le plan ne contient pas quatre points mutuellement à distance $1$ l’un de l’autre. L’espace oui, mais le plan non. Du coup, à première vue, rien ne semble empêcher l’existence possible d’un coloriage admissible du plan à trois couleurs.
Patatras, cet espoir un peu naïf est vite refroidi. Voici en effet une configuration de sept points [2] qui empêche l’existence d’un coloriage admissible du plan à trois couleurs :
Petite explication : parmi ces sept points $A,B,C,D,E,F,G$, les paires de points à distance $1$ sont matérialisées par une arête les liant. Par exemple, le point $A$ a exactement quatre voisins à distance $1$, à savoir $B,E,C,F$. De même, le point $B$ a exactement trois voisins à distance $1$, à savoir $A,C,D$.
Il se trouve que tout coloriage admissible des sept points de cette configuration requiert au moins quatre couleurs.
Nous encourageons les lectrices et les lecteurs à relever un défi avant de poursuivre leur lecture : démontrer cette affirmation ! Si nécessaire, un petit coup de pouce, et une preuve complète, sont disponibles en cliquant sur les blocs déroulants ci-dessous.
Faut-il une infinité de couleurs ?
Au vu de ce qui précède, et comme le plan contient une infinité de points, on pourrait maintenant craindre que tout coloriage admissible du plan nécessite... une infinité de couleurs !
Fort heureusement, ce n’est pas le cas. Pour s’en convaincre, il suffit d’exhiber, comme nous allons le faire tout de suite, un coloriage admissible du plan à neuf couleurs seulement.
Neuf couleurs suffisent
Commençons par la configuration de $3 \times 3$ carrés ci-dessous, chacun étant colorié par l’une des neuf couleurs disponibles.
Le segment unité en noir indique l’échelle. On voit ainsi que les petits carrés ont des côtés de longueur $0,6$.
Pour colorier de façon admissible le plan tout entier, il suffit de le paver en répétant périodiquement cette configuration. Voici le résultat :
On a disposé quelques segments unité noirs ici ou là pour se convaincre que notre contrainte de coloriage est bien respectée.
Et maintenant ?
Revenons à la question de départ : quel est le plus petit nombre possible de couleurs requis par un coloriage admissible du plan ?
Nous avons vu que quatre couleurs sont nécessaires et que neuf couleurs suffisent. Bref, la réponse à cette question se situe quelque part entre $4$ et $9$ compris.
Cet encadrement est déjà très bien, bien sûr. Mais pour quiconque aspire à une réponse complète, ça reste un peu lâche. Peut-on l’améliorer, quitte à payer le prix d’efforts supplémentaires ? Eh bien oui ! Prêt à l’embarquement pour la suite ?
Sept couleurs suffisent
Mettons donc un peu plus de jus. Plutôt qu’avec des carrés, on va maintenant paver le plan avec des hexagones, et ce de telle façon que sept couleurs suffiront pour obtenir un coloriage admissible du plan [3].
Commençons par cette jolie fleur à sept hexagones et sept couleurs, et toujours un segment unité noir pour indiquer l’échelle.
Il suffit maintenant de paver le plan avec cette fleur en la répétant périodiquement. Voici ce que l’on obtient.
Là encore, quelques segments unité noirs sont placés à divers endroits pour nous convaincre de l’admissibilité de ce coloriage.
Voilà une vraie amélioration par rapport à l’encadrement donné plus haut, une nette réduction de l’incertitude. Nous savons désormais que le plus petit nombre de couleurs requis par un coloriage admissible du plan se situe quelque part entre $4$ et $7$ compris.
Ça, c’était l’état des connaissances sur ce problème depuis les années 1950. Et ça l’est resté jusqu’à il y a... quelques semaines.
Une avancée fantastique
Coup de tonnerre au printemps 2018, annoncé sur ce site le 20 avril [4] : un scientifique anglais du nom de Aubrey de Grey a construit une configuration de $1581$ points du plan pour laquelle tout coloriage admissible des points de cette configuration requiert au moins cinq couleurs [5].
Ce résultat est d’autant plus spectaculaire que Aubrey de Grey n’est pas un mathématicien, mais un ex-informaticien et un autodidacte en biogérontologie.
Voici un aperçu de sa remarquable configuration.
Résumons. L’état actuel des connaissances, c’est que le nombre minimal de couleurs requis par un coloriage admissible du plan se situe quelque part entre $5$ et $7$ compris. L’incertitude est désormais réduite à trois possibilités !
Pour réduire encore plus l’incertitude, jusqu’à la valeur exacte du nombre cherché, il faudrait au moins pouvoir répondre à la question suivante.
Un sous-problème
On a vu plus haut la construction d’un coloriage admissible du plan à $7$ couleurs. Peut-on faire de même avec une couleur de moins ? D’où le sous-problème suivant, que l’on propose ici même de désigner par le titre de cet article.
Problème des Six Couleurs. Existe-t-il un coloriage admissible du plan à $6$ couleurs ?
Pour répondre non, il faudrait construire, si cela est possible, une configuration finie de points du plan telle que tout coloriage admissible de ses points requière au moins $7$ couleurs. Dans ce cas de figure, le problème principal serait entièrement et définitivement résolu : le nombre minimal de couleurs requis par tout coloriage admissible du plan serait $7$, point final.
Par contre, pour répondre oui, il « suffirait » d’exhiber un tel coloriage à $6$ couleurs, certainement très fin et très subtil, comme on l’a fait plus haut pour $7$ couleurs avec des hexagones pavant le plan. Dans ce second cas de figure, il resterait une incertitude : le nombre minimal de couleurs requis par tout coloriage admissible du plan vaudrait soit $5$ soit $6$, et des efforts supplémentaires seraient alors requis pour déterminer laquelle de ces deux valeurs est la bonne.
Origine du problème
Officiellement, le nombre minimal de couleurs requis pour un coloriage admissible du plan s’appelle le nombre chromatique du plan.
L’origine du problème de déterminer ce nombre est longtemps restée obscure, ayant été attribuée à toute une palette de mathématiciens divers et variés. C’est à Alexander Soifer que l’on doit d’avoir mené l’enquête [6], en contactant la plupart des acteurs concernés et en épluchant les articles de recherche à ce sujet, et d’avoir déterminé sans le moindre doute que l’inventeur du problème était bien le jeune étudiant Edward Nelson en 1950. Voir aussi le volumineux et captivant livre historique de Soifer sur les problèmes mathématiques de coloriage [7], dont deux courts chapitres nous ont été bien utiles pour la rédaction de cet article.
Pour l’anecdote, c’est le problème original des Quatre Couleurs qui a inspiré ce nouveau problème à Edward Nelson. Il l’appelait le « Second Problème des Quatre Couleurs », parce qu’il pensait que le nombre chromatique du plan devait valoir $4$, pas plus. Comme relaté plus haut, cela vient juste d’être démenti par la fabuleuse configuration qu’Aubrey de Grey a découverte ce printemps.
Épilogue
Exceptionnellement pour cette rubrique, on se contentera de problèmes ouverts sans formuler de conjecture spécifique. Les avis des experts diffèrent trop quant à la valeur présumée du nombre chromatique du plan.
Les résultats rapportés ici se résument en l’affirmation que ce nombre vaut $5$, $6$ ou $7$. C’est l’état de l’art actuel sur la question.
On espère ne pas devoir attendre des dizaines d’années supplémentaires avant la prochaine réduction de cette incertitude. Alors, laissez votre imagination piloter vos crayons !
Les auteurs remercient Antonin Guilloux et Bruno Martin pour leur relecture attentive et leurs remarques très pertinentes.
Notes
[1] Là encore par un jeune étudiant en mathématiques, Francis Guthrie. Voir par exemple l’article Coloriages de cartes : mathématiques, droit, géographie et politique sur ce site.
[2] Découverte par Léo Moser dans les années 1960.
[3] Curieusement, ce coloriage admissible est dû au mathématicien suisse Hugo Hadwiger qui l’a décrit dans un autre contexte en... 1945, soit cinq ans avant la formulation du problème par Edward Nelson.
[4] Par Jérôme Germoni, responsable sur ce site de la rubrique Actualités. On remercie d’ailleurs Jérôme de nous avoir suggéré ce thème pour le présent article.
[5] Aubrey D.N.J. de Grey, The chromatic number of the plane is at least 5. Ce lumineux article de recherche est disponible librement comme prépublication sur arXiv.
[6] Alexander Soifer, Chromatic Number of the Plane : A Historical Essay, Geombinatorics 1 (1991), no. 3, 13-15.
[7] Alexander Soifer, The Mathematical Coloring Book : Mathematics of Coloring and the Colorful Life of Its Creators. Springer, New York 2009.
Partager cet article
Pour citer cet article :
Jean Fromentin, Shalom Eliahou — «Le Problème des Six Couleurs» — Images des Mathématiques, CNRS, 2021
Laisser un commentaire
Dossiers
Actualités des maths
-
20 janvier 2023Le vote électronique - les défis du secret et de la transparence (Nancy, 26/1)
-
17 novembre 2022Du café aux mathématiques : conférence de Hugo Duminil-Copin (Nancy et streaming, 24/11)
-
16 septembre 2022Modélisation et simulation numérique d’instruments de musique (Nancy & streaming, 22/9)
-
11 mai 2022Printemps des cimetières
-
3 mai 2022Comment les mathématiques se sont historiquement installées dans l’analyse économique (streaming, 5/5)
-
1er avril 2022Prix D’Alembert 2022 attribué à Jean-Michel Blanquer
Commentaire sur l'article
Le Problème des Six Couleurs
le 26 septembre 2018 à 11:25, par Pierre-Antoine Guihéneuf