<foo> simply produces <foo>in the text).
<URL: http://somewhere.tld/ >,
and it will be automatically made into a link.
(Do not try any other way or it might count as an attempt to spam.)mailto: URI,
e.g. mailto:my.email@somewhere.tld,
if you do not have a genuine Web site).
sbi (2018-04-24T06:07:33Z)
@Koko90: j'ai d'abord cru à une parodie puis j'ai vérifié, et le lien existe…
La Cour de cassation vient de dire en gros "si vous tombez dans le panneau d'un
texte écrit grossièrement avec des fautes d'orthographe, vous êtes un neuneu et
allez vous faire voir" (16-20.018).
Dans le lien que tu pointe je vois: "quelque soit l'unité de mesure choisie…",
aussi nul qu'une vulgaire publicité Darty. Game over Science & Vie!
Serge (2018-04-20T14:26:02Z)
Quelle est la raison qui te persuade que χ=7 ? Pourquoi ne pas conjecturer que χ=5, mais avec un coloriage non-mesurable ? La valeur χ=7 provient peut-être de l'utilisation d'un pavage par des polygones, tandis que des courbes de Jordan quelconques donneraient χ=6. Qu'en penses-tu ?
Koko90 (2018-04-16T12:56:37Z)
[quote]
Peut-être que la presse généraliste va s'en emparer (et raconter des conneries)
[/quote]
https://www.science-et-vie.com/science-et-culture/inedit-un-bio-gerontologue-resout-un-probleme-vieux-de-70-ans-en-mathematiques-10802
Le titre est un peu racoleur (le problème n'est pas "résolu") et la description du problème est fausse :
"Supposons qu'on possède un plan de plusieurs m² (voire infini) et qu'on y définit une unité de mesure, par exemple 1 cm. Supposons aussi qu'on doive paver ce plan par des tuiles de même forme et taille (choisies par nous), de sorte qu'il n'y ait ni trous ni chevauchements.
Le défi est de choisir des couleurs pour colorier les tuiles de sorte qu'on ne puisse jamais trouver deux points de même couleur distants d'une unité (1 cm). Question : quel est le nombre minimum de couleurs dont on doit peindre les tuiles pour toujours respecter la consigne ?"
Ruxor (2018-04-13T21:07:43Z)
@pensebête: Il y a certainement des choses de ce genre, mais j'ai peur de ne pas avoir de réponse claire à apporter. Je doute qu'il y ait quelque chose d'aussi simple que « si un graphe réalisable avec distance 1 non 5-coloriable existe, il en existe un dont les coordonnées sont des combinaisons rationnelles de 1, √3, √5, √7, √11, √13 », mais il y a peut-être bien quelque chose du même style qu'on peut dire. La seule chose dont je suis certain, c'est que si un graphe réalisable avec distance 1 non 5-coloriable existe, il en existe un dont les coordonnées sont algébriques ; en poussant un peu, j'imagine pouvoir montrer de façon pas trop difficile qu'on peut exprimer ces coordonnées avec des racines carrées uniquement (c'est-à-dire les nombres constructibles à la règle et au compas, ce qui est assez logique pour un tel graphe) ; mais le fait qu'on n'ait pas lieu de faire intervenir des choses comme √(3+√2), par exemple, je ne vois pas vraiment de raison.
Dans l'autre direction, un des résultats de ma note sur l'arXiv est que tout graphe réalisable avec distance 1 dont les coordonnées sont dans ℚ(√3,√11) (c'est-à-dire combinaison rationnelle de 1, √3, √11 et √33) est forcément 5-coloriable ; on doit d'ailleurs pouvoir ajouter encore la racine carrée de n'importe quels nombres premiers congrus à 1, 3, 4, 5 ou 9 modulo 11 (la raison est, en gros, que dans ce cas on peut « réduire modulo 11 » les coordonnées, et le graphe de toutes les coordonnées modulo 11 est 5-coloriable). Mais je ne sais vraiment pas expliquer (autrement qu'en agitant les mains) pourquoi aller chercher √7 est plus naturel que telle ou telle expression compliquée.
pensebête (2018-04-13T19:51:30Z)
Un petite question de béotien à l'arithméticien que tu es.
Appelons V le sorte d'espace vectoriel de dimension 3 à coordonnées rationnelles Q(1,sqrt(3),sqrt(11)), puis W=Q(1,sqrt(3),sqrt(5),sqrt(7),sqrt(11)), qui est de dimension 5. Peut-être un autre mot comme corps est plus approprié, j'ai oublié tout mon algèbre, mais passons.
D'après le fichier au format sage du graphe à 1585 sommets, on voit que tous les points ont des coordonnées dans W. Cela doit d'ailleurs être évident à qui comprend la construction.
Or dans le cas du Spindle et du Golomb ils sont dans V, mais d'après ceci <URL: http://demonstrations.wolfram.com/MoserSpindlesGolombGraphsAndRoot33/ > il existe d'autres graphes non 3-coloriables qui n'y sont pas (et je n'ai pas réussi à trouver si ils sont dans un autre espace de dimension 3 inclus dans W, du genre Q(1,sqrt(5),sqrt(7)), ou dans quelque chose de dimension 4 voire 5). A supposer qu'ils soient aussi dans des choses de dimension 3, on peut se demander si le n dans "ne pas être n-coloriable" est lié au n dans "dim(X)-1", ou X serait l'espace contenant le contre-exemple.
Dit autrement, est-ce qu'il y a des idées arithmétiques qui confirment l'idée que, si il existe, il suffit de chercher un graphe non 5-coloriable avec des coordonnées dans Q(1,sqrt(3),sqrt(5),sqrt(7),sqrt(11),sqrt(13)) ? Merci pour tout éclaircissement.
Ruxor (2018-04-12T21:10:13Z)
@Onde: Ah oui, j'ai abusé. Ce que j'aurais dû dire, c'est que s'il y a un modèle standard de ZFC dans lequel χ=7 alors χ=7 dans tout modèle de ZF. Mais effectivement, contrairement à ce que je disais, il est concevable que χ vaille 5,6,7 dans différents modèles de ZFC.
Onde (2018-04-12T19:25:37Z)
Ah oui, le gars qui pensait ça ne croyait pas en l'axiome du choix, donc c'était sûrement ZF qu'il disait, désolé.
En tout cas, pour moi, c'était pas du tout évident que c'était pas possible de varier dans ZFC : j'avais l'impression que par exemple le nombre pouvait valoir 5 en vrai, mais que dans certains modèles, il y avait un sous-graphe "fini" (de taille un entier non-standard) non 5-coloriable voire non-6-coloriable. Mais visiblement, soit cette impression est dépourvue de sens, soit elle est fausse.
Ruxor (2018-04-12T14:36:19Z)
@jonas: Yes, this is essentially the reasoning that had convinced me that it was probably impossible to find a unit distance graph that has chromatic number at least 5, you explain it much more clearly than what I wrote. Of course I realize (and I realized even at the time) that having equal distance everywhere is very special, and that the graph consisting of a large number of equilateral triangles in a tiling pattern has a number of edges equal to 3 times its number of vertices (plus O(1)), so there can't be a trivial argument saying that a unit distance graph with n vertices has at most 2n+C edges. But still, I believed that one "couldn't do much" even with the equilateral tiling because its number of 4-colorings seems huge. I'm still confused as to how de Grey managed to pull off the trick.
jonas (2018-04-12T14:09:02Z)
I'd expand on the coincidence part this way.
If you want to find n points in the plane with some distances specified between them, you can in general specify 2*n-3 distances. Moser's spindle has 7 nodes and 11 edges, exactly that amount. The second graph you show has 10 nodes and 18 edges, which is one more than this amount, but you can actually omit one edge and the graph is still not 3-colorable.
However, a graph with 2*n-3 edges can always be 4-colored. A 5-chromatic graph needs at least 2*n edges, and in fact at least 2*n+1 edges unless it contains a complete graph on 5 points. If you want to specify distances between points on the edges of such a graph, then you have restrictions on how you can choose the distances. The only reason why it's possible at all is because all unit distances is special enough.
Ruxor (2018-04-12T11:46:43Z)
@Onde: "chaque valeur entre 4 [ou 5] et 7 du nombre chromatique était compatible avec ZFC" n'est pas possible : s'il y a un modèle de ZFC où le nombre chromatique du plan vaut 7, alors il vaut 7 dans tout modèle de ZF (i.e., cette affirmation est démontrable), parce qu'il existe un graphe non-6-coloriable réalisable avec distance 1 et à coordonnées algébriques réelles, ce qui est absolu entre modèles de ZFC. (Et j'ajoute que je pense que c'est le cas.) Ce qui est concevable, c'est qu'il existe des modèles de ZF où le nombre chromatique vaut 5, 6 et 7, ou, de façon encore plus tarabiscotée, qu'il existe des modèles de ZFC où le nombre chromatique vaut 5 et 6.
Onde (2018-04-12T11:26:18Z)
Le problème lorentzien, si le nombre est bien infini, est plus intéressant en ce sens qu'il est moins brute-forçable, qu'on sera obligé de comprendre un motif à un moment.
Onde (2018-04-12T11:24:52Z)
C'est vrai que les jolies histoires sont sympas pour les efforts de vulgarisation, mais c'est plus un argument de séduction que de profondeur (la profondeur devant être robuste à ce genre de variations), donc j'imagine que ce n'est pas bien grave (même s'il faut avouer que le storytelling d'avant était mignon). Peut-être peux-tu te consoler en disant que c'est resté ouvert longtemps, et que l'étape après lycéen, c'est un non-"mathématicien professionnel".
Y a même un aspect positif à cette évolution. Avant, on pouvait se dire que y avait une transition de phase entre les résultats accessibles (tous faciles) et les résultats à jamais inaccessibles (beaucoup trop durs) : ce n'était pas forcément une invitation à réfléchir dessus du coup. Là, on sait que la transition n'est pas si abrupte que ça ; après, ça reste globalement faux de penser que "oh bah tiens, un random a autant de chance qu'un chercheur professionnel de trouver la solution" : c'est très bien d'inviter à chercher bien sûr et c'est carrément bien d'être optimiste plutôt que défaitiste, mais faut pas non plus tordre la réalité (je ne prétends pas que tu le fais).
De fait, en mode transition abrupte, je connais des matheux qui pensaient que chaque valeur entre 4 et 7 du nombre chromatique était compatible avec ZFC.
Koko90 (2018-04-12T11:23:39Z)
J'ai fait une thèse sur la théorie des graphes (très orientée sur la construction algébrique de graphes) et j'étais persuadé qu'un jour on trouverait un graphe pour distance-unité avec un nombre chromatique de cinq.
J'avais essayé de bricoler des stratégies pour chercher un tel graphe (en utilisant mes capacités à programmer). Evidemment je n'avais rien trouvé (mais je n'en avais pas déduit que c'était infaisable, juste que c'était difficile et probablement au-delà de mes capacités).
Je suis très content qu'une solution assez "bricolage" ait aboutit. C'est agréable de voir que parfois il faut juste de l'ingéniosité et du bricolage.
Je pense que c'est une bonne nouvelle pour tous les chercheurs amateurs. Cela veut dire que certains problèmes ouverts peuvent êtres résolus par des non-spécialiste s'ils sont assez ingénieux (et sont prêt à utiliser des ordinateurs pour les assister).
Fab (2018-04-12T10:22:49Z)
"Mais j'ai un peu essayé [de limiter leurs possibilités de 4-coloriages jusqu'à toutes les tuer] et je m'y suis salement cassé les dents : tout me semblait suggérer que plus on augmente le nombre de sommets plus les possibilités de 4-coloriages se multiplient, plus vite qu'on arrive à les tuer en ajoutant des arêtes"
Ceci me fait penser aux problèmes d'hydre qui pourraient[#] "suggérer" à l'opposé qu'un ordinal (où une "forme" d'ordinal à spécifier, exercice spéculatif étant laissé au lecteur :-) se cacherait peut-être derrière ces unit-distance graphes grâce auquel on pourrait montrer que χ=7 (vague intuition que j'ai eue aussi en apprenant que χ>4), borne naturelle intrinsèquement liée au pavage hexagonal du plan. Tiens au fait, j'imagine qu'il n'existe pas de pavage spectaculairement régulier de l'espace de Lorentz ? (oui je suppose à tort et à travers, on est d'accord, la dernière supposition se basant sur ton intuition que χL=∞)
Arnaud Spiwack (2018-04-12T07:04:12Z)
Juste une note: d'après Terrence Tao, de Grey a participé à des projets polymaths. Ce qui, je suppose, compte comme des contributions mathématiques, même si peu conventionnelles. https://plus.google.com/u/0/+TerenceTao27/posts/QBxTFAsDeBp
jonas (2018-04-11T22:09:10Z)
See also Gil Kalai's short blog entry <URL: https://gilkalai.wordpress.com/2018/04/10/aubrey-de-grey-the-chromatic-number-of-the-plane-is-at-least-5/ > and Scott Aaronson's short blog entry <URL: https://www.scottaaronson.com/blog/?p=3697 > on the same progress.