À quoi sert le nombre de Graham ?

Réponse publiée sur Quora

Voici un petit problème de maths:

Soit un hypercube de dimension n dont on relie tous les couples de sommets pour obtenir un graphe complet à $2^n$sommets. Si l’on colorie chacune des $2^{n–1}$arêtes du graphe en bleu ou en rouge, quelle est la plus petite valeur de n telle que, pour chaque façon de colorier le graphe, il existe un sous-graphe complet monochrome sur quatre sommets coplanaires ?

On ne connaît pas la solution de ce problème, mais Ronald Graham a montré en 1977 que n était inférieur à un nombre énorme , le “Nombre de Graham” , qui a longtemps été le plus grand nombre utilisé dans une démonstration mathématique.

Depuis on a réduit le “majorant” pour le problème ci-dessus, mais d’autres problèmes comme le Théorème de Kruskal ont nécessité d’utiliser des nombres encore plus grands.

Sur les notations utilisées pour écrire ces nombres, voir Très très très grands nombres - Pourquoi Comment Combien