5 nuances d’Aubrey de Grey

Drapeau vert : Cet article ne demande aucune connaissance mathématique particulière


Pas besoin d’être un pro des mathématiques pour s’amuser avec des graphes. Avec seulement quelques points et des arêtes, il est possible de concocter des problèmes au apparences simplistes qui résistent pourtant plusieurs décennies.

Récemment, c’est le problème du nombre chromatique du plan qui a fait parler de lui, puisqu’un certain Aubrey de Grey, biologiste de métier, a apporté une avancée significative à cette question vieille de plusieurs décennies : de combien de couleurs a-t-on besoin pour colorier le plan ?

Tout ceci semble un peu flou, alors apportons sans plus tarder un peu de précisions, si vous le voulez bien.

Colorier un graphe

Un graphe, comme mentionné dans cette introduction, c’est un ensemble de points – appelés sommets – dont certains sont reliés entre eux par des traits, des arêtes. Les graphes sont très utiles pour représenter certaines situations : on peut penser au réseau du métro, à un arbre généalogique ou à un graphe d’amis sur les réseaux sociaux.

Une fois devant un graphe, on peut alors se donner à toutes sortes de jeu. Celui qui nous intéresse aujourd’hui concerne le coloriage : à chaque sommet du graphe, je souhaite assigner une couleur, mais en faisant cela, je ne veux pas que deux sommets reliés par une arête aient la même couleur.

Naturellement, en bon mathématicien radin que je suis, je veux utiliser le moins de couleurs possibles pour réaliser mon coloriage – sans pour autant déroger à la règle instaurée deux lignes plus haut ! – : dans ce cas, le nombre de couleurs utilisé s’appellera nombre chromatique du graphe.

Graphe de Moser. Son nombre chromatique est de 4 : 3 couleurs ne suffisent pas à le colorier correctement.

Trouver le nombre chromatique d’un graphe n’est pas une affaire aisée : il faut, en gros, essayer tous les coloriages de ce graphe et déterminer le meilleur, ce qui peut prendre beaucoup de temps lorsque le graphe comporte beaucoup de sommets et – surtout- beaucoup d’arêtes.

Et ça le devient encore plus lorsque ces deux ensembles sont… infinis !

Graphe unitaire

Pour notre coloriage, nous allons choisir un graphe un peu particulier. Comme sommets de ce graphe, nous considérerons tous les points du plan. Tous. Sans exception. Imaginez une feuille blanche qui s’étend à l’infini dans toutes les directions, choisissez un point dessus. Gagné, il est dans le graphe !

Reste alors à décrire les arêtes : deux sommets de ce graphe seront reliés si la distance qui les sépare vaut 1 (1m, 1 cm, 1 année-lumière, que sais-je, vous prendrez bien l’unité qui vous convient). Cela revient à tracer un cercle de rayon 1 autour de chaque point du plan, et de relier tous les points de ce cercle au centre. Autant dire que ça en fait des arêtes.

La question est donc la suivante : quel est le nombre chromatique de ce graphe ? De combien de couleurs ai-je besoin, au minimum, pour le colorier sans que deux sommets voisins aient la même couleur ? En bref, quel est le nombre chromatique du plan ?

Une autre manière de s’imaginer ce problème est le suivant : si je possède un bâton de longueur 1, il faut trouver un coloriage du plan tel que, où que je pose mon bâton, ses deux extrémités se trouvent sur des points de couleurs différentes.

Ce problème, appelé problème de Hadwiger-Nelson, a été pour la première fois mentionné en 1950, avant d’être relayé par Martin Gardner dix ans plus tard. Et pourtant, il résiste encore et toujours, non pas à l’envahisseur, mais au commun des mortels.

Rassurez-vous, tout n’est pas aussi noir, et nous pouvons tout de même formuler quelques résultats.

D’abord, le nombre chromatique du plan ne peut excéder 7 : nous devons ce résultat à John Isbell qui s’est inspiré d’un pavage hexagonal pour établir cette borne supérieure.

En plaçant une baguette de longueur 1 sur ce pavage, ses deux extrémités se trouvent forcément sur deux couleurs différentes.

Isbell utilise des hexagones de diamètre légèrement inférieur à 1 et les colorie de 7 couleurs différentes. De cette manière, peut importe le point que je choisis, tous les points se trouvant à distance 1 de celui-ci se trouvent dans des zones d’une couleur différente à la première.

Graphe de Golomb

Graphe de Golomb, impossible à colorer avec seulement 3 couleurs

Ensuite, on sait depuis quelques années que le nombre chromatique du plan est d’au moins 4 : il existe en effet certains graphes unitaires, comme le graphe de Moser ou le graphe de Colomb, qui ne peuvent être coloriés en utilisant seulement 3 couleurs.

Ne restent alors que 4 options pour notre nombre chromatique : 4, 5, 6 ou 7… Et voilà, l’histoire s’est arrêtée là pendant un bon bout de temps, jusqu’à ce que le précédemment mentionné Aubrey de Grey ne vienne mettre son nez dans cette affaire.

Le graphe de De Grey

Dans son article intitulé « The chromatic number of the plane is at least 5« , De Grey annonce la couleur (ah, ah !) : le nombre chromatique du plan est d’au moins 5, et pour le montrer, De Grey a construit un graphe impossible à colorer avec seulement 4 couleurs.

De Grey commence par observer un graphe, qu’il appelle H, ayant la forme d’un hexagone régulier avec un point en son centre. Le nombre chromatique de ce graphe est 3, mais ce n’est pas ce qui nous intéresse ici. De Grey remarque en effet que si on utilise au plus 4 couleurs, certaines colorations de ce graphe présentent un triangle monochromatique, alors que d’autres non.

Colorations du graphe H. Les deux versions du haut possèdent au moins un triplet de points de la même couleur – trois bleus, en l’occurrence. Image tirée de l’article de De Grey.

Partant de ce point, De Grey va alors construire deux graphes, chacun d’eux contenant au moins une copie de H. Concentrez-vous bien, car même si ce n’est pas très compliqué, il y a de forts risques de se perdre là-dedans.

  • Le premier graphe, appelé L – oui, c’est intime tout ça – est obtenu en dupliquant le graphe H de départ. Au final, ce graphe L contient 52 copies du graphe H, mais le plus important est que, si l’on essaye de colorier L à l’aide de 4 couleurs, alors au moins une copie de H de ce grand graphe présentera un triplet de point de même couleur.

Construction du graphe L à partir du graphe H

  • Le second graphe, appelé M, est une extension du graphe H – on rajoute des sommets et des arêtes, d’une façon un peu intelligente tout de même – qui vérifie une propriété contraire : si j’essaye de colorier M avec 4 couleurs, alors le graphe H ne contiendra cette fois aucun triplet de la même couleur.

Le graphe M de De Grey compte 1345 sommets et 8268 arêtes. Autant dire qu’il est impossible de vérifier à la main tous les coloriages possibles.

Bref, nous avons deux graphes L et M. Chacun peut être colorié avec 4 couleurs, mais le premier implique la présence d’un triplet monochromatique de points sur les copies de H, alors que c’est le contraire pour ce second graphe. Il n’y a plus qu’à les combiner ensemble et faire marcher la contradiction ! Le graphe obtenu ne peut pas être colorié avec seulement 5 couleurs.

Le graphe obtenu possède alors 20425 sommets, autant dire que ce n’est pas un petit graphe ! Heureusement, il est possible de retirer certains sommets pour aboutir à un graphe plus petit – 1581 puis 1577 sommets -, sans que celui-ci ne devienne colorable avec 4 couleurs pour autant.

Le graphe de De Grey à 1581 sommets. Source : Aubrey de Grey

On peut alors vérifier à l’aide d’un programme que 4 couleurs ne suffisent à colorer ce graphe : cela prend à peine 5 heures et demis avec du bon matériel, tandis que colorier ce graphe avec 5 couleurs prend moins d’une seconde.

Bref, le nombre chromatique du plan est au moins 5. C’est peut-être 5, 6 ou 7, mais 4 a disparu de la liste des choix.

Depuis la publication de l’article, un projet Polymath a d’ailleurs été lancé pour trouver des graphes toujours plus petits mais impossible à colorier avec seulement 4 couleurs. Ainsi, Marijn Heule est parvenu à réduire le nombre de sommets à 826.

Graphe de Marijn Heule, à 826 sommets. Source : Marijn Heule

En outre, ce projet a deux autres objectifs :

  • d’abord, voir si cette méthode peut s’étendre à la découverte de graphes unitaires qui ne peuvent être colorié avec 6 couleurs ou à des problème liés, comme le nombre chromatique des espaces de dimensions supérieurs
  • mais aussi réduire autant que possible l’utilisation de l’ordinateur dans cette preuve : les mathématiciens sont très attachés aux démonstrations « à la main ».

En bref, il y a encore du travail, mais cette avancée en appellera peut-être de nouvelles dans les mois à venir ?

Compléments et références

  • Soifer, A. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators
  • De Grey, A. The Chromatic Number of The Plane is At Least 5
  • L’article de Quanta Magazine qui parle de cette découverte.
  • Deux articles sur le blog Short, Fat Matrices : ici, avec notamment les temps de calcul pour la coloration de graphe et , pour la description de la méthode
  • Le projet Polymath et les graphes sont décrits à cette adresse
  • Un article sur le blog de Gil Kalai, Combinatorics and more
  • En français cette fois, Eljj avait fait un article de blog sur la couleur du plan, c’est à cette adresse.
  • Un article sur le blog de David Madore qui traite également de la coloration du plan.
Cet article, publié dans Actualité, Conjectures et théorèmes, est tagué , , , . Ajoutez ce permalien à vos favoris.

Un commentaire pour 5 nuances d’Aubrey de Grey

  1. Ping : Aubrey de Grey: The chromatic number of the plane is at least 5 | Combinatorics and more

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion /  Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s