théorème de Ramsey

COMBINATOIRE

Un graphe à n sommets est dit complet si tout couple de sommets est relié par une arête. On le note Kn.
• Le théorème de Ramsey fini : r étant un entier naturel, il existe un entier naturel n tel que pour tout coloriage des arêtes de Kn en deux couleurs, il existe un sous-graphe de type Kr dont toutes les arêtes ont la même couleur.
Si l’entier n convient alors n+1 convient aussi puisque Kn+1 contient Kn qui contient le sous-graphe monochrome Kr.

Le théorème se généralise avec des colorations de plus de deux couleurs.
Soient k et r deux entiers naturels. Alors il existe un entier n
tel que, pour tout coloriage des arêtes de Kn en r couleurs (Ci)i,r, le graphe
Kn contient un sous-graphe de type Kk (à k sommets), monochrome.

• Théorème de Ramsey infini :
Soit A un ensemble infini dénombrable et n un entier. Pour toute partition finie de [A]n (ensemble des sous-ensembles de taille finie de A), il existe un sous ensemble infini B de A tel que [B]n soit inclus dans une des classes d’équivalence de la partition.