Preuve du Théorème de Ramsey: démonstration de la version finie à partir de la version infinie

Résumé du document

Matière scolaire : Mathématiques
Thèmes abordés : Théorie des graphes, théorème de Ramsey, coloration des arêtes.
Résumé : Le théorème de Ramsey est une propriété fondamentale de la théorie des graphes. Sa version infinie dit que pour tout entier k et toute partition finie des arêtes d'un graphe infini en k classes, il existe une clique ou une anti-clique infinie. Nous allons prouver la version finie du théorème de Ramsey à partir de sa version infinie.

Extraits

[...] Nous allons maintenant prouver la version finie du théorème de Ramsey à partir de sa version infinie. Soit G un graphe fini à n sommets. Nous allons montrer que pour tout entier il existe un entier tel que si les arêtes de G sont coloriées avec k couleurs, alors il existe une clique de taille dont les arêtes ont toutes la même couleur. Soit m = - 1 et soit H un graphe infini construit de la manière suivante : pour chaque sous-ensemble S de m sommets de nous ajoutons un sommet à H. [...]

[...] Comme H contient une clique infinie ou une anti-clique infinie, cela signifie qu'il existe un sous-ensemble S de m sommets de G dont les arêtes sont toutes de la même couleur, contredisant notre hypothèse. Nous avons donc prouvé que pour tout entier il existe un entier tel que si les arêtes de G sont coloriées avec k couleurs, alors il existe une clique de taille dont les arêtes ont toutes la même couleur. Cela est la version finie du théorème de Ramsey. [...]