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 !