Ordre et désordre

Un dernier verre, peut-être ? Venez, ma mie, je vous invite pour un dernier chocolat chaud. Installez-vous sur le canapé, je reviens dans un instant. Ne faites pas attention à cette pile de papiers sur la table et faites comme si les affaires qui traînent par terre, c'est normal. Ignorez également la vaisselle entassée dans l'évier, toute comme cette casserole dans lequel il reste un fond de... euh... ce que j'ai mangé la semaine dernière. Comment ça, cet appartement est mal rangé ? Absolument pas ! D'ailleurs, le désordre total ne peut pas exister ! Ce n'est pas moi qui dit ça, c'est la théorie de Ramsey... Et n'allez pas croire que je me cache derrière les maths... Eh, revenez, je n'ai pas terminé le chocolat chaud !...

La théorie de Ramsey est la suivante : dans une structure contenant beaucoup d'éléments, on finit toujours par retrouver une propriété donnée. La question qui se pose alors, c'est la valeur numérique de ce "beaucoup", qui, pour certain exemple, peut être démesurément grand. On résume plus souvent la théorie de Ramsey par "le désordre total n'existe pas".

Le principe de base de la théorie de Ramsey est le principe des pigeons (alias principe des tiroirs de Dirichlet). Par exemple, à partir de combien de personnes peut-on être sûr d'en trouver deux possédant le même signe du zodiaque ? Puisqu'avec 12 personnes, on peut avoir le zodiaque au complet, la propriété "au moins deux personnes possèdent le même signe astrologique" devient vraie à partir de 13.

Théorème de Ramsey
Le problème central en théorie de Ramsey (et, de façon plus générale, en combinatoire) est celui du théorème de Ramsey. On présente souvent ce théorème par le célèbre problème des six amis.

Vous invitez un groupe d'amis pour une occasion quelconque (soirée foot à la télé, soirée puzzle ...). Parmi ces invités, certains se sont déjà rencontrés auparavent, d'autres se rencontrent pour la première fois. Mais à partir de combien d'invités peut-on être sûr qu'il y ait
- soit trois invités qui se connaissent deux à deux
- soit trois invités qui ne se connaissent pas deux à deux.
Ce nombre, on le notera R(3).

Graphe de la situation.
Deux invités sont reliés par une arête bleue si ils se connaissent, en rouge sinon.
Pour 5 invités, il n'existe pas forcément de trio qui se connaissent ou qui ne se connaissent pas
Ce contre-exemple prouve R(3) ≥ 6.

La réponse est 6, et je peux le prouver ! On suppose que 6 invités sont là, et que David en fait partie (il y a toujours un David dans les invités). Parmi les 5 autres invités, soit il y en a 3 qui le connaissent, soit 3 ne le connaissent pas (par le principe des tiroirs). Sans pertes de généralité, on peut supposer que ces trois invités connaissent David, et qu'ils s'appellent respectivement Karen, Natalie et Billy. Deux possibilités alors : soit ces trois invités ne se connaissent pas (et on a notre trio gagnant), soit il y en a au moins deux qui se connaissent, et ils forment avec David le trio gagnant. CQFD.

Ce problème se reformule dans la théorie des graphes : si les arêtes d'un graphe complet d'ordre 6 sont colorés à l'aide deux couleurs, alors il existe un triangle unicolore.

On peut lister l'ensemble des graphes bicolores complets à 6 noeuds.
Ils admettent tous un sous-graphe complet unicolore.

Mais le problème se généralise : combien faut-il réunir d'invités pour être sûr que, parmi eux, il existe un groupe de k invités se connaissant mutuellement, ou ne se connaissant pas du tout ? Ce que nous dit le théorème de Ramsey, c'est que ce nombre existe toujours. Ce que ne nous dit pas le théorème, c'est sa valeur exacte.

Pour k = 4, on peut montrer R(4) = 18, en raisonnant de façon similaire (en trouvant un graphe contre-exemple à 17 sommets, puis en montrant que cela marche bien dès que n=18).
Pour k = 5, les choses se compliquent. Tout ce que l'on sait dire aujourd'hui, c'est que R(5) est strictement compris entre 42 et 50.
Pour k = 6, cela empire : on ne sait pour l'instant dire qu'une seule chose, c'est que le nombre R(6) est quelque part entre 102 et 165...

A ce sujet, Erdõs a imaginé ce qu'il se passerait si une armée d'aliens belliqueux nous déclarait la guerre, à moins qu'on leur fournisse la valeur de R(5). Dans un tel cas, on pourrait mettre à profit l'ensemble des ordinateurs et des mathématiciens de la planète pour calculer ce nombre. Cependant, si ils nous réclamaient R(6), les ordinateurs et mathématiciens disponibles seraient plutôt réquisitionnés pour mettre au point une stratégie permettant de mettre hors d'état de nuire ces extraterrestres...

Le problème de la fin heureuse
Dès qu'un problème cherche le nombre minimal d'objets à réunir pour qu'une propriété soit vérifiée, on peut l'inclure dans la théorie de Ramsey. Un autre problème représentatif est le problème du Happy ending (parce que, à la fin, ils se marièrent et eurent beaucoup¹ d'enfants). Ce théorème nous annonce que :

Etant donné (au moins) 5 points du plan (jamais alignés ni confondus),
il y existe toujours quatre points formant les sommets d'un quadrilatère convexe.

Un quadrilatère (ou n'importe quelle figure géométrique) est convexe quand il ne possède aucun creux. Par exemple, le quadrilatère rouge en dessous n'est pas convexe.

A gauche : un exemple où 4 points ne forment pas un quadrilatère convexe.
A droite, plusieurs dispositions de 5 points. Dans tous les cas, il existe toujours (au moins) un quadrilatère convexe. L'enveloppe convexe des groupes de 5 points est représentée en jaune.

Pour démontrer ce fait, il suffit d'envisager tous les cas possibles, selon l'enveloppe convexe des 5 points (l'enveloppe convexe, c'est le polygone que l'on obtient quand on place un élastique autour de l'ensemble de ses points. Par essence, une enveloppe convexe est convexe).
- si l'enveloppe convexe est un pentagone, il suffit d'en retirer un point pour retrouver le quadrilatère tant cherché.
- si l'enveloppe convexe est un quadrilatère, inutile d'aller chercher plus loin
- si c'est un triangle, alors les deux points à l'intérieur forment un quadrilatère convexe avec au moins l'un des côté (avec le côté qui ne coupe pas la droite formée par les points intérieurs). CQFD.

Cette histoire de quadrilatère convexe est le problème original du happy ending, découvert et démontré en 1933 par Esther Klein. Elle demande alors a ses collègues si l'un d'eux a une idée pour généraliser la question : étant donné un grand nombre de points, y existe-t-il toujours un pentagone/hexagone/n-gone convexe. George Szekeres revient une semaine plus tard avec sa réponse : oui !

Théorème de Erdös-Szekeres : Étant donné un ensemble suffisamment grand de points du plan (jamais alignés ni confondus), il y existe toujours N points formant les sommets d'un polygone convexe.

9 points suffisent pour y trouver un pentagone convexe

Si Erdös a accolé son nom a celui de Szekeres, c'est qu'il a pas mal étudié la question lui aussi. C'est d'ailleurs Erdos qui a surnommé ce théorème "happy ending" en 1937, puisque c'est celui-ci qui a mené Esther Klein et George Szekeres à se marier en 1937 !

On peut être un peu plus précis sur la valeur de "suffisamment grand" :
- si on cherche les triangles convexes, 3 points suffisent (puisqu'on les suppose ni alignés, ni confondus)
- si on cherche les quadrilatères convexes, 5 points suffisent.
- si on cherche les pentagones convexes, il faut au moins 9 points.
- si on cherche des hexagones convexes, c'est 17 points qu'il est suffisant d'avoir. Ceci n'a été démontré qu'en 2006 (Szekeres, Peters)
- pour les polygones plus grand, rien n'est encore sûr. On sait qu'il faut au moins 1+2^N-2 points pour y trouver à coup sûr un N-gone convexe, on conjecture que cette borne est optimale.

Le problème du polygone vide
Le théorème de Erdös-Szekeres serait encore plus élégant si, en plus d'être convexe, le polygone pouvait être vide (aucun point à l'intérieur). Pour 5 points, pour peu que l'on modifie légèrement la démonstration, on peut montrer qu'il existe toujours un quadrilatère convexe vide. Pour 9 points, il n'existe pas forcément de pentagone convexe vide, mais il suffit de 10 points pour rendre cette assertion vraie. Mais existe-t-il toujours un hexagone convexe vide dans un ensemble assez grand de points ?

La réponse est oui, mais il a fallu attendre 2007 pour en être sûr. Le nombre exact de points suffisant n'est pas connu exactement, mais on sait quand même qu'avec 463 points, on est sûr d'avoir un hexagone convexe vide.

463 points au hasard. Il y existe forcément (au moins) un hexagone convexe vide
Avec moins de 463 points, rien n'est sûr...

Je prèfère ne pas trop évoquer le cas de l'heptagone convexe vide, puisqu'il contredit la théorie de Ramsey : même avec un nombre arbitrairement grand de points, on ne peut pas être sûr d'y trouver d'heptagone convexe vide...

Le nombre de Graham
Un dernière exemple de problème de la théorie de Ramsey, le problème de Graham :

Considérons un hypercube de dimension n où chaque arête et diagonale est coloré en rouge ou en bleu.
Y existe-t-il toujours un plan unicolore défini par 4 sommets coplanaires ?
Si non, à partir de quelle dimension n est-ce toujours vraie ?

Exemple, avec n = 3. On a donc un cube (on ne peut plus classique, en 3D), on colore en rouge/bleu ses 28 arêtes et diagonales. Parfois, on peut y trouver un plan unicolore :

Et parfois, non :

Impossible de trouver un plan unicolore passant par 4 points dans ce cube

A partir de quelle dimension peut-on être sûr d'en trouver ? Les spécialistes conjecturent qu'il suffit de chercher dans un hypercube de dimension 13. Mais entre ce que l'on conjecture et ce qu'on l'on arrive à démontrer il y a un gouffre, ce problème en est le plus gros exemple. Ce que Graham est parvenu à démontrer, c'est que la dimension recherchée est un nombre grand. Très grand. Ce nombre est tellement grand que je ne peux l'écrire sur ce blog. Je ne peux même pas écrire le nombre de chiffres qui le compose, pas plus que le nombre de chiffres qui compose son nombre de chiffres. Ce nombre est tellement grand que si je l'utilise dans une blague de "ta mère", on pourrait penser que j'exagère un peu. A l'heure d'aujourd'hui, cette borne supérieure reste la pire qui existe de toute l'histoire des démonstrations mathématiques. Et pourtant, grâce à cette démonstration, on peut quand même dire qu'il est vrai que la propriété de Graham est vraie en grandes dimensions...

Ce nombre N*, c'est le 64e terme de la suite
u₁ = 4
u₂ = 3 ↑↑↑↑ 3
u₃ = 3 ↑^{3 ↑↑↑↑ 3} 3
... où ↑ⁿ désigne la flèche (itérée n fois) de Knuth (voir ce vieil article)

Certaines personnes ont du mal à penser en dimension 3, la plupart des gens sont incapable de penser en dimension 4. Il ne me semble pas que quiconque sur Terre soit capable de réfléchir en dimension N*. 

---

Sources :
Une démonstration du calcul de R(4), et plein d'autres articles intéressants sur cut-the-knot
Colorie-moi le ciel, qui parle aussi du théorème de Ramsey infini
Le désordre total n'existe pas..., Pour la Science N°376 - fevrier 2009

Images :
Friends strangers graph

---

1 : Encore une fois, la théorie de Ramsey ne nous donne pas la valeur exacte de ce "beaucoup".

Comments

[El Jj]

@bob & @ProfGra : merci pour votre lecture attentive, j'ai tout de suite corrigé les erreurs.

(Je supprime les commentaire relevant les coquilles seulement pour éviter le trop plein de commentaires)

[Bob]

Merci pour ce bel article !



Pour répondre à Pollux : clairement, la réponse est non. Ce que tu proposes revient écrire le nombre n tel qu'en prenant n fois le log du nombre de Graham, on obtienne 0. Ce nombre est donc grosso modo le nombre de 10 qu'il faudrait utiliser pour écrire G=10^10^10...^10.

Or, un peu de réflexion montre que rien que pour le terme u_2 de la suite utilisée dans l'article, le nombre de "10" nécessaires pour avoir u_2<10^10^...^10 est (largement) supérieur au nombre d'atomes dans la galaxie, par exemple.

[speace]

si j'avais su ça quand j'étais jeune j'aurai rangé ma chambre moins souvent avec ce type d'argument :)

un article très plaisant comme toujours.

P.S : petite coquille "sur ce viel article"

[Pollux]

Est-ce que le nombre qui compte le nombre de fois que l'on utilise récursivement "le nombre de chiffres qui compose le nombre de chiffres qui compose le nombre de chiffres .... de N*" jusqu'à obtenir un nombre que l'on peut écrire peut être écrit ?