ArithmétiqueThéorème · Glossaire
théorème de Ramsey
Le théorème de Ramsey affirme qu’un désordre assez grand contient forcément de l’ordre. Pour tous entiers positifs k et r, il existe N tel que tout coloriage en r couleurs des arêtes d’un graphe complet d’au moins N sommets contient k sommets dont toutes les arêtes mutuelles ont la même couleur. Dans la version infinie, pour tout entier positif p, toute partition finie des parties à p éléments d’un ensemble infini dénombrable possède un sous-ensemble infini dont toutes les parties à p éléments appartiennent à une même classe.
Sommaire
Ce que vous allez apprendre
- Relier le théorème au coloriage des arêtes d'un graphe complet.
- Refaire le raisonnement qui force un triangle monochrome parmi six personnes.
- Distinguer le résultat de Ramsey du principe des tiroirs et de la notion de clique.
- Reconnaître les hypothèses de complétude et de nombre fini de couleurs.
En clair
Imaginez six personnes réunies dans une pièce. Entre chaque paire, coloriez un trait en rouge si elles se connaissent et en noir si elles ne se connaissent pas. Même si ces relations semblent désordonnées, trois personnes se connaissent toutes deux à deux, ou trois personnes sont toutes étrangères les unes aux autres.
Le théorème de Ramsey étend cette idée : dès que le groupe est assez grand, une configuration uniforme d'une taille fixée devient inévitable. Il garantit son existence, même quand le coloriage a été choisi pour la dissimuler.
Définition
Un graphe complet à n sommets, noté Kn, relie chaque paire de sommets par une arête. On fixe une taille k et un nombre fini r de couleurs, puis on attribue une couleur à chaque arête. Le théorème de Ramsey fini affirme qu'il existe un entier N tel que tout coloriage en r couleurs des arêtes de KN contient un Kk monochrome : ses k sommets sont deux à deux reliés par des arêtes de la même couleur.
Dans la version à deux couleurs, le plus petit seuil qui garantit un Kk monochrome est un nombre de Ramsey. L'existence d'un seuil suffit au théorème ; sa valeur minimale peut être difficile à déterminer. La propriété est héréditaire : si un entier N convient, tout entier plus grand convient aussi, car on peut se restreindre à N sommets.
La version infinie porte sur un ensemble infini dénombrable A. Pour un entier positif p, on répartit en un nombre fini de classes toutes les parties de A qui ont p éléments. Il existe alors un sous-ensemble infini B dont toutes les parties à p éléments appartiennent à une même classe.
Le principe
Soient k et r deux entiers positifs, représentant respectivement la taille recherchée et le nombre de couleurs. Si le graphe complet possède au moins un certain nombre N de sommets et si chacune de ses arêtes reçoit l'une des r couleurs, alors il contient k sommets dont toutes les arêtes mutuelles ont la même couleur. Ce seuil dépend de k et de r, pas du coloriage choisi.
Quand l'utiliser
La forme finie s'applique à un graphe complet : chaque paire de sommets doit donc être reliée. La taille monochrome recherchée et le nombre de couleurs sont fixés avant de choisir le nombre de sommets. Enfin, chaque arête reçoit exactement l'une de ces couleurs. La conclusion garantit un sous-graphe complet monochrome, mais ne dit ni où il se trouve ni combien il y en a.
Un graphe incomplet constitue un contre-cas concret : trois sommets reliés par seulement deux arêtes rouges ne forment pas un triangle monochrome, car la troisième relation manque. Il faut alors compléter le modèle en donnant une couleur aux relations absentes, ou employer un résultat adapté aux graphes non complets. Avec une infinité de couleurs, la version infinie énoncée ne s'applique plus : la partition doit avoir un nombre fini de classes.
Un exemple, pas à pas
Six personnes, nommées A à F, sont représentées par les sommets de K6. Une arête rouge signifie « se connaissent » et une arête noire « ne se connaissent pas ». Ces relations sont supposées réciproques. On cherche trois personnes dont les trois relations ont la même couleur.
Étape 1. Depuis A partent cinq arêtes réparties entre deux couleurs.
Étape 2. Le principe des tiroirs assure qu'au moins trois de ces arêtes ont la même couleur. Le raisonnement étant identique pour les deux couleurs, détaillons le cas où AB, AC et AD sont rouges.
Étape 3. Si l'une des arêtes BC, BD ou CD est rouge, elle forme avec A un triangle rouge.
Étape 4. Si aucune n'est rouge, les trois sont noires et BCD est un triangle noir.
Étape 2. Le principe des tiroirs assure qu'au moins trois de ces arêtes ont la même couleur. Le raisonnement étant identique pour les deux couleurs, détaillons le cas où AB, AC et AD sont rouges.
Étape 3. Si l'une des arêtes BC, BD ou CD est rouge, elle forme avec A un triangle rouge.
Étape 4. Si aucune n'est rouge, les trois sont noires et BCD est un triangle noir.
Dans les deux cas, un triangle monochrome existe. Le contrôle consiste à vérifier les deux branches : une arête rouge parmi BC, BD et CD suffit pour la première ; leurs trois couleurs noires valident la seconde. Le dessin présente cette seconde branche sans dépendre de sa position dans la page.
En pratique
Dans un problème de relations entre personnes, on représente chaque paire par une arête et chaque type de relation par une couleur. Le théorème convient lorsque toutes les paires sont classées ; sinon, un modèle de graphe non complet est plus fidèle.
Pour prouver qu'une configuration homogène doit apparaître, on fixe d'abord sa taille et le nombre de couleurs. On cherche ensuite un seuil de Ramsey ou une borne suffisante. Une recherche exhaustive sert plutôt lorsque le nombre de sommets est petit et qu'il faut exhiber les configurations.
Face à un grand ensemble colorié, le bon geste consiste souvent à isoler un élément puis à regrouper ses relations par couleur. Ce tri local, illustré avec A, fait apparaître un sous-ensemble sur lequel le raisonnement peut continuer.
À ne pas confondre
Avec le principe des tiroirs. Ce principe garantit qu'une même catégorie reçoit plusieurs objets dès que les objets sont assez nombreux. Dans l'exemple, il donne trois arêtes de même couleur issues de A ; le théorème de Ramsey exige en plus que les trois sommets obtenus soient reliés entre eux de façon monochrome.
Avec une clique. Une clique est un ensemble de sommets deux à deux adjacents. Dans K6, les six sommets forment déjà une clique avant tout coloriage. Le résultat de Ramsey porte sur une clique dont les arêtes ont aussi une couleur commune : la couleur est le critère qui tranche.
Limites et pièges
Existence ne signifie pas seuil optimal. Le théorème affirme qu'un entier suffisant existe. Pour six personnes et deux couleurs, un triangle monochrome est garanti ; ce cas ne fournit pas automatiquement les seuils correspondant à des tailles plus grandes.
Monochrome ne signifie pas sommets de même couleur. Dans la forme présentée, ce sont les arêtes qui sont coloriées. Il faut contrôler toutes les arêtes entre les sommets retenus, pas une propriété portée séparément par chaque sommet.
Un grand graphe quelconque ne suffit pas. La garantie donnée ici suppose le graphe complet. Si des arêtes manquent, le symptôme est qu'une paire du groupe candidat n'a aucune couleur ; il faut traiter l'absence comme une couleur ou changer de théorème.
La finitude des classes est essentielle dans l'énoncé infini. Si chaque paire d'entiers reçoit une couleur qui lui est propre, aucune couleur ne peut couvrir toutes les paires d'un sous-ensemble infini. Il faut donc vérifier que la partition possède bien un nombre fini de classes.
Pour aller plus loin
Le graphe complet précise le support sur lequel le coloriage de Ramsey est défini : aucune paire de sommets n'y manque.
La fiche sur le sous-graphe aide à distinguer le graphe initial de la configuration monochrome que l'on en extrait.
Le principe des tiroirs fournit le premier regroupement du raisonnement sur six personnes et éclaire une technique fréquente des preuves de Ramsey.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres