Les nombres diagonaux de Ramsey

Le BDF considère que la fête sera réussie si au moins trois invités se connaissent entre eux – car ils sauront alors initier une bonne dynamique pendant la soirée – ou si, au contraire, au moins trois convives ne se connaissent pas du tout – car les rencontres sont toujours stimulantes. Conscient des risques sanitaires, le BDF souhaite également inviter le moins de personnes possible. Combien de convives doit-il tirer au hasard pour respecter toutes ces contraintes ?

La réponse est 6. Mais combien aurait-il fallu inviter de personnes si, au lieu de trois, le BDF avait voulu garantir un groupe de k convives se connaissant les uns les autres ou au contraire ne se connaissent pas du tout entre eux ? Cette question se reformule ainsi en langage de théorie des graphes : déterminer le k^ème nombre diagonal de Ramsey R (k).

Traduisons le problème du BDF en termes mathématiques. Représentons chaque convive par un point (un sommet) sur une feuille, puis relions chaque paire de points par un trait (une arête), rouge si les deux convives qu’ils représentent se connaissent, bleu sinon. On a alors construit un graphe complet. Exiger qu’il existe soit un groupe de trois personnes se connaissant mutuellement, soit un groupe de trois personnes ne se connaissant pas entre elles revient donc à exiger qu’il existe, dans notre graphe, soit trois points reliés les uns aux autres par des arêtes rouges (un triangle rouge), soit trois points reliés les uns aux autres par des arêtes bleues (un triangle bleu). Déterminer R(3), c’est trouver le nombre minimal de sommets que doit comporter le graphe pour garantir que, quel que soit le coloriage des arêtes, il y ait forcément un triangle rouge ou un triangle bleu. Cinq sommets ne suffisent pas, comme le montre la figure de gauche.