Club mathématique
de l'Université de Montréal

Accueil Journal Calendrier Archive

Le théorème de Ramsey

Le théorème de Ramsey est un des bijoux de mathématiques discrètes, utile, par exemple, en théorie des graphes, en théorie des ensembles, en théorie de complexité. Dans cette conférence on va regarder plusieurs de ses versions, on en prouvera au moins une, infinie, et on indiquera comment en déduire la version finie correspondante (ce qui permettra de parler quelques minutes de la compacité en logique).
La preuve du théorème est très simple et jolie. Le théorème général dit que si on colorie les parties à m éléments d’un ensemble infini X avec k couleurs, alors on peut trouver dans X une partie Y , infini et dénombrable, dont toutes les parties à m éléments ont la même couleur (k, m ∈ N).

Par Gena Hahn, (Professeur, DIRO, Université de Montréal)