Problème de Hadwiger-Nelson

De testwiki
Aller à la navigation Aller à la recherche
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 Modèle:Lien, 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 Modèle:Citation. 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 (C1,C2,…,Cn) telle qu'aucun des Ci ne contienne de couples de points séparés d'une unité[6] ; sous cette forme, on peut exiger que les Ci aient des propriétés géométriques supplémentaires, simplifiant le problème, comme analysé ci-dessous.

Bornes

Le graphe de Solomon W. Golomb, un graphe distance-unité 4-chromatique ayant dix sommets.

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 Modèle:Date, 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]Modèle:,[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. IsbellModèle: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]Modèle:,[12].

Variantes du problème

Le problème se généralise facilement aux dimensions supérieures. Comme pour le plan, le Modèle:Citation (à 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].

Voir aussi

Notes

Modèle:Références

Références

Liens externes

Modèle:Portail

  1. ↑ Modèle:Harvsp
  2. ↑ Modèle:Harvsp
  3. ↑ Modèle:Harvsp
  4. ↑ Modèle:Harvsp
  5. ↑ 5,0 et 5,1 Modèle:Harvsp, chapitres 2 et 3.
  6. ↑ Modèle:Harvsp
  7. ↑ Modèle:Harvsp, p. 19.
  8. ↑ Aubrey D.N.J. de Grey, The chromatic number of the plane is at least 5 Modèle:En.
  9. ↑ David Madore, Le progrès récent sur le problème de Hadwiger-Nelson.
  10. ↑ 10,0 et 10,1 Modèle:Harvsp
  11. ↑ Modèle:Harvsp
  12. ↑ Modèle:Harvsp
  13. ↑ Modèle:Harvsp; Modèle:Harvsp.
  14. ↑ Voir, par exemple, Modèle:Harvsp.
  15. ↑ Modèle:Harvsp, pp. 557–563; Modèle:Harvsp
  16. ↑ Modèle:Harvsp ; voir aussi Modèle:Harvsp pour une autre démonstration d'un résultat analogues.
Récupérée de "https://fr.wiki.beta.math.wmflabs.org/w/index.php?title=Problème_de_Hadwiger-Nelson&oldid=11844"