Problème de Hadwiger-Nelson

Le problème fut énoncé par Edward Nelson en 1950^[1], et publié par Martin Gardner en 1960^[2]. Cependant, Hugo Hadwiger avait publié auparavant un résultat apparenté, montrant que pour tout revêtement du plan par cinq ensembles fermés isométriques, il existe deux points séparés d'une unité et situés dans le même ensemble^[3] ; il mentionna le problème sous sa forme exacte dans une publication ultérieure^[4]. En 2008, Alexander Soifer a publié une étude approfondie du problème et de son histoire^[5].

En termes de théorie des graphes, la question peut s'énoncer ainsi : soit G le graphe distance-unité du plan, c'est-à-dire le graphe dont les sommets sont tous les points du plan (euclidien) et dont les arêtes relient deux points si et seulement si leur distance vaut 1. Le problème de Hadwiger-Nelson est alors de déterminer le nombre chromatique de G, c'est pourquoi ce problème est souvent décrit comme la question de « déterminer le nombre chromatique du plan ». Le théorème de De Bruijn-Erdős montre qu'en admettant l'axiome du choix, la question revient à déterminer le plus grand nombre chromatique d'un graphe planaire distance-unité fini. La question est aussi équivalente à déterminer le plus petit entier ${\displaystyle n}$ pour lequel il existe une partition du plan ${\displaystyle (C_{1},C_{2},\dots ,C_{n})}$ telle qu'aucun des ${\displaystyle C_{i}}$ ne contienne de couples de points séparés d'une unité^[6] ; sous cette forme, on peut exiger que les ${\displaystyle C_{i}}$ aient des propriétés géométriques supplémentaires, simplifiant le problème, comme analysé ci-dessous.

La façon la plus simple d'obtenir un majorant de la solution consiste à exhiber une coloration du plan satisfaisant à l'énoncé ; de même, un minorant ${\displaystyle k}$ est obtenue en exhibant un contre-exemple, c'est-à-dire un graphe distance-unité de nombre chromatique ${\displaystyle k}$.

Jusqu'en 2018, on n’avait pas découvert de graphe distance-unité de nombre chromatique supérieur à 4. Le premier exemple d’un graphe 4-chromatique fut découvert en 1961 par les frères William et Leo Moser, un graphe à 7 sommets appelé le fuseau de Moser. Un autre graphe (à 10 sommets) fut découvert à peu près en même temps par Solomon W. Golomb, mais il ne le publia pas immédiatement^[7].

Cependant, en avril 2018, des graphes de nombre chromatique 5 (comportant plusieurs milliers de sommets, le plus petit a 1581 sommets) ont été découverts par Aubrey de Grey et contrôlés par ordinateur^[8],[9].

Le majorant 7 provient de l'existence d'un pavage du plan par des hexagones réguliers de diamètre un peu inférieur à 1, que l'on peut colorier périodiquement en 7 couleurs (cette coloration est connue sous le nom de carte de Heawood^[10]), ce qui fut remarqué par John R. Isbell^{[Quand ?][11]}.

Il a souvent été remarqué que le problème de Hadwiger-Nelson est non seulement d'énoncé simple, mais que les meilleurs encadrements connus (jusqu'en 2018) reposaient sur des exemples et contre-exemples tout à fait élémentaires, rendant exaspérante l'absence de progrès faits vers sa résolution en plus d'un demi-siècle^[5],[12].

Le problème se généralise facilement aux dimensions supérieures. Comme pour le plan, le « nombre chromatique de l'espace » (à trois dimensions) n'est pas connu, mais on sait qu'il est compris entre 6 et 15^[13].

On peut aussi imposer aux ensembles de points d'une même couleur de devoir satisfaire une condition supplémentaire^[14]. Cela rend certaines colorations inacceptables, ce qui peut augmenter le nombre de couleurs requises. Ainsi, si l'on demande que tous ces ensembles soient mesurables au sens de Lebesgue, on savait (longtemps avant les découvertes de 2018) que cinq couleurs au moins sont nécessaires. Si l'on demande que les ensembles soient formés de régions ayant pour frontières des courbes de Jordan, six couleurs au moins sont nécessaires^[15].

Il est enfin possible de se limiter à certains sous-ensembles de points du plan, par exemple aux points à coordonnées rationnelles ; on dispose souvent de résultats exacts dans ce cas^[10].

• Théorème des quatre couleurs
• Nombre de Hadwiger