4. Théorèmes d'existence
Le théorème de Ramsey et celui de Hall-König, dont nous donnons les énoncés maintenant, jouent un rôle spécial en combinatoire. Ils assurent l'existence de certaines configurations dans des conditions très générales et ont ainsi trouvé de nombreuses applications.
Supposons que l'on ait un graphe de six sommets, dans lequel deux sommets distincts sont joints par une arête « coloriée » en bleu ou en rouge. Démontrons la propriété (P) suivante : Il existe un triangle dont les trois arêtes ont la même couleur. Considérons en effet les cinq arêtes issues d'un sommet donné S1 du graphe. Nécessairement trois de ces arêtes ont la même couleur, disons bleue ; appelons-les S1S2, S1S3 et S1S4. Si l'une des arêtes S2S3, S2S4, S3S4 est bleue, disons S2S3, le triangle S1S2S3 est bleu. Sinon les arêtes S2S3, S2S4, S3S4 sont rouges, mais alors le triangle S2S3S4 est rouge. La propriété (P) est ainsi vérifiée. L'argument essentiel qui a été utilisé est le principe des tiroirs : si l'on met n objets dans p tiroirs (p ≤ n), alors le nombre des objets dans au moins un tiroir est supérieur ou égal à n/p. Le théorème de Ramsey peut être considéré comme une généralisation de ce principe.
Théorème de Ramsey. Soit X un ensemble de n éléments et supposons donnés d'abord trois entiers p, q, r satisfaisant à p ≥ r, q ≥ r et r ≥ 1, ensuite une partition de l'ensemble de toutes les parties de X de cardinal r, en deux classes P et Q. Alors il existe un entier N(p, q, r) ne dépendant que des entiers p, q, r et non pas de l'ensemble X tel que la propriété (P′) suivante soit vérifiée : Si n ≥ N(p, q, r), il existe ou bien une partie A de X de p éléments qui a tous ses sous-ensembles de cardinal r dans P, ou bien une partie B de q
… pour nos abonnés, l'article se prolonge sur 8 pages…
