Coloriage (assez difficile)
Imaginez que vous attribuiez une couleur à chaque point du plan. De combien de couleurs avez-vous besoin pour que deux points quelconques, distants de 1 cm, aient toujours deux couleurs différentes ?
Ce nombre de couleurs est appelé nombre chromatique du plan.
Raisonnons un peu pour essayer de le déterminer.
Il faut au moins deux couleurs : les extrémités d'un segment de 1 cm doivent en effet avoir des couleurs différentes.
Il en faut même au moins trois puisque les sommets d'un triangle équilatéral de 1 cm de côté doivent aussi avoir des couleurs différentes.
Si vous observez le graphe en début de cet article vous serez persuadé qu'il en faut au moins quatre.
Et si vous imaginez un réseau d'hexagones réguliers coloriés de diamètre un peu inférieur à 1 cm, disposés sur le plan comme des tommettes sur le sol, vous serez persuadé que 7 couleurs suffisent à attendre votre objectif.
Entre 1945, où le problème a été soulevé, et 2018, on n'a rien su de plus sur le nombre chromatique du plan : il est entre 4 et 7.
En 2018, Aubrey de Grey a construit un graphe de 1581 sommets qui ne pouvait pas être colorié avec seulement 4 couleurs. Cette performance est d'autant plus remarquable que de Grey n'est pas un mathématicien professionnel.
Par la suite, le graphe a été simplifié à 861 nœuds.
Ce nombre chromatique vaut donc 5, 6 ou 7 mais on ne le connaît toujours pas.
On ne sait même pas si on peut connaître sa valeur.
Et pourtant... ce nombre existe !
je vous laisse méditer là-dessus...
Pour aller plus loin :
Il n'est pas précisé combien d'arrête chaque sommet peut avoir ?
RépondreSupprimerLe graphe qui sous-tend la notion de nombre chromatique est infini. Ses sommets sont tous les points du plan et ses arêtes sont tous les segments de longueur 1. Ainsi, un point est relié à autant d'autres sommets qu'il y a de points sur le cercle de rayon 1 dont il est le centre.
RépondreSupprimerPour trouver un minorant m au nombre chromatique, bien entendu, il suffit de considérer un sous-graphe fini tel que celui au début de l'article et montrer qu'il faut au moins m couleurs pour le colorier.