théorie de Ramsey

COMBINATOIRE

La théorie de Ramsey répond à une question du type : combien d’éléments d’une structure donnée doivent être considérés pour qu’une propriété particulière soir vérifiée ?
Un premier exemple est celui connu sous le nom de principe des tiroirs : on range n chaussettes dans m tiroirs. Y a-t-il une valeur de n à partir de laquelle on est sûr d’avoir au moins 1 tiroir contenant au moins 2 chaussettes ? (posé par Dirichlet en 1834).
Plus généralement on considère une structure mathématique, on la découpe en plusieurs morceaux, et on s’intéresse à une propriété particulière. Quelle doit être la grandeur de la structure d’origine pour que la propriété soit vérifiée dans au moins 1 des morceaux ?
Ramsey étudie les coloriages des graphes et énonce plusieurs théorèmes, l’énoncé le plus général de ces théorèmes étant :
Théorème : 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.
Ce théorème a ensuite été généralisé : théorème de van der Waerden, théorème de Schur notamment.