Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Théorie de Ramsey

La théorie de Ramsey, qui porte le nom de P. Ramsey franc, étudie les conditions dans lesquelles l'ordre doit apparaître. Les problèmes dans la théorie de Ramsey posent 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 slogan souvent cité sur le sujet est: « le désordre complet est impossible ».

Supposons, par exemple, que n pigeons soient logés dans m trous de pigeon. Comment l'entier n doit-il être grand pour que nous puissions être sûrs qu'au moins un trou de pigeon loge au moins deux pigeons ? La réponse est donnée par le principe des tiroirs: si n > m, alors au moins un trou de pigeon accueillera au moins deux pigeons. Le théorème de Ramsey généralise ce principe expliqué précédemment.

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.

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 pour tout entier i compris entre 1 et c, il doit contenir 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.

Deux 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.

Voyez également

• L'analyse combinatoire