Coloration du plan en sept couleurs, et dessin du graphe de Moser, exhibant des bornes supérieures et inférieures pour le problème de Hadwiger–Nelson.
En théorie géométrique des graphes(en), le problème de Hadwiger-Nelson, posé par Hugo Hadwiger et Edward Nelson vers 1950, consiste à déterminer le nombre minimum de couleurs nécessaires pour colorier le plan de telle sorte que deux points séparés d'une unité soient toujours de couleurs distinctes. La réponse est inconnue, mais est l'un des trois entiers 5, 6 ou 7 ; la valeur exacte pourrait d'ailleurs dépendre de l'axiome du choix.
Historique
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 congruents, 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].
Énoncé du problème
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 n pour lequel il existe une partition du plan telle qu'aucun des ne contienne de couples de points séparés d'une unité[6] ; sous cette forme, on peut exiger que les 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 une borne supérieure à la solution consiste à exhiber une coloration du plan satisfaisant à l'énoncé ; de même, une borne inférieure k est obtenue en exhibant un contre-exemple, c'est-à-dire un graphe distance-unité de nombre chromatique 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 , 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].
La borne supérieure 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 meilleures bornes connues (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].
Variantes du problème
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. Il existe des modèles de la théorie des ensembles (par exemple le modèle de Solovay) dans lesquels tous les sous-ensembles du plan sont mesurables, et donc dans ces modèles le nombre chromatique du plan est au moins cinq ; c’est ce résultat qui fait penser que la réponse pourrait dépendre de l’axiome du choix[15]. 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[16].
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].
(en) N. G. de Bruijn et P. Erdős, « A colour problem for infinite graphs and a problem in the theory of relations », Nederl. Akad. Wetensch. Proc. Ser. A, vol. 54, , p. 371–373.
(en) K. B. Chilakamarri, « The unit-distance graph problem: a brief survey and some new results », Bull Inst. Combin. Appl., vol. 8, , p. 39–60.
(en) Hugo Hadwiger, « Überdeckung des euklidischen Raumes durch kongruente Mengen », Portugal. Math., vol. 4, , p. 238–242.
(en) Hugo Hadwiger, « Ungelöste Probleme No. 40 », Elem. Math., vol. 16, , p. 103–104.
(en) Tommy R. Jensen et Bjarne Toft, Graph Coloring Problems, Wiley-Interscience Series in Discrete Mathematics and Optimization, , 150–152 p..
(en) Michael S. Payneg, « Unit distance graphs with ambiguous chromatic number », The Electronic Journal of Combinatorics, (lire en ligne)
(en) Radoš Radoičić et Géza Tóth, Discrete and Computational Geometry : The Goodman–Pollack Festschrift, vol. 25, Berlin, Springer, coll. « Algorithms and Combinatorics », , 695–698 p. (DOI10.1007/978-3-642-55566-4_32, MR2038498, lire en ligne), « Note on the chromatic number of the space ».
(en) Alexander Soifer, The Mathematical Coloring Book : Mathematics of Coloring and the Colorful Life of its Creators, New York, Springer, (ISBN978-0-387-74640-1),
