Six convives suffisent-ils ? Le nombre de Ramsey R(3)

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente. Pour démarrer notre analyse d'aujourd'hui, imaginons une situation très concrète, presque très terre-à-terre. Un bureau des fêtes étudiants doit organiser une soirée.

Intervenant 20:12

D'accord.

Intervenant 10:13

Contraintes sanitaires obligent, il faut inviter le moins de monde possible. Mais pour que l'ambiance prenne vraiment, il y a une exigence absolue. On veut s'assurer que parmi les invités, il y ait au moins trois personnes qui se connaissent déjà très bien, ou à l'inverse, trois personnes qui soient de parfaits inconnus.

Intervenant 20:30

La théorie des graphes

Intervenant 10:45

Et c'est bien la mission de notre plongée du jour. Comment est-ce qu'on transforme un comportement humain en pure logique mathématique ? Pour visualiser, on peut imaginer chaque invité comme un point dessiné sur une feuille.

Intervenant 20:58

Ouais, tout à fait.

Intervenant 10:59

Si les deux personnes se connaissent, on trace, disons, un trait rouge entre

Intervenant 21:03

elles.

Intervenant 11:04

Et si elles ne se sont jamais vues, on trace un trait bleu.

Intervenant 21:07

Voilà, l'objectif devient complètement géométrique, du coup, on cherche le nombre minimal de points qu'il faut pour forcer l'apparition d'un triangle d'une seule couleur. Et ça, quelle que soit la façon dont on dessine les lignes.

Intervenant 11:19

Un triangle rouge pour trois amis ou bleu pour trois inconnus.

Intervenant 21:22

Exactement. Et ce seuil critique s'apporte un nom très précis en mathématiques, c'est le quaième nombre diagonal de Ramsey, qu'on note R de K. Et pour notre petite soirée, K vaut 3.

Intervenant 11:33

R de 3.