La couleur du plan
Il existe un théorème ultra connu qui dit quelque chose comme : "toute carte bla bla bla quatre couleurs". Avant de devenir "théorème des quatre couleurs" en 1976, il est resté "conjecture des quatre couleurs" pendant une bonne douzaine de décennies.
Il faut donc lui trouver un remplaçant pour le titre de "conjecture de la théorie des graphes qui implique des crayons de couleurs". Et pourquoi pas le problème de Hadwiger-Nelson ? On connaît aussi ce problème sous le nom de "problème du nombre chromatique du plan" ou, plus prosaïquement, "conjecture des quatre, cinq, six ou sept couleurs".
Le problème du nombre chromatique du plan
Un graphe, c'est des points (les sommets) reliés entre eux (par des arêtes). On peut les représenter graphiquement, ou en listant ses sommets et ses arrêtes.
Quelque exemples de graphes
- Un graphe planaire (ici, W8) : ses arêtes ne se croisent pas.
- Un graphe unitaire (ici M, le graphe de Moser) : toutes ses arêtes sont de la même longueur.
- Un graphe infini (le pavage triangulaire). Et en plus, il est unitaire.
Face à un graphe, le mathématicien ne peut s'empêcher de se poser une question : quel est son nombre chromatique de ce graphe ? Autrement dit, si on cherche à colorier les sommets du graphe de façon à ce que deux sommets reliés entre eux ne soient pas de la même couleur, de combien de feutres allons-nous avoir besoin ?
On dit donc que le nombre chromatique d'un graphe G, noté χ(G), vaut K si il faut au moins K couleurs pour le colorier et qu'il peut être colorié avec K couleurs.
Quelques colorations de graphes
- W8 demande au moins 4 couleurs (comme le dit le théorème éponyme, les graphes planaires demandent au plus 4 couleurs)
- M demande au moins 4 couleurs (il n'y a pas encore de théorème équivalent au théorème des 4 couleurs pour les graphes unitaires)
- Le nombre chromatique du pavage triangulaire est de 3.
Le roi des graphes planaires unitaires, c'est le graphe U², qui réunit en lui tous les graphes unitaires imaginables : les sommets de U², ce sont les points du plan ; deux sommets sont reliés entre eux dans U² s'ils sont séparés d'une distance de 1. Ce graphe est infini et plutôt compliqué à dessiner, mais il n'en est pas moi intéressant.
Mais quel est son nombre chromatique ?! C'est ça, le problème du nombre chromatique du plan :
Combien faut-il au minimum de couleurs pour colorier l'ensemble des points du plan de façon à ce que deux points distants d'une unité ne partagent pas la même couleur ?
Le problème de Hadwiger-Nelson
La première formulation du problème remonte à 1950, dans les écrits de l'américain Edward Nelson, mais ne sort de l'ombre qu'en 1960, quand Martin Gardner en parle dans le Scientific American. Les prémisses du problème apparaissent en 1945 chez l'allemand Hugo Hadwiger. Grand fan de la question, Paul Erdös a passé beaucoup de temps à en faire du lobbyisme, sans succès.
Bref. Pour trouver le nombre chromatique de U², on peut procéder à tâtons :
- en cherchant un graphe unitaire ayant le plus grand nombre chromatique possible (Puisque tout graphe unitaire se retrouve dans U², on obtient une borne inférieure pour χ(U²))
- en cherchant une coloration du plan demandant le moins de couleurs possibles (ce qui donne une borne supérieure pour χ(U²))
Avec un peu de chance, les deux bornes correspondront.
Pour la borne inférieure, on peut reprendre M, le graphe de Moser. Puisque χ(M)=4, on trouve 4 ≤ χ(U²). Existe-t-il des graphes unitaires (finis) avec un nombre chromatique plus grand ?... Ça, on aimerait bien le savoir ! A priori, non, mais les tentatives de preuves ont toutes échoué... En fait, les deux problèmes sont équivalents, si on accepte l'axiome du choix (par le théorème de De Bruijn–Erdős, 1951).
Pour la borne supérieure, on peut prendre un pavage hexagonal. Ce pavage, on peut le colorier avec 7 couleurs sans avoir de problèmes. Autrement dit, χ(U²) ≤ 7.
Une 7-coloration de U².
Les points du cercle sont les points liés au point rouge.
Finalement, χ(U²) est quelque part entre 4 et 7. Mais pourquoi, depuis 60 ans, on n'arrive pas à se décider entre 4, 5, 6 ou 7 ?!
On peut regarder ce que donne le problème en dimension 3 : la marche de manœuvre est encore plus grande, puisque, cette fois-ci, 6 ≤ χ(U3) ≤ 15.
On peut aussi imposer des conditions sur le coloriage. Par exemple, si on demande à ce que les composante connexes d'une couleur soient convexes, on trouve 6 ≤ χ(U²) ≤ 7. Si on demande à ce qu'elles soient Lebesgue-mesurables, on a cette fois-ci 5 ≤ χ(U²) ≤ 7.
La conjecture des quatre, cinq, six ou sept couleurs
Et si, en fait, le problème n'avait pas qu'une seule solution ? Par exemple, χ(U²) serait égal à 4 dans un univers, et à 7 dans un univers parallèle ? Ben oui, pourquoi pas ?...
Malheureusement, ce n'est pas si débile que ça... Si la somme des angles d'un triangle quelconque dépend de la géométrie que l'on considère (euclidienne, hyperbolique, sphérique...), pourquoi χ(U²) ne dépendrait pas des axiomes de la théorie des ensembles que l'on utilise ?
Une triste découverte a été faite en 2003 par Shelaha et Soifer : l'existence d'un graphe dont le nombre chromatique dépend des axiomes utilisés. Si on garde AC, l'axiome du choix classique, ce graphe demande 2 couleurs. Si on remplace l'axiome du choix classique par l'axiome des choix dépendants et l'axiome LM (DC+LM), il faudra une infinité (non dénombrable) de couleurs...
[Pour ceux qui se posent la question, le graphe en question est celui dont les sommets sont les nombres réels et deux points x et y sont liés si x-y-√2 est un nombre rationnel.
Pour montrer que 2 couleurs suffisent, on considère la relation d'équivalence suivante : x~y si x-y=p/q +k√2, avec p,q,k entiers. Avec l'axiome du choix, on choisit dans chaque famille d'équivalence un représentant xi. Ainsi, dans la famille i, un élément x s'écrit sous la forme x=xi+p/q+k√2. Si k est pair, x est bleu, sinon, il est rouge. On peut ensuite montrer que cette coloration fonctionne.
Pour montrer que n couleurs ne suffisent pas, on considère les n paquets de points de même couleur. L'axiome LM dit que tout ces ensembles ont une mesure (nulle ou positive). On peut montrer que si un de ces paquets a une mesure non nulle, alors deux point sont liés (et paf, contradiction). Donc tous les paquets ont une mesure nulle, donc ℝ aussi et re-paf, contradiction.]
Avant cette découverte, les deux théories (AC et DC+LM) se battaient essentiellement sur l'existence ou la non-existence d'ensemble non mesurables, ce qui autorise ou non le paradoxe de Banach-Tarski. Le graphe de Shelaha-Soifer montre que les deux théories peuvent aussi se battre sur des sujets un peu plus concrets (et qu'il y a un moment où il va falloir réfléchir sur le sens profond des différents systèmes d'axiomes de la théorie des ensembles, pour trouver lequel d'entre eux est le plus naturel).
Le graphe de Shelaha et Soifer est loin de ressembler à U², mais le progrès est en marche. En 2009, M. Payne trouve (entre autres) un exemple de graphe unitaire ayant un nombre chromatique se baladant entre 3 et 5...
Contrairement au problème des quatre couleurs ("le plus gros pétard mouillé de l'histoire des mathématiques"), le problème de Nelson, lui, contribue à de véritables avancées philosophico-mathématiques ! La révolution ensembliste est en marche.
Sources :
Hadwiger–Nelson problem, sur Wikipédia (pour une encore plus grande bibliographie)
Coloriages irréels, Pour la science n°328, février 2005 (avec de vraies explications sur ce que sont les axiomes AC, DC et LM)
Axiom of choice and chromatic number of the plane, le papier de Shelaha et Soifer (avec de vraies démonstrations à l'intérieur)
Unit distance graphs with ambiguous chromatic number, le papier de Peyne.