Graphe complet à six points : le triangle inévitable

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente. L'objectif de cette exploration aujourd'hui, c'est de décortiquer un article vraiment fascinant sur la coloration de graphes.

Intervenant 20:09

Ouais, un sujet qui a l'air super simple sur le papier, mais qui cache des trucs, enfin, des concepts vraiment dingues.

Intervenant 10:15

Exactement. En fait, pour bien comprendre, imaginons une situation très concrète, genre une soirée avec six personnes.

Intervenant 20:21

C'est le meilleur moyen de visualiser la chose.

Intervenant 10:23

Et apparemment, les lois mathématiques dictent qu'il y aura toujours au moins trois personnes qui se connaissent déjà toutes ou alors trois personnes qui sont de parfaites inconnues les unes pour les autres.

Intervenant 20:33

C'est ça. Et la mission de notre analyse d'aujourd'hui, c'est de découvrir comment ce concept tout bête, qui ressemble à un petit jeu de lignes tracées sur un bout de papier, se transforme en un véritable défi pour les mathématiques modernes.

Intervenant 10:45

Alors le point de départ est en effet très visuel, presque enfantin je dirais. On place juste quelques points sur une feuille et on les relie tous entre eux.

Intervenant 20:54

Voilà, avec des lignes. Et la règle du jeu exige simplement de colorier chaque ligne avec une couleur parmi deux au choix, disons bleu ou rouge.

Intervenant 11:02

D'accord. Donc si on place cinq points, j'ai cru comprendre qu'on arrive assez facilement à agencer les couleurs pour qu'aucun triangle formé par ces lignes ne soit d'une seule et même couleur.

Intervenant 21:10

Ouais, avec cinq points, la structure reste totalement sous contrôle. Mais le truc fou, c'est qu'en ajoutant un seul point...

Intervenant 11:16

Juste un seul, pour arriver à six.

Intervenant 21:18

Exactement. Le triangle d'une seule couleur devient absolument inévitable.

Intervenant 11:22

Mais du coup, comment on explique cette espèce de bascule géométrique ?

Intervenant 21:27

Reprenons l'image de la soirée avec six personnes. On prend une personne au hasard, disons Alice.

Intervenant 11:32

Ok, on garde Alice.

Intervenant 21:34

Alice, elle est reliée aux cinq autres personnes par cinq lignes. Avec seulement deux couleurs possibles, la logique pure nous dit qu'au moins trois de ces cinq lignes partagent obligatoirement la même couleur.

Intervenant 11:44

Ah oui, parce que deux couleurs pour cinq lignes, il y en a forcément une qui est majoritaire.

Intervenant 21:49

C'est le principe des tiroirs, tout à fait. Donc, disons que trois lignes qui partent d'Alice sont bleues.

Intervenant 11:53

D'accord. Alice a trois lignes bleues qui la relient à trois autres invités spécifiques. Mais que se passe-t-il si l'on observe le triangle formé spécifiquement par ces trois invités entre eux ?

Intervenant 22:04

C'est là que le piège se referme. Si l'une des lignes entre ces trois invités est bleue, bam, elle forme immédiatement un triangle bleu fermé avec notre point de départ, Alice.

Intervenant 12:14

Logique. Et à l'inverse ?

Intervenant 22:15

Bah si aucune de ces lignes n'est bleue, ça veut dire qu'elles sont toutes

Intervenant 12:18

rouges. Et donc leur triangle commun est intégralement rouge.

Intervenant 22:21

Voilà. La conclusion tombe. Un triangle d'une seule couleur se forme obligatoirement. C'est imparable.

Intervenant 12:29

La mécanique est vraiment brillante. Et je crois que c'est Frank Plumpton-Romsay, un mathématicien britannique des années 1920, qui a théorisé tout ça, non ?

Intervenant 22:39

Oui, tout à fait. Il a prouvé ça pour six points. Et la suite logique pour la communauté, c'était de chercher le nombre total de points nécessaires pour garantir un groupe de quatre points reliés par la même couleur.

Intervenant 12:51

Et alors pour quatre points ?

Intervenant 22:53

Eh bien, il faut monter à dix-huit points.

Intervenant 12:55

Dix-huit ?

Intervenant 22:56

Ouais. Et la preuve mathématique de ce nombre n'est arrivée qu'en 1955.

Intervenant 13:01

Attendez une seconde. On vient de résoudre le problème pour trois points. Allez, quelques secondes d'explication. Pourquoi diable est-ce qu'il a fallu attendre plus de 25 ans juste pour ajouter un seul point à ce groupe monochrome ?

Intervenant 23:14

C'est parce que la quantité de combinaisons explose littéralement. Pour prouver que la réponse est bien 18, il a fallu démontrer que 17 points ne suffisaient pas.

Intervenant 13:23

Ah, je vois, il fallait trouver l'exception.

Intervenant 23:26

C'est ça. Les mathématiciens ont dû construire un contre-exemple parfait avec 17 points.

Intervenant 13:31

Mais comment on fait, très concrètement, pour prouver qu'un réseau de 17 points peut éviter de former un groupe de 4 points de la même couleur ?

Intervenant 23:39

Alors l'astuce, c'est de placer ces 17 points en cercle, un peu comme sur le cadran d'une horloge en fait.

Intervenant 13:45

D'accord, un grand cercle.

Intervenant 23:46

Voilà. Et en organisant les lignes selon une symétrie tournante très précise, avec un motif de couleur répétitif basé sur la distance entre les points, on empêche géométriquement toute forme à quatre sommets d'être d'une seule couleur.

Intervenant 13:59

De ceci, non. Donc, si passer de trois à quatre points a pris des décennies, qu'est-ce qui se passe quand on cherche des nombres à peine plus grands, genre cinq ?

Intervenant 24:07

Ah bah là, on entre tout simplement dans le flou.

Intervenant 14:09

Vraiment ?

Intervenant 24:10

Oui. Les mathématiques touchent à leurs limites actuelles. Pour garantir un groupe de cinq points, on n'a pas la réponse exacte. On a juste un encadrement. On sait que le nombre total de points requis se situe entre 43 et 49. Mais c'est fou

Intervenant 14:23

ça ! Et si l'on double la mise pour, disons, garantir un groupe de dix points de la même couleur ?

Intervenant 24:29

Alors pour 10, la valeur exacte reste un mystère absolu. Le flou est colossal. La réponse est coincée quelque part entre 798 et plus de 23

Intervenant 14:38

000. 23 556, pour être précise, selon l'article. Pour les auditeurs, ça pourrait paraître complètement absurde.

Intervenant 24:45

C'est sûr.

Intervenant 14:45

Je veux dire, à l'ère de l'intelligence artificielle et des supercalculateurs, pourquoi on ne peut pas simplement demander à une machine de tester toutes les possibilités pour 10 petits points ?

Intervenant 24:56

Parce que le nombre de configurations possibles pour ces points dépasse allègrement le nombre d'atomes dans l'univers observable.

Intervenant 15:02

Wow ! Ah oui, quand même !

Intervenant 25:04

Ouais, aucune machine ne pourrait toutes les tester. Une règle du jeu extrêmement simple en apparence, dissimule en fait une immensité inexplorée de combinaisons.

Intervenant 15:12

Ça donne vraiment une belle leçon d'humilité théorique. Derrière l'élégance de ces petits problèmes de coloriage, il y a une complexité vertigineuse que nos outils peinent encore à dompter.

Intervenant 25:22

C'est clair, ça demande une rigueur mathématique qui est tout simplement fascinante.

Intervenant 15:26

Pour conclure cette analyse, il y a une dernière pensée qu'on peut laisser infuser dans les esprits. L'article que nous avons décortiqué se limite sagement à des lignes de deux couleurs.

Intervenant 25:35

Oui, juste bleu et rouge.

Intervenant 15:38

Exactement. On laisse donc les auditeurs imaginer l'immensité du chaos combinatoire si l'on décidait soudainement de rajouter une troisième couleur au problème.