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.
Définitions et énoncé 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 a démontré ce résultat sous une forme légèrement différente, correspondant à une application à un problème de logique formelle. é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 grapheLe sens donné ici à cette expression est différent de celui de l'article Coloration des arêtes d'un graphe, qui réclame de plus que deux arêtes adjacentes soient de couleurs distinctes. 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).
Exemple : calcul de R(3,3) = 6
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 tiroirsDont on peut voir la théorie de Ramsey comme une vaste généralisation., 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é. Si l'une des arêtes {r, s}, {r, t} ou {s, t} est également bleue, le triangle correspondant ({v, r, s} dans le premier cas) est entièrement bleu ; sinon, c'est le triangle formé par ces trois arêtes ({r, s, t}) qui est entièrement rouge. On vient donc de montrer que tout K 2-coloré contient un K monochromatique, et donc que R(3, 3) est inférieur ou égal à 6.
On peut également démontrer ce résultat par double dénombrement (ce qui permet de le généraliser) : on compte le nombre de triplets (ordonnés) de sommets (x, y, z) tels que l'arête {x, y} soit rouge et l'arête {y, z} bleue. Chaque sommet n'appartient à aucun tel triplet si les cinq arêtes partant de ce sommet sont de la même couleur, appartient à 1 × 4 = 4 triplets si quatre arêtes sont d'une même couleur, et à 2 × 3 = 6 triplets si trois arêtes sont d'une des couleurs et deux de l'autre. Il y a donc au plus 6 × 6 = 36 triplets de ce type. Or chaque triangle {x, y, z} non monochromatique contribue pour exactement 2 tels triplets. Il y a donc au plus 18 triangles non monochromatiques, et comme K contient triangles, deux d'entre eux au moins sont monochromatiques.
On peut réinterpréter ce résultat sous la forme suivante : dans tout graphe ayant au moins 6 sommets, trois d'entre eux sont connectés deux à deux, ou trois d'entre eux n'ont aucune connexion.
Cette question est fréquemment proposée sous forme d'un problème de mathématiques récréativesC'était par exemple un des énoncés de la de 1953. On le trouve également dans . ; la version précédente est souvent formulée en termes de « Théorème des amis et des étrangers » car dans une assemblée de six personnes trois d'entre elles se connaissent mutuellement ou trois d'entre elles s'ignorent mutuellementJean-Paul Delahaye, chronique "Logique & Calcul", Pour la Science, septembre 2017, Cinq énigmes pour la rentrée, paragraphe "Enigme 3 : se connaître ou s'ignorer", pages 82 et 83..
En revanche, il est possible de 2-colorer K sans aucun K monochromatique (une telle coloration, unique à isomorphisme près, est montrée à droite), ce qui démontre que R(3, 3) > 5.
Ainsi, R(3, 3) = 6.
Démonstration du théorème de Ramsey Cas de deux couleurs Dans le cas d'une 2-coloration, on va raisonner par récurrence sur r + s. La définition implique clairement que, pour tout n, R(n, 1) = R(1, n) = 1. Montrons que R(r, s) existe en en donnant un majorant explicite. On suppose (hypothèse de récurrence) que R(r − 1, s) et R(r, s − 1) existent. On va montrer (Lemme 1) que R(r, s) ≤ R(r − 1, s) +R(r, s − 1)
Démonstration du lemme. Considérons un graphe complet 2-coloré ayant R(r − 1, s) + R(r, s − 1) sommets. Choisissant un sommet v, on définit une partition des autres sommets en deux ensembles M et N par « w appartient à M si (v, w) est bleue » et « w appartient à N si (v, w) est rouge ». Le graphe ayant R(r − 1, s) + R(r, s − 1) = |M| + |N| + 1 sommets, on a |M| ≥ R(r − 1, s) ou |N| ≥ R(r, s − 1). Dans le premier cas, si M contient un K monochromatique rouge, il en est du même du graphe initial ; sinon, M contient un K monochromatique bleu, et donc M ∪ {v} contient un K bleu par définition de M. Échangeant les couleurs, on a le même résultat (pour N) dans le second cas. Le lemme est donc démontré, ce qui achève par récurrence la démonstration du théorème pour deux couleurs.
Remarque : dans la démonstration précédente, si R(r − 1, s) et R(r, s − 1) sont tous deux pairs, on peut légèrement améliorer l'inégalité du lemme., obtenant R(r, s) ≤ R(r − 1, s) + R(r, s − 1) − 1.
Cas général Le cas général se démontre également par récurrence, cette fois sur le nombre c de couleurs. Le résultat est trivial pour c = 1 et vient d'être démontré pour c = 2. Si c > 2, on va montrer l'inégalité suivante (Lemme 2) : R(n, … , n) ≤ R(n, … , n, R(n, n)).
Démonstration du lemme. Soit une c-coloration du graphe complet K ayant t sommets, où t = R(n, … , n, R(n, n)). Identifiant les couleurs c − 1 et c, on obtient une (c-1)-coloration du graphe qui, d'après l'hypothèse de récurrence, contient soit un K monochromatique de couleur i avec 1 ≤ i ≤ c − 2, soit un K de la couleur obtenue par identification. Le premier cas satisfait le lemme ; dans le second, on est donc ramené à un problème de 2-coloration et, par définition de R(n, n), on doit avoir soit un K (c − 1)-monochrome, soit un K c-monochrome. Dans les deux cas, ceci achève la démonstration du lemme. Par récurrence, le cas général est donc prouvé.
Nombres de Ramsey Les nombres R(r, s), et leurs extensions à un nombre de couleurs quelconque, sont appelés des nombres de Ramsey. Un majorant pour R(r, s) peut être déduit de la démonstration précédente ; d'autres arguments donnent des minorants (le premier fut obtenu par Paul Erdős à l'aide de la méthode probabiliste, qu'il développa à cette occasion).
Cependant, il reste un écart important entre les meilleurs minorants et majorants connus et il n'y a que très peu de couples (r, s) pour lesquels on a pu déterminer la valeur exacte de En général, déterminer un minorant L pour R(r, s) revient à exhiber une 2-coloration du graphe K ne contenant aucun K bleu et aucun K rouge ; une telle coloration du graphe K est souvent appelée un graphe (r, s, n). Des majorants sont souvent plus difficiles à établir : on doit, soit contrôler toutes les colorations possibles pour vérifier qu'il n'y a pas de contre-exemple, soit découvrir un argument mathématique prouvant qu'il n'y en a pas. Bien que des programmes informatiques sophistiqués évitent d'envisager toutes les 2-colorations possibles (par exemple en utilisant des arguments de symétrie, ou des techniques d'exploration d'arbres), la recherche de contre-exemples, ou la preuve par recherche exhaustive qu'il n'en existe pas, est une tâche que les logiciels existant ne peuvent accomplir que pour des graphes de petite taille : la complexité d'une recherche exhaustive est en effet, pour un graphe de n sommets, de l'ordre de O(2) (en utilisant la notation de Landau) 2.6 Ramsey Theory from Mathematics Illuminated.Plus précisément, K possède n(n–1)/2 arêtes ; il y a donc à isomorphisme près (par permutation des sommets) un nombre de 2-colorations au moins égal à n(n–1)/2n! (parce qu'une permutation des sommets peut ne pas changer la coloration)..
Comme démontré plus haut, R(3, 3) = 6. Il est facile de voir que R(4, 2) = 4 et, plus généralement, que R(s, 2) = s pour tout s (un graphe monochromatique de s − 1 sommets montre que R(s, 2) ≥ s ; un graphe de s sommets non entièrement rouge contient une arête bleue, donc un K monochromatique). Utilisant alors le lemme 1 de la démonstration précédente, on voit que et donc que R(4, 4) ≤ R(4, 3) + R(3, 4) ≤ 18. Parmi les 6,4.10 2-colorations du graphe complet à 16 sommets (identifiées aux graphes non orientés quelconques à 16 sommets, en convenant qu'on colorie en bleu une arête si elle relie deux sommets du graphe non orienté, et en rouge sinon), il n'y a (à isomorphisme près) que deux graphes (4, 4, 16) (c'est-à-dire des 2-colorations du graphe complet K sans aucun K monochromatique) et un seul graphe (4, 4, 17) (le graphe de Paley d'ordre 17) parmi les 2,46.10 2-colorations de K. (ces nombres montrent bien la difficulté d'une recherche exhaustive) ; ce résultat fut démontré par Evans, Pulham et Sheehan en 1979. Il en résulte que R(4, 4) = 18. Enfin., R(4, 5) = 25.
On ignore la valeur exacte de R(5, 5), mais on sait depuis 1997 qu'elle est comprise entre 43 et 49. (en 2017, cet encadrement a été légèrement amélioré : on sait désormais que R(5,5) est inférieur ou égal à 48) ; il est cependant conjecturé que 43 est la vraie valeur. Erdős a illustré la difficulté d'une détermination exacte en demandant d'imaginer qu'une armée extra-terrestre bien plus puissante que nous débarque et demande la valeur de R(5, 5), faute de quoi ils détruiront notre planète. Dans ce cas, dit-il, nous devrions mobiliser tous nos ordinateurs et tous nos mathématiciens dans l'espoir de déterminer ce nombre. Mais s'ils nous demandaient R(6, 6), nous ferions mieux d'essayer de détruire les extra-terrestres..
McKay, Radziszowski et Exoo ont employé des méthodes de construction de graphe assistée par ordinateur pour formuler en 1997 la conjecture selon laquelle R(5, 5) vaut exactement 43. Ils construisirent une liste de 656 graphes de type (5, 5, 42), et arrivèrent à la même liste par plusieurs méthodes distinctes, les amenant à conjecturer que leur liste est complète ; aucun de ces 656 graphes ne peut être étendu à un graphe (5, 5, 43)..
Pour R(r, s) avec r, s > 5, on ne connait que des bornes assez lâches. Les minorants pour R(6, 6) et R(8, 8) n'ont d'ailleurs pas été améliorés depuis, respectivement, 1965 et 1972Pour plus de données, accompagnées de références, voir ..
La table suivante donne R(r, s) pour les valeurs de r et s jusqu'à 10 (avec r ≤ s, la table étant symétrique puisque R(r, s) = R(s, r)). Lorsque la valeur exacte n'a pas été déterminée, la table donne le meilleur encadrement connu. r,s 1 2 3 4 5 6 7 8 9 10 1 1 2 1 2 3 1 3 6 4 1 4 9 18 5 1 5 14 25 43–48 6 1 6 18 36–41 58–87 102–165 7 1 7 23 49–61 80–143 113–298 205–540 8 1 8 28 58–84 101–216 132–495 217–1031 282–1870 9 1 9 36 73–115 126–316 169–780 241–1713 317–3583 565–6588 10 1 10 40–42 92–149 144–442 179–1171 289–2826 331–6090 581–12677 798–23556
Comportement asymptotique L'inégalité R(r, s) ≤ R(r − 1, s) + R(r, s − 1) implique par récurrence que
Ce résultat, dû à Paul Erdős et George Szekeres, donne en particulier, lorsque r = s, que
Un minorant exponentiel,