La théorie de Ramsey est une branche des mathématiques qui cherche à répondre à la question : « Quelle est la taille minimale d’un système pour qu’une structure ordonnée particulière soit garantie d’apparaître ? ».
L’idée fondamentale est que dans un univers suffisamment grand et coloré de manière arbitraire, on ne peut pas éviter de trouver des sous-structures monochromes. Le théorème est souvent illustré en théorie des graphes.
- Un graphe complet $K_n$ est un graphe où chaque paire de sommets est reliée par une arête.
- Une clique de taille $m$ dans un graphe est un sous-ensemble de $m$ sommets où tous les sommets sont connectés les uns aux autres.
Pour toute paire d’entiers $(m, n)$, il existe un nombre entier minimal, noté $R(m, n)$, tel que pour tout graphe complet à $R(m, n)$ sommets dont les arêtes sont coloriées en deux couleurs (disons rouge ou bleu), il existe soit une clique rouge de taille $m$, soit une clique bleue de taille $n$.
Le Problème des Amis et des Étrangers
L’exemple le plus célèbre est le calcul de $R(3, 3)$.
Dans un groupe de 6 personnes, il y a forcément soit 3 personnes qui se connaissent mutuellement, soit 3 personnes qui sont de parfaits étrangers les uns pour les autres.
- Traduction en graphe : Les 6 personnes sont les sommets du graphe. On trace une arête rouge entre deux personnes si elles se connaissent, et une arête bleue si elles ne se connaissent pas.
- Ce que l’on cherche : On cherche soit un triangle rouge (une clique de 3 personnes qui se connaissent), soit un triangle bleu (une clique de 3 personnes qui ne se connaissent pas).
- Conclusion : Le théorème nous dit que $R(3, 3) = 6$. Avec 5 personnes, il est possible d’éviter cette situation, mais à partir de 6, c’est inévitable.
Les Nombres de Ramsey
Le théorème garantit que les nombres $R(m, n)$ existent, mais leur calcul est extrêmement difficile.
- On sait que $R(3,3)=6$, $R(3,4)=9$, $R(4,4)=18$.
- Le nombre $R(5,5)$ est inconnu à ce jour ! On sait seulement qu’il est compris entre 43 et 48.
- Le célèbre mathématicien Paul Erdős disait que si des extraterrestres surpuissants menaçaient de détruire la Terre à moins que nous ne calculions $R(5,5)$, nous devrions mobiliser tous nos ordinateurs et mathématiciens pour le trouver. Mais s’ils demandaient $R(6,6)$, nous devrions nous préparer à nous battre, car le calcul serait tout simplement hors de notre portée.