Ê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éorème de Ramsey
Résumé
En mathématiques, et plus particulièrement en combinatoire, le théorème de Ramsey, dû à Frank Ramsey (en 1930), est un théorème fondamental de la théorie de Ramsey. Il affirme que pour tout n, tout graphe complet suffisamment grand dont les arêtes sont colorées contient des sous-graphes complets de taille n d'une seule couleur. En théorie des ensembles, une de ses généralisations, le théorème de Ramsey infini, permet de définir un type particulier de grand cardinal.
La théorie de Ramsey est souvent paraphrasée en affirmant qu'on ne peut pas avoir de désordre complet dans une structure assez grande, ou plutôt qu'une telle structure contient nécessairement des sous-structures ayant un certain ordre. Plus précisément, le théorème de Ramsey fini énonce que si l'on impose un tracé en un nombre fixé de couleurs et une taille fixée (par exemple 100), un « dessin » arbitraire suffisamment grand contiendra nécessairement un réseau de cette taille, donc formé de 100 traits adjacents, tous colorés de la même couleur. Un énoncé plus rigoureux demande un peu de vocabulaire de la théorie des graphes, rappelé ci-dessous.
Un graphe complet d'ordre n est un graphe simple non orienté ayant n sommets et dans lequel toute paire de sommets est reliée par une arête (il y a donc arêtes). Une coloration (des arêtes) d'un graphe est une application de l'ensemble des arêtes du graphe vers un ensemble de c « couleurs » ; une telle application sera appelée une c-coloration. Un graphe ainsi coloré est monochromatique si chaque arête a pour image la même couleur.
Avec ces définitions, on a :
Le plus petit entier N ayant cette propriété est noté R(n, n, ... , n).
Soit une 2-coloration en rouge et bleu du graphe complet à six sommets K. Cinq arêtes de ce graphe partent d'un sommet quelconque v, et donc, d'après le principe des tiroirs, trois d'entre elles au moins (mettons {v, r}, {v, s} et {v, t}) sont de la même couleur, qu'on peut supposer bleue sans perte de généralité.
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.