Théorie de ramsey

La théorie de Ramsey, qui porte le nom de Frank P. Ramsey, pose typiquement une question de la forme : combien d'éléments d'une certaine structure doivent être considérés pour qu'une propriété particulière se vérifie ? Un adage souvent cité sur le sujet est : « le désordre complet est impossible » (T.S. Motzkin).

Sommaire 1 Quelques exemples 2 Théorème de Ramsey fini 2.1 Généralisations du théorème de Ramsey fini 2.2 Théorème d'indécidabilité de Paris et Harrington 3 Théorème de Ramsey infini 4 Notes et références 5 Bibliographie 6 Articles connexes

Quelques exemples

Le premier exemple de résultat de cette forme est le principe des tiroirs, énoncé par Dirichlet en 1834.

Supposons, par exemple, que n chaussettes soient rangées dans m tiroirs. Existe-t-il une valeur de l'entier n à partir de laquelle nous puissions être sûrs qu' il existe au moins un tiroir contenant au moins deux chaussettes ? La réponse donnée par le principe des tiroirs est que c'est le cas dès que n > m. Le théorème de Ramsey généralise ce principe.

Un résultat typique dans la théorie de Ramsey commence par considérer une certaine structure mathématique, qui est alors découpée en morceaux. Quelle doit être la grandeur de la structure d'origine afin d'assurer qu'au moins un des morceaux possède une certaine propriété ?

Par exemple, considérons un graphe complet d'ordre n, c'est-à-dire ayant n sommets reliés à chaque autre sommet par un segment. Un graphe complet d'ordre 3 s'appelle un triangle. Colorons maintenant chaque côté en rouge ou bleu. Quelle grandeur n doit-il avoir afin d'assurer l'existence d'au moins un triangle bleu ou un triangle rouge ? Il se trouve que la réponse est 6. Voyez l'article sur le théorème de Ramsey pour une démonstration rigoureuse. Ce résultat peut s'exprimer autrement de la manière suivante : à une soirée à laquelle se rendent au moins six personnes, il y a au moins trois personnes qui se connaissent mutuellement ou au moins trois qui sont étrangères les unes aux autres.

Théorème de Ramsey fini

Ce résultat est également un cas particulier du théorème de Ramsey, qui indique que pour un nombre entier c donné, et pour des nombres donnés n₁, ..., n_c, il existe un nombre entier, noté R(n₁ ...,n_c ; c), tel que si les arêtes d'un graphe complet d'ordre R(n₁, ..., n_c ; c) sont colorées avec c différentes couleurs, alors il y a un entier i compris entre 1 et c, tel que le graphe contient un sous-graphe complet d'ordre n_i dont les arêtes sont toutes de la couleur i. Le cas particulier ci-dessus correspond à c = 2 et n₁=n₂= 3. La première borne inférieure a été obtenue par Paul Erdös, en utilisant la méthode probabiliste.

Généralisations du théorème de Ramsey fini

D'autres théorèmes principaux de la théorie de Ramsey sont :

• Le théorème de Van der Waerden : Pour tous entiers c et n donnés, il existe un nombre entier V, tel que si les éléments d'une progression arithmétique de V nombres sont colorés avec c différentes couleurs, alors elle doit contenir une progression arithmétique de la longueur n dont les éléments sont tous de la même couleur.
• Le théorème de Hales-Jewett : Pour tous entiers n et c donnés, il existe un nombre H tels que si les n × n × n × ... × n cellules d'un cube de dimension H sont colorées avec c couleurs, il doit exister une rangée, une colonne, etc. de longueur n dont les cellules sont toutes de la même couleur. Si par exemple, vous jouez au morpion dans un damier à k dimensions de côté n, avec k suffisamment grand c'est-à-dire avec « beaucoup de directions », la victoire étant attribuée au joueur qui aligne n pions le premier, vous gagnerez immanquablement si vous commencez la partie, même s'il y a un grand nombre de joueurs ou si n est grand.
• Le théorème de Schur énonce que, pour toute partition de l'ensemble des entiers strictements positifs en un nombre fini c de parties, l'une des parties contient trois entiers x, y, z tels que x + y = z, et plus précisément, qu'il existe un nombre S(c) tel que ce résultat soit vrai pour l'ensemble {1, 2, ..., S(c)}.

Théorème d'indécidabilité de Paris et Harrington

Le théorème de Paris et Harrington ^[1]montre qu'une variante du théorème de Ramsey fini est un énoncé indécidable de l'axiomatique de Peano. Historiquement ce théorème de 1977 a donné le premier exemple d'énoncé "proprement" arithmétique (i.e. non issu d'un codage "gödelien") indécidable dans l'arithmétique de Peano 46 ans après le théorème d'incomplétude de Gödel. Depuis on en connait d'autres comme le théorème de Goodstein. Ce résultat fut jugé assez important pour être inséré dans le handbook of mathematical logic, se voulant la synthèse de la discipline à ce moment, alors en cours de publication.

Théorème de Ramsey infini

On note [A]ⁿ l'ensemble des sous-ensembles de taille n de A.

• Théorème : Soit A un ensemble infini dénombrable et n un entier. Pour toute partition de [A]ⁿ il existe un sous ensemble infini B de A tel que [B]ⁿ soit inclus dans une des classes d'équivalence de la partition.

Si tout ensemble infini contient une partie dénombrable (conséquence de l'axiome du choix), on peut supposer A infini.

La version infinie du théorème implique la version finie.

Ce théorème a connu diverses généralisations notamment sur les partitions récursives^[2].

Il est aussi à l'origine de la notion de "cardinal de Ramsey", qui est un (très !) grand cardinal. κ est un cardinal de Ramsey ssi pour tout ensemble K de cardinal κ et toute partition en deux classes de Fin(K), il existe une partie "homogène" A de K de cardinal κ, ce qui veut dire qu'une des deux classes de la partition inclut Fin(A). Fin(X) désigne ici l'ensemble des parties finies de X.

Notes et références

Bibliographie

• Hao Wang, Popular Lectures on Mathematical Logic, ed. Dover, 1993, pp. 25-27 et pp. 83-86, ISBN 0-486-67632-3 . Qui aborde certains résultats de décidabilité et d'indécidabilité des versions finie et infinie du théorème dans l'axiomatique de Peano et une de ses extensions.

Articles connexes

• L'analyse combinatoire

• Portail des mathématiques