Comments on Le piège de Hadwiger-Nelson

Nick (2016-08-03T21:19:02Z)

Bon, je conteste quand même l'idée que ce problème soit le plus simple à formuler. Des questions comme « est-ce que π^π^π^π est un entier ? » ou « 33 est-il une somme de trois cubes ? » me paraissent plus simples (et cacher moins de subtilités, notamment la deuxième).

Fier d'avoir ... (2012-05-04T03:23:21Z)

@Ruxor:
Merci pour tes explications qui sont très claires.

Je vais encore râler contre la WP, mais leur présentation donne vraiment l'impression que ce graphe est avant tout un objet géométrique. C'est très net à la rubrique "construction", où la construction est d'abord présentée comme géométrique. Même remarque pour l'article "unit distant graph", d'ailleurs.

Je pense qu'évidemment, cela ne posera pas de problèmes à un mathématicien, conscient de la possible ambiguïté de nature des graphes, mais est-ce que la WP s'adresse en priorité à des mathématiciens ?

Ruxor (2012-05-03T22:24:54Z)

@W: Oui, c'est correct.

W (2012-05-03T22:07:45Z)

@Fier:

Dans la définition du problème, il assez clair qu'on veut associer à chaque point une unique couleur. (Mais dans un autre problème on aurait pu en décider autrement. On se pose les problèmes qu'on veut.)

En dimension 1, il faut et il suffit que pour tout point A, les points A-1 et A+1 soient de l'autre couleur, donc que les points A-2 et A+2 soient de la première couleur, donc que les points A-3 et A+3 soient de l'autre, etc.

Autrement dit, il faut et il suffit que le coloriage soit périodique de période 2, et que si on prend une période [x,x+2], ses 2 moitiés soient le négatif l'une de l'autre. Encore autrement dit, le coloriage est "antipériodique de période 1".

Concrètement, on choisit un segment [x,x+1[, on le colorie vraiment comme on veut, et après on le duplique à gauche et à droite comme ceci : négatif-positif-négatif-positif-…

Par exemple, dans [0,1[, je colorie d'une couleur les nombres rationnels et de l'autre couleur les nombre irrationnels, puis dans [1,2[, le contraire, etc. Ça marche, même si on ne peut pas le représenter par un dessin.

(Confirmation, Ruxor ?)

Ruxor (2012-05-03T21:03:13Z)

@Oudeis: Oui, il y a ambiguïté. Il n'est pas rare que les définitions mathématiques soient assez floues sur le fait de savoir si tel objet est la donnée de tel machin muni de telle structure ou seulement de tel machin sur lequel il *est possible* de mettre telle structure. Dans beaucoup de cas ça n'a absolument aucune importance, donc on ne fait pas attention. Mais il peut arriver que ce soit un point crucial, et évidemment, un bon matheux doit savoir reconnaître si ça l'est ou pas pour la démonstration qu'on est en train de considérer.

En l'occurrence, je dirais qu'un unit-distance graph est un graphe abstrait tel qu'*il est possible* de trouver pour chaque sommet du graphe un point dans le plan de manière que deux points associés à des sommets reliés par une arête soient à distance 1. En général, le distinguo n'est pas important parce que les unit-distance graphs intéressants ont tendance à être rigides, c'est-à-dire qu'il n'y a de toute façon (à déplacement près) qu'une seule façon de les réaliser de cette manière, et c'est le cas du fuseau de Moser.

La définition de Wikipédia dit : « a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points by an edge whenever the distance between the two points is exactly one », on remarquera bien que, si on fait attention, elle définit bien un unit-distance graph comme le graphe *formé* par la collection des points, et pas comme la collection des points eux-mêmes. En revanche, il y a une autre ambiguïté dans la définition, qui peut être plus gênante, c'est de savoir si « whenever » correspond à une condition nécessaire et suffisante ou seulement nécessaire : par exemple, si je prends un hexagone régulier de côté 1 et son centre (soit 7 points au total, le point central étant relié aux 6 autres qui sont reliés entre eux cycliquement), j'obtiens certainement un unit-distance graph (le « wheel graph » ayant 7 sommets et 12 arêtes), mais ai-je le droit de retirer une arête et d'appeler quand même le graphe résultant (ayant 7 sommets et 11 arêtes) un unit-distance graph ? Wikipédia remarque l'ambiguïté (dans la section « Subgraphs of unit distance graphs »), ce qui est bien.

Il ne faut pas s'imaginer que la terminologie mathématique est toujours sans ambiguïté. En général les gens rédigent quand même assez bien pour qu'on comprenne de quoi ils parlent (ou qu'on comprenne que ça n'a pas d'importance…).

Oudeis (2012-05-03T20:05:26Z)

@Ruxor:
Je ne suis pas mathématicien, donc je ne mets nullement en doute ce que tu dis, mais j'ai l'impression que vous autres, mathématiciens, employez parfois des formules ambiguës pour qui ne connaît pas précisément ce dont vous parlez.

Par exemple, ici, tu dis que le fuseau de Moser est un graphe abstrait, alors que la fiche WP dit que le fuseau de Moser est un « unit distant graph », c'est-à-dire un graphe constitué de points dans le plan (géométrique, donc ?).

Bien sûr, tu nuances dans ton dernier paragraphe : il peut arriver, dis-tu, qu'on ne soit pas tout à fait d'accord sur les propriétés définitoires d'un objet mathématique, comme c'est apparemment le cas pour la WP et toi à propos du « fuseau de Moser ». Cependant, je te fais plus confiance qu'à WP et je pense qu'il faudrait modifier la fiche qui ne définit ce fuseau que comme un graphe géométrique (alors, d'ailleurs, que les propriétés données dans l'encadré de droite ne concernent pas les distances). Ou alors c'est leur définition de « unit distant graph » qui est fausse et il faut entendre par là « graphe (abstrait) *pouvant* être représenté dans le plan par une collection de points etc. » ?

Tout cela me rappelle la différence entre vecteur et bipoint.

Ruxor (2012-05-03T13:14:22Z)

@Fier d'avoir…: Ce que j'appelle un « graphe abstrait » (et c'est ce qu'un mathématicien veut généralement dire quand il parle d'un graphe tout court), c'est une structure avec des sommets et des arêtes entre les sommets mais sans que les sommets soient considérés comme des points du plan (ou de l'espace, ou de quoi que ce soit), donc sans qu'ils aient une position. En tant que graphe abstrait, le fuseau de Moser, c'est donc un graphe avec sept sommets qu'on pourrait arbitrairement appeler A,B,C,D,E,F,G avec des arêtes AB, AC, BC, BD, CD, AE, AF, EF, DG, EG, FG, et c'est bien ce qui est représenté sur l'article Wikipédia <URL: http://en.wikipedia.org/wiki/Moser_spindle > (précisément, <URL: http://en.wikipedia.org/wiki/File:Moser_spindle_pseudotriangulation.svg >).

Maintenant, il se trouve que ce graphe abstrait peut être représenté par sept points A…G dans le plan de telle sorte que deux points reliés par une arête soient toujours à distance 1 : on dit que c'est un graphe représentable par distance 1 dans le plan (« unit-distance graph »). Et si on fait ça, on obtient la figure que j'ai tracée dans mon entrée. Mais là c'est plus qu'un graphe abstrait, c'est un graphe géométrique dans le plan.

Tout ça relève de la question parfois épineuse de décider ce que ça veut dire au juste que deux objets mathématiques soient « le même », et de quelles données on considère comme faisant partie de l'objet ou pas.

Fier d'avoir ... (2012-05-03T01:24:28Z)

@Ruxor:
Merci pour ces réponses intéressantes, que je n'ai pas toutes comprises mais c'est parce que je n'ai pas les compétences mathématiques requises :

- je n'ai pas bien compris si par « il [faut?] prendre des intervalles semi-ouverts », il fallait entendre « on ne peut pas faire autrement, de toutes façons (pour la raison du point bicolore que j'ai donné avec mon gros bon sens que les mathématiques démentent souvent) » ou « il faut faire comme ça pour qu'on ne puisse pas poser le segment unitaire de telle sorte que ses deux extrémités soient sur deux points de couleurs différentes »

- je n'ai pas bien compris ce qui tombait juste et ce que cela avait d'étonnant

Pour le fuseau de Moser, je sais bien que la géométrie est l'art de raisonner juste sur des figures fausses, mais la page indique précisément les mesures des angles, les distances entre les points (unit distant graph) et le fait que les segments ne se chevauchent pas (matchstick graph). D'autres propriétés sont en revanche respectées (nombre de sommets, d'arêtes, etc.) : est-ce cela qu'il faut entendre par « graphe abstrait » ? Est-ce plus important que les premières propriétés, celles qui ne sont pas respectées par le schéma ?

Surtout, pourquoi mettre ce graphe abstrait alors que le graphe « concret » conviendrait aussi bien ?

(J'en profite pour dire que le nom de l'image est « pseudotriangulation » : cela veut tout dire.)

Enfin, si mes questions te saoulent, n'hésite pas à ne pas y répondre : je comprendrais que tu aies autre chose à faire.

Ruxor (2012-05-02T13:35:59Z)

@Fier d'avoir…: J'oubliais : le dessin du fuseau de Moser sur l'article <URL: http://en.wikipedia.org/wiki/Moser_spindle > est un dessin en tant que graphe abstrait, alors que moi j'ai fait un dessin en tant que graphe dans le plan pour la relation être-à-distance-1. C'est bien le même graphe, juste qu'il n'est pas visualisé de la même façon (ou si on veut, le mien a une structure supplémentaire, une représentation plane pour la distance 1).

@Fab: Les moyens informatiques ne permettent pas vraiment de conclure grand-chose. On peut certes chercher à énumérer plein de graphes pour espérer en trouver un qui ait nombre chromatique au moins 5 et qui soit représentable comme un graphe de distance 1, mais le nombre de graphes explose de façon faramineuse et tester si un graphe donné est représentable avec distance 1 est un problème algorithmiquement difficile (au moins conjecturalement), donc au final on n'arrive pas à grand-chose (à part que décidément on n'y arrive pas, mais que ça ne prouve rien).

@Grasyop: Le minorant 6 pour la dimension 3 vient apparemment de l'article : O. Nechushtan, « On the space chromatic number », *Discrete Math.* 256 (2002), 499–507.

Ruxor (2012-05-02T13:28:37Z)

@Fier d'avoir…: Tu as bien compris ce que je voulais dire.

Je veux vraiment insister sur le fait que le fuseau de Moser est certes le graphe le plus petit qui prouve que le nombre chromatique de Hadwiger-Nelson vaut au moins 4, mais il n'a rien de profondément naturel, il existe plein d'autres graphes qui peuvent le prouver. Voir par exemple le graphe (dû à O'Donnell) en figure 15.6 de <URL: http://books.google.fr/books?id=Vn3GLf-4YkEC&pg=PA115 >, qui a 56 sommets et est réalisable avec distance 1, qui n'est coloriable qu'avec 4 couleurs comme le fuseau de Moser, mais qui a surtout la propriété remarquable de ne contenir aucun triangle (je veux dire, aucun triangle d'arêtes, i.e., aucun triangle équilatéral de côté 1). Comme quoi même le triangle n'est pas incontournable.

En dimension 1, oui, il prendre des intervalles semi-ouverts, et on tombe « tout juste », ce qui est peu surprenant vu qu'on trouve pile le nombre optimal de couleurs.

Les majorant et minorant connus en dimension n (qui n'ont rien de profondément naturels, puisqu'il s'agit juste du mieux qu'on sache faire) sont bien sûr des entiers pour chaque n, mais ce que j'ai donné c'est l'équivalent asymptotique, pas la valeur exacte de ces majorant et minorant. (Équivalent asymptotique, ça veut dire que le rapport entre les deux tend vers 1 quand n tend vers l'infini.)

Grasyop (2012-05-02T12:14:43Z)

Dans l'espace, peut-on réellement minorer χ par 6 ? Wikipédia donne cet encadrement 6 ≤ χ ≤ 15, mais le document indiqué en référence affirme seulement 5 ≤ χ ≤ 15.

Fab (2012-05-02T09:15:25Z)

Problème vraiment intéressant dont je n'avais jamais entendu parler, tiens !
Et je trouve effectivement très fort le fait que la preuve de l'inégalité 4≤χ≤7 est triviale (ou presque) sans qu'on puisse améliorer cet encadrement même avec les maths de haut niveau qu'on connaît (enfin quand je dis « on », je ne m'inclus pas, hein).

Mais ce que je trouve encore plus fort, c'est qu'on ne propose même pas une toute petite conjecture à ce sujet ?? Même avec des moyens informatiques ?

Fier d'avoir ... (2012-05-02T02:29:50Z)

@Ruxor:
Merci pour ces remarques intéressantes.

Je comprends ton objection, et je dois admettre qu'en effet, de même que la suite "segment"-"triangle équilatéral" semble appeler comme troisième terme "tétraèdre", alors que c'est "fuseau de Moser", de même la suite "segment"-"triangle équilatéral"-"fuseau de Moser" semble appeler comme quatrième terme le "double tétraèdre" (je ne connais pas le nom exact) alors qu'il y a peut-être un quatrième terme dans le plan.

(Désolé si je répète ce que tu as dit, mais je pense que cela peut en aider d'autres à comprendre s'ils lisent cette idée exprimée différemment.)

Par ailleurs, je rêve ou l'article "Moser spindle" de Wikipédia
<URL: http://en.wikipedia.org/wiki/Moser_spindle >
est illustré par un graphe qui n'est pas un fuseau de Moser ?

Concernant les "infiniment petits", si j'ai bien compris, tu veux dire qu'un segment [AB[ a la même longueur que [AB] (de même qu'on montre facilement que 0,999999… = 1).

Mais au fond, la question n'est pas là, n'est-ce pas ? C'est juste que si je place A, B et C sur le plan tel que AB=BC=1/2*AC et que je colorie [AB] d'une couleur et [BC] de l'autre, je vais avoir un problème parce que B est de deux couleurs (ou alors ce n'est pas un problème ?). Donc il vaut mieux que [AB[ soit d'une couleur, [BC[ de l'autre.

C'est terrible, parce qu'on a vraiment l'impression qu'on va pouvoir placer le segment dans la zone de même couleur, et en fait non !

Pour la généralisation à n dimensions, on aurait envie, naïvement, de poser pour le minorant 2n et pour le majorant 2^(n+1)-1 parce que cela donne les valeurs connues pour les dimensions 1, 2 et 3, mais j'imagine que l'esprit fertile des mathématiciens a dû montrer que pour n=4, il fallait que ce soit autre chose, d'où ces constantes bizarres qui ne donnent même pas des majorants et minorants entiers !

En tout cas, il est bien vrai que ce problème donne beaucoup à penser…

Ruxor (2012-05-01T22:00:48Z)

@Fier d'avoir…: J'aurais sans doute dû mieux expliquer d'où sortait ce fuseau de Moser, en effet. Mais il ne faut pas se faire l'idée qu'il est le *seul* graphe qui montre χ≥4 : il y a beaucoup de graphes qui ont nombre chromatique 4 et qui peuvent se représenter avec distance 1 (chercher par exemple "Golomb graph" dans Google images), donc il est difficile de conclure qu'il n'y en a pas qui ont nombre chromatique 5, 6 ou 7. La seule chose qui est véritablement naturelle, c'est des sommets tous reliés les uns aux autres (ce qu'on appelle une clique : ici, un segment dans la droite, un triangle équilatéral dans le plan, un tétraèdre dans l'espace), et si on ne connaissait pas le fuseau de Moser, on pourrait se dire « le segment montre que 2 couleurs sont nécessaires et suffisantes pour la droite, pour le plan, un triangle montre qu'il faut au moins 3 couleurs, or le graphe suivant, le tétraèdre, n'existe que dans l'espace, donc je conjecture que 3 couleurs suffisent pour le plan » — et on se serait trompé.

@Grasyop: Je ne sais pas. Il y a un nombre faramineux de questions adjacentes à Hadwiger-Nelson et beaucoup d'entre elles ont malheureusement cette même réponse…

@DH: On a des bornes en toute dimension, bien sûr, mais elles sont encore pires qu'en dimension 2. En dimension 3 les meilleures bornes connues semblent être 6≤χ≤15, et en dimension n on a des bornes qui sont équivalentes à 1.239…^n pour le minorant, et à et 3^n pour la borne supérieure.

Pour la droite, la réponse est évidemment 2, comme l'a signalé W.

@Oudeis: Les "infiniment petits" n'ont pas de place dans les réels.

Oudeis (2012-05-01T17:13:24Z)

@W :
Si le segment est ouvert, n'a-t-il pas une longueur inférieure à l'unité (d'une longueur infiniment petite, certes) ?

N'est-il pas possible, en ce cas, de poser le segment unitaire de telle sorte qu'un des deux bouts soit sur la limite fermée d'un segment coloré (l'autre étant sur la limite ouverte), puis de le décaler d'une longueur infiniment petite pour que les deux bouts du segment soient sur des zones de même couleur ?

W (2012-05-01T16:11:24Z)

@Fier: En dimension 1, χ=2. Il suffit de découper la droite en segments de longueur 1, ouverts d'un côté et fermés de l'autre. Si j'ai bien compris le problème.

Oudeis (2012-05-01T16:04:24Z)

@DH :
La généralisation du fuseau de Moser dont il a été question prouve que pour un espace en trois dimensions, il faut au moins cinq couleurs.

DH (2012-05-01T13:18:00Z)

Tiens, et qu'en est-il en dimension supérieure (3 au moins) ?

Grasyop (2012-05-01T11:09:54Z)

Le plan doit être au moins quadricolore. Est-ce qu'il y a moyen de montrer qu'on peut trouver ces quatre couleurs sur un même cercle de rayon 1/√3 (c'est-à-dire circonscrit à un triangle équilatéral de côté 1) ?

Fier d'avoir trouvé ça tout seul (2012-05-01T01:01:54Z)

DH me donne l'occasion de faire observer que cette entrée n'est pas très pédagogique.

Mais comme le problème exposé est en effet intéressant, j'y ai réfléchi pour comprendre le pourquoi du « fuseau de Moser ». J'en arrive à la conclusion que khi=4 ! Évidemment, je ne peux pas le prouver (je n'ai pas cette prétention, rassurez-vous), mais je retiens les indices suivants :
- le triangle équilatéral prouve que khi>2
- le fuseau de Moser prouve que khi>3
- il semblerait donc naturel qu'on trouve une nouvelle figure qui soit au fuseau de Moser ce que celui-ci était au triangle équilatéral. En cherchant deux minutes, on voit qu'elle est en 3D (deux pyramides collées par la base). D'où l'idée que khi=3 pour 1 dimensions, khi=4 pour 2 dimensions, khi=5 pour 3 dimensions, etc.

C'est cohérent avec le fait que le triangle équilatéral s'obtient en faisant pivoter un segment (1 dimension) autour d'un pivot ; que le fuseau de Moser s'obtient en faisant pivoter un losange (deux dimensions) autour d'un pivot ; qu'on peut faire pivoter les deux pyramides collées dont j'ai parlé autour d'un pivot dans un espace en 3D pour obtenir une sphère dont tous les points doivent être de couleur identique, ce qui permet de trouver deux points sur la sphère distants de l'unité qui contredisent la demande initiale.

(Cela ne prouve rien, je sais.)

Je précise pour f3et, qui m'a l'air un peu chagrin, que je ne poste pas ça pour faire avancer la science, parce que je suis sûr que de vrais mathématiciens ont déjà trouvé ça, mais seulement parce que je suis fier d'être arrivé à ces conclusions tout seul (euh, je voulais bien sûr dire parce je serais intéressé par des commentaires de gens compétents, même si un blog n'est pas le lieu idéal pour cela).

DH (2012-04-30T11:02:08Z)

OK, je vois maintenant :-)

Ruxor (2012-04-30T10:43:15Z)

@DH: Si je n'ai que trois couleurs, chaque triangle équilatéral de côté 1 doit avoir un sommet de chacune des trois couleurs. Si j'appelle c la couleur du point en bas à gauche de ma figure, les deux autres sommets de n'importe quel triangle équilatéral de côté 1 ayant ce point pour sommet se partagent les deux autres couleurs (disons a et b, dans un certain ordre, peu importe), et du coup quand on fait un nouveau triangle équilatéral sur ces deux sommets, on obtient à nouveau la couleur c pour le troisième sommet (qui est à distance √3 du sommet de départ). Or sur ma figure on en a deux comme ça, à distance 1, d'où une contradiction.

Oui, ce serait plus clair si je donnais des noms à mes points. :-)

DH (2012-04-30T08:48:04Z)

Tu peux développer sur la borne inférieure à 4 ? Je suis le raisonnement logique, mais j'ai du mal à visualiser l'étape intermédiaire (qui porte sur les 4 sommets à distance 1 du point en bas à gauche).

Ruxor (2012-04-30T06:04:49Z)

La question suggérée par Jean Némar, chercher à colorier le plan avec le nombre minimal de couleurs de façon qu'aucun triangle équilatéral de côté 1 ne soit monochromatique, est une question intéressante en soi, et elle a été étudiée aussi (et on me souffle que la réponse est que 2 couleurs suffisent, mais je n'ai pas de référence ni même de certitude). Je ne pense pas qu'elle puisse vraiment aider à résoudre le problème de Hadwiger-Nelson original, mais elle est assez typique de ce que font les matheux face à un problème trop difficile : le généraliser, ou, au moins, chercher des problèmes adjacents auxquels on saurait mieux répondre.

f3et (2012-04-30T03:05:39Z)

(Pour Jean Némar) Feynman, commentant ce genre d'approche, disait :" C'est un peu comme d'être en train d'essayer d'ouvrir un coffre-fort, et qu'un quidam s'approche en vous demandant si vous avez essayé 123456, alors qu'après plusieurs heures de dur travail, vous avez déjà déterminé que la combinaison est formée de 8 chiffres et deux lettres… Vous n'avez guère envie d'interrompre votre tâche pour le lui expliquer"

Jean Némar (2012-04-29T19:11:24Z)

Dans ce genre de problème, il faut y aller progressivement. Une bonne piste est sans doute de trouver le nombre minimum de couleurs à utiliser pour que tout triangle équilatéral de coté un ne soit pas d’une couleur, puis ensuite pour qu’il soit de trois couleurs.

Ruxor (2012-04-29T15:49:18Z)

@Ilia: Oui, tu as raison, du point de vue de la logique, c'est une condition nécessaire (le fait que ce soit suffisant est trivial). Le verbe « suffire » est à comprendre au sens « il suffit de regarder les graphes finis » (ceux-ci « suffisent » à contrôler le nombre chromatique[#]), mais du coup c'est particulièrement confusant et mal dit, j'en conviens.

[#] Ils ne suffisent pas pour le nombre chromatique fractionnaire, soit dit en passant (enfin, au moins pour une des définitions du nombre chromatique fractionnaire pour un graphe infini).

Ilia (2012-04-29T12:49:06Z)

"Un théorème d'Erdős et de Bruijn (qui est une conséquence immédiate du théorème de compacité du calcul propositionnel, ou — un petit peu moins immédiate — de la compacité des produits de compacts) assure que pour minorer le nombre de couleurs χ nécessaire pour colorier le plan, il « suffit » d'exhiber un graphe fini réalisable avec distance 1 et qui n'est coloriable qu'avec ce nombre de couleurs."

J'ai trouvé ce passage un peu confusant. J'ai l'impression que le "il suffit" exprime en fait une condition nécessaire, et non une condition suffisante : le fait que l'existence d'un tel graphe implique une minoration est trivial, c'est la réciproque qui est intéressante. Ai-je bien raison ? ou alors c'est moi qui me plante complètement dans la logique ? ou peut-être que tu voulais dire complètement autre chose ?
(Cela dit, je comprends aussi comment on peut écrire ça ; peut-être que j'aurais écrit la même chose, en fait. N'empêche que ça m'a fait bugguer à la première lecture.)


You can post a comment using the following fields:
Name or nick (mandatory):
Web site URL (optional):
Email address (optional, will not appear):
Identifier phrase (optional, see below):
Attempt to remember the values above?
The comment itself (mandatory):

Optional message for moderator (hidden to others):

Spam protection: please enter below the following signs in reverse order: 04a357


Recent comments