Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Théorie de Ramsey
Résumé
En mathématiques, et plus particulièrement en combinatoire, la théorie de Ramsey, nommée d'après Frank Ramsey, tente typiquement de répondre à des questions 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 ? »
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 une arête (un graphe complet d'ordre 3 s'appelle un triangle). Colorons maintenant chaque arête en rouge ou bleu. Quelle grandeur n doit-il avoir afin d'assurer, quelle que soit la coloration choisie, l'existence d'au moins un triangle bleu ou un triangle rouge ? On peut démontrer que la réponse est 6. Ce résultat peut se reformuler 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.
Parmi les résultats de la théorie de Ramsey on peut distinguer les exemples suivants, à commencer par le théorème de Ramsey.
Théorème de Ramsey
Le résultat précédent est un cas particulier du théorème de Ramsey, qui indique que pour toute suite finie (n, ...
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.