théorie de Ramsey

Prenez six points et reliez chaque paire. Coloriez chaque lien en rouge ou en noir, sans règle particulière. Malgré cette liberté, trois points formeront toujours un triangle dont les trois liens ont la même couleur. Avec seulement cinq points, on peut encore éviter un tel triangle.

La théorie de Ramsey étudie ce basculement : une structure assez grande force l'apparition d'un motif homogène, même quand son découpage cherche à le dissimuler. Elle ne prétend pas que tout devient ordonné ; elle garantit qu'une petite zone d'ordre subsiste.

La théorie de Ramsey est une branche de la combinatoire consacrée aux motifs homogènes inévitables. On part d'un ensemble d'objets, on répartit certaines de ses sous-structures en un nombre fini de classes, souvent appelées couleurs, puis on cherche une sous-structure dont tous les éléments appartiennent à une même classe. Dans un graphe complet, les sommets forment l'ensemble support, chaque paire de sommets forme une arête, et ce sont les arêtes qui sont réparties en classes, autrement dit colorées.

Dans la version infinie donnée par le théorème de Ramsey, la lettre A désigne un ensemble infini dénombrable, n un entier positif et [A]ⁿ l'ensemble des parties de A ayant exactement n éléments. Si une coloration c répartit [A]ⁿ entre un nombre fini de couleurs, il existe un sous-ensemble infini B de A et une couleur i tels que :

Autrement dit, toutes les parties de B à n éléments reçoivent la même couleur. Les versions finies demandent plutôt la taille minimale garantissant un motif fixé. Le nombre R(3,3) vaut 6 : toute coloration rouge-noir des arêtes d'un graphe complet à six sommets contient un triangle monochromatique, tandis qu'une coloration à cinq sommets peut l'éviter.

Colorions en rouge ou en noir chaque arête reliant six sommets A, B, C, D, E et F. Le schéma isole le raisonnement qui force un triangle monochromatique.

Données.
Nombre de sommets : 6.
Nombre de couleurs : 2.
Motif recherché : 3 sommets reliés par 3 arêtes d'une seule couleur.

Étape 1. Le sommet A possède cinq arêtes incidentes. Le principe des tiroirs garantit qu'au moins trois ont la même couleur. Supposons, sans perdre de généralité, que AB, AC et AD soient rouges.

Étape 2. Si l'une des arêtes BC, CD ou DB est rouge, elle forme avec A un triangle rouge. Par exemple, BC rouge donne le triangle ABC.

Étape 3. Si aucune de ces trois arêtes n'est rouge, elles sont toutes noires. Les sommets B, C et D forment alors un triangle noir.

Contrôle. Les deux cas épuisent les possibilités : une arête rouge existe parmi BC, CD et DB, ou aucune n'est rouge. Dans les deux cas, un triangle monochromatique apparaît. Sur les cinq sommets de K5, colorier en rouge les cinq arêtes d'un cycle C5 et en noir les cinq autres arêtes évite tout triangle monochromatique et montre que six est bien le seuil minimal.

Pour analyser une coloration finie, on précise d'abord les objets colorés, le nombre de couleurs et le motif homogène recherché. Dans le cas des six sommets, les objets colorés sont les arêtes et le motif est un triangle.

Pour prouver qu'un motif est inévitable, on fixe un objet puis on regroupe ses relations par couleur. Le principe des tiroirs fournit souvent un premier groupe assez grand ; un raisonnement par cas termine ensuite la preuve. Une construction explicite est préférable lorsqu'on veut montrer que le seuil ne peut pas être abaissé.

Pour distinguer existence et calcul, on vérifie la question posée. Un théorème de Ramsey peut assurer qu'un seuil fini existe sans donner immédiatement sa valeur minimale. Déterminer cette valeur exige alors deux résultats : une garantie au seuil proposé et un contre-exemple juste en dessous.

Principe des tiroirs. Il force une répétition quand davantage d'objets que de cases sont utilisés. La théorie de Ramsey force une sous-structure dont plusieurs relations ont la même couleur. Dans la preuve à six sommets, le principe des tiroirs sélectionne trois arêtes issues de A ; le raisonnement de Ramsey force ensuite un triangle.

Coloriage propre d'un graphe. Un coloriage propre attribue des couleurs aux sommets de façon que deux voisins diffèrent. Le cas R(3,3) colorie au contraire toutes les arêtes d'un graphe complet et cherche trois arêtes de même couleur. Le support colorié et la contrainte ne sont donc pas les mêmes.

Nombre de Ramsey et théorème infini. Un nombre de Ramsey est un seuil fini associé à des motifs et à des couleurs fixés. Le théorème infini porte sur une partition finie des parties à n éléments d'un ensemble infini dénombrable. R(3,3)=6 relève de la première formulation, pas de la seconde.

Sous le seuil. Cinq sommets ne suffisent pas à forcer un triangle monochromatique : un cycle rouge de longueur cinq, complété par cinq arêtes noires, évite les triangles monochromatiques. Il faut donc fournir un contre-exemple avant d'affirmer qu'une borne est minimale.

Nombre fini de classes. Dans l'énoncé infini présenté ici, la partition de [A]ⁿ doit avoir un nombre fini de classes. Si chaque partie reçoit sa propre couleur, aucun sous-ensemble infini ne peut être homogène. Il faut conserver l'hypothèse de finitude.

Existence sans valeur explicite. La garantie d'un seuil ne fournit pas automatiquement sa valeur exacte ni une méthode rapide pour la calculer. Il faut distinguer une preuve d'existence, une borne supérieure et la détermination du minimum.

Motif garanti, ordre total non garanti. Un coloriage peut rester très irrégulier dans son ensemble. Le théorème n'en extrait qu'une sous-structure homogène de la taille demandée. Il faut donc identifier précisément le motif promis au lieu de conclure que toute la structure devient uniforme.

L'article L’ordre selon Ramsey prolonge l'idée centrale : les configurations suffisamment grandes font apparaître des régularités malgré un découpage arbitraire.

Le glossaire consacré au principe des tiroirs détaille l'outil de comptage utilisé dans la preuve de R(3,3)=6. Ce principe fournit la première sélection homogène, avant l'analyse des arêtes restantes.

Le théorème de van der Waerden et le théorème de Schur, cités parmi les prolongements de la source, déplacent la même recherche de régularité vers des configurations arithmétiques.