Voir la source de Théorème de Ramsey

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 [[graphe (mathématiques discrètes)|arêtes]] sont colorées contient des sous-[[Graphe complet|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<ref name=ramsey>{{harvsp|Ramsey|1930|texte=Ramsey (1930)}} a démontré ce résultat sous une forme légèrement différente, correspondant à une application à un problème de [[logique formelle]].</ref> é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.

[[Image:Complete graph K5.svg|vignette|Le graphe complet à cinq sommets ''K''{{ind|5}}.]]
Un graphe complet d'ordre ''n'' est un [[graphe (mathématiques discrètes)|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 {{nobr|''n''(''n'' – 1)/2}} arêtes). Une coloration (des arêtes) d'un graphe<ref>Le 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.</ref> 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 :
{{Théorème|Théorème de Ramsey (fini)<ref name=ramsey/>|Pour tout entier ''c'' et toute suite d'entiers (''n''{{ind|1}}, ''n''{{ind|2}}, … , ''n{{ind|c}}''), il existe un entier ''N'' tel que pour toute coloration en ''c'' couleurs du graphe complet ''K{{ind|N}}'' d'ordre ''N'', il existe une couleur ''i'' et un sous-graphe complet de ''K{{ind|N}}'' d'ordre ''n{{ind|i}}'' qui soit monochromatique de couleur ''i''.}}
Le plus petit entier ''N'' ayant cette propriété est noté ''R''(''n''{{ind|1}}, ''n''{{ind|2}}, … , ''n{{ind|c}}'').

== Exemple : calcul de ''R''(3,3) = 6 ==
[[Image:RamseyTheory K5 no mono K3.svg|cadre|Une 2-coloration de ''K''{{ind|5}} sans aucun ''K''{{ind|3}} monochromatique.]]

Soit une 2-coloration en rouge et bleu du graphe complet à six sommets ''K''{{ind|6}}. Cinq arêtes de ce graphe partent d'un sommet quelconque ''v'', et donc, d'après le [[principe des tiroirs]]<ref>Dont on peut voir la théorie de Ramsey comme une vaste généralisation.</ref>, 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''{{ind|6}} 2-coloré contient un ''K''{{ind|3}} monochromatique, et donc que ''R''(3, 3) est inférieur ou égal à 6.

On peut également démontrer ce résultat par [[preuve par double dénombrement|double dénombrement]] (ce qui permet de le généraliser) : on compte le nombre de [[n-uplet|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&nbsp;×&nbsp;4&nbsp;=&nbsp;4 triplets si quatre arêtes sont d'une même couleur, et à 2&nbsp;×&nbsp;3&nbsp;=&nbsp;6 triplets si trois arêtes sont d'une des couleurs et deux de l'autre. Il y a donc au plus 6&nbsp;×&nbsp;6&nbsp;=&nbsp;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''{{ind|6}} contient <math>{6\choose3}=20</math> 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éatives]]<ref>C'était par exemple un des énoncés de la ''[[William Lowell Putnam Mathematical Competition|{{Lang|en|Putnam Competition}}]]'' de 1953. On le trouve également dans {{Ouvrage|langue=en|auteur1=Eugene P. Northrop|titre=Riddles in mathematics|traduction titre=Fantaisies et paradoxes mathématiques|éditeur=|année=1963}}.</ref> ; 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 mutuellement<ref>[[Jean-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.</ref>.

En revanche, il est possible de 2-colorer ''K''{{ind|5}} sans aucun ''K''{{ind|3}} monochromatique (une telle coloration, unique [[À quelque chose près|à isomorphisme près]], est montrée à droite), ce qui démontre que ''R''(3, 3)&nbsp;>&nbsp;5.

Ainsi, ''R''(3, 3)&nbsp;=&nbsp;6.

== Démonstration du théorème de Ramsey ==
=== Cas de deux couleurs ===
Dans le cas d'une 2-coloration, on va [[raisonnement par récurrence|raisonner par récurrence]] sur ''r''&nbsp;+&nbsp;''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''&nbsp;−&nbsp;1, ''s'') et ''R''(''r'', ''s''&nbsp;−&nbsp;1) existent. On va montrer ('''Lemme 1''') que ''R''(''r'', ''s'') ≤ ''R''(''r''&nbsp;−&nbsp;1, ''s'') +''R''(''r'', ''s''&nbsp;−&nbsp;1)

'''Démonstration du lemme.''' Considérons un graphe complet 2-coloré ayant ''R''(''r''&nbsp;−&nbsp;1, ''s'') + ''R''(''r'', ''s''&nbsp;−&nbsp;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{{ind|s}}'' monochromatique rouge, il en est du même du graphe initial ; sinon, ''M'' contient un ''K''{{ind|''r''–1}} monochromatique bleu, et donc ''M'' ∪ {''v''} contient un ''K{{ind|r}}'' 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''&nbsp;−&nbsp;1, ''s'') et ''R''(''r'', ''s''&nbsp;−&nbsp;1) sont tous deux pairs, on peut légèrement améliorer l'inégalité du lemme<ref>{{lien web|langue=en|url=http://www.cut-the-knot.org/Curriculum/Combinatorics/ThreeOrThree.shtml#inequality2 |titre=Party Acquaintances}}.</ref>, obtenant ''R''(''r'', ''s'') ≤ ''R''(''r''&nbsp;−&nbsp;1, ''s'') + ''R''(''r'', ''s''&nbsp;−&nbsp;1)&nbsp;−&nbsp;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''{{ind|1}}, … , ''n{{ind|c}}'') ≤ ''R''(''n''{{ind|1}}, … , ''n''{{ind|''c''−2}}, ''R''(''n''{{ind|''c''−1}}, ''n{{ind|c}}'')).

'''Démonstration du lemme.''' Soit une ''c''-coloration du graphe complet ''K{{ind|t}}'' ayant ''t'' sommets, où ''t'' = ''R''(''n''{{ind|1}}, … , ''n''{{ind|''c''−2}}, ''R''(''n''{{ind|''c''−1}}, ''n{{ind|c}}'')). Identifiant les couleurs ''c''&nbsp;−&nbsp;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{{ind|n{{ind|i}}}}'' monochromatique de couleur ''i'' avec 1 ≤ ''i'' ≤ ''c''&nbsp;−&nbsp;2, soit un ''K''{{ind|''R''(''n''{{ind|''c''−1}}, ''n{{ind|c}}'')}} 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''{{ind|''c''−1}}, ''n{{ind|c}}''), on doit avoir soit un ''K''{{ind|''n''{{ind|''c''−1}}}} (''c''&nbsp;−&nbsp;1)-monochrome, soit un ''K{{ind|n{{ind|c}}}} 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 {{nobr|''R''(''r'', ''s'').}} En général, déterminer un minorant ''L'' pour ''R''(''r'', ''s'') revient à exhiber une 2-coloration du graphe ''K''{{ind|''L''−1}} ne contenant aucun ''K{{ind|r}}'' bleu et aucun ''K{{ind|s}}'' rouge ; une telle coloration du graphe ''K{{ind|n}}'' 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{{exp|''n''(''n ''−1)/2}}) (en utilisant la [[Comparaison asymptotique|notation de Landau]])<ref>{{en}} [http://www.learner.org/channel/courses/mathilluminated/units/2/textbook/06.php 2.6 Ramsey Theory from Mathematics Illuminated].</ref>{{,}}<ref>Plus précisément, ''K{{ind|n}}'' possède ''n''(''n''–1)/2 arêtes ; il y a donc à [[isomorphisme de graphes|isomorphisme]] près (par permutation des sommets) un nombre de 2-colorations au moins égal à ''n''(''n''–1)/2''n''! (parce qu'une permutation des sommets peut ne pas changer la coloration), mais montrer que deux graphes sont isomorphes est un [[problème NP-complet]], c'est pourquoi l'on ne peut guère améliorer l'estimation donnée pour une approche exhaustive.</ref>.

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''&nbsp;−&nbsp;1 sommets montre que ''R''(''s'', 2)&nbsp;≥&nbsp;''s'' ; un graphe de ''s'' sommets non entièrement rouge contient une arête bleue, donc un ''K''{{ind|2}} monochromatique). Utilisant alors le lemme 1 de la démonstration précédente, on voit que {{nobr|1=''R''(4, 3) ≤ ''R''(4, 2) + ''R''(3, 3) − 1 = 9,}} et donc que ''R''(4, 4)&nbsp;≤&nbsp;''R''(4, 3)&nbsp;+&nbsp;''R''(3, 4)&nbsp;≤&nbsp;18. Parmi les 6,4.10{{22}} 2-colorations du graphe complet à 16 sommets (identifiées aux [[Graphe non orienté|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''{{ind|16}} sans aucun ''K''{{ind|4}} monochromatique) et un seul graphe (4, 4, 17) (le [[graphe de Paley]] d'ordre 17) parmi les 2,46.10{{26}} 2-colorations de ''K''{{ind|17}}<ref>{{lien web|id=McKay, Ramsey Graphs|langue=en|url=http://cs.anu.edu.au/~bdm/data/ramsey.html|titre=Ramsey Graphs|auteur=B. McKay}}.</ref> (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)&nbsp;=&nbsp;18. Enfin<ref>{{article|langue=en|titre=R(4, 5)&nbsp;=&nbsp;25|auteur=[[Brendan Damien McKay|Brendan D. McKay]] et {{Lien|Stanisław Radziszowski|texte=Stanislaw P. Radziszowski}}|journal=Journal of Graph Theory|année=1995|mois=mai|doi=10.1002/jgt.3190190304}}.</ref>, ''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<ref>{{article |langue=en |prénom=G. |nom=Exoo |titre=A lower bound for ''R''(5, 5) |journal=Journal of Graph Theory |volume=13 |année=1989 |doi=10.1002/jgt.3190130113 |pages=97-98 }}.</ref>{{,}}<ref name=SubraphCounting/> (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<ref>{{lien arXiv|auteur1=|auteur2=|eprint=1703.08768v2|titre=<math>R(5,5) \leq 48</math>|année=2017|class=math.CO|nom1=Vigleik Angeltveit|nom2=Brendan McKay}}</ref>) ;  il est cependant conjecturé que 43 est la vraie valeur<ref name="SubraphCounting" />. 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<ref>{{Ouvrage|langue=en|auteur1=[[Joel Spencer|Joel H. Spencer]]|titre=Ten Lectures on the Probabilistic Method|sous-titre=Second Edition|éditeur=[[Society for Industrial and Applied Mathematics|SIAM]]|année=1994|pages totales=88|passage=4|isbn=978-0-89871-325-1|lire en ligne=https://books.google.fr/books?id=Kz0B0KkwfVAC&pg=PA4}}.</ref>.

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)<ref name=SubraphCounting>{{article|langue=en|url=http://cs.anu.edu.au/~bdm/papers/r55.pdf|titre=Subgraph counting identities and Ramsey numbers|auteur=Brendan D. McKay|auteur2=Stanislaw P. Radziszowski|journal=Journal of Combinatorial Theory|année=1997}}.</ref>.

Pour ''R''(''r'', ''s'') avec ''r'', ''s''&nbsp;>&nbsp;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 1972<ref name="Survey">Pour plus de données, accompagnées de références, voir {{Article|langue=en|url=http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1/0|revue=Dynamic Surveys|titre=Small Ramsey numbers|vol=DS1|jour=12|mois=1|année=2014|auteur=Stanisław Radziszowski}}.</ref>.

La table suivante<ref name="Survey" /> donne ''R''(''r'', ''s'') pour les valeurs de ''r'' et ''s'' jusqu'à 10 (avec ''r''&nbsp;≤&nbsp;''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.
{| class="wikitable"
! ''r'',''s''
! width="80" | 1
! width="80" | 2
! width="80" | 3
! width="80" | 4
! width="80" | 5
! width="80" | 6
! width="80" | 7
! width="80" | 8
! width="80" | 9
! width="80" | 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''&nbsp;−&nbsp;1, ''s'') + ''R''(''r'', ''s''&nbsp;−&nbsp;1) implique par récurrence que
:<math>R(r,s) \leq \binom{r+s-2}{r-1}. </math>
Ce résultat, dû à [[Paul Erdős]] et [[George Szekeres]], donne en particulier, lorsque ''r'' = ''s'', que
:<math>R(s,s) \leq (1 + o(1))\frac{4^{s-1}}{\sqrt{\pi s}}.</math>
Un minorant exponentiel,
:<math>R(s,s) \ge(1 + o(1)) \frac s{\sqrt2{\rm e}} 2^{\frac s2},</math>
fut obtenu par Erdős en 1947<ref>{{article|langue=en
 | nom = Erdős | prénom = Paul
 | journal=[[Bulletin of the American Mathematical Society|Bull. Amer. Math. Soc.]]
 | pages = 292-294
 | titre = Some remarks on the theory of graphs
 | volume = 53
 | année = 1947
 | doi = 10.1090/S0002-9904-1947-08785-1
 | numéro = 4|url=http://projecteuclid.org/euclid.bams/1183510596}}.</ref> et joua un rôle essentiel dans son introduction de la [[méthode probabiliste]] en combinatoire. L'écart entre ces deux bornes est important : pour ''s''&nbsp;=&nbsp;10, par exemple, on en déduit que 101 ≤ ''R''(10, 10) ≤ {{nombre|48620}}. Cependant, l'ordre de [[croissance exponentielle]] n'a pu être amélioré depuis cette époque (on a seulement des résultats équivalents à <math>(\ln2)n<2\ln R(n,n)<(4\ln2) n</math>) ; de plus, on ne connait pas de construction explicite de graphes (''n'', ''n'', ''L'') (justifant le minorant ''L'') pour lesquels ''L'' serait une [[fonction exponentielle]] de ''n''. Les meilleures bornes actuellement connues de ces nombres de Ramsey diagonaux sont<ref>{{article|langue=en
 | nom = Spencer | prénom = J.
 | journal = J. Combin. Theory Ser. A
 | pages = 108-115
 | titre = Ramsey's theorem – a new lower bound
 | volume = 18
 | année = 1975
 | doi = 10.1016/0097-3165(75)90071-0}}.</ref>{{,}}<ref>{{article|langue=en
 | nom = Conlon | prénom = D.
 | journal =[[Annals of Mathematics]]
 | pages = 941-960
 | titre = A new upper bound for diagonal Ramsey numbers
 | volume = 170
 | année = 2009
 | doi = 10.4007/annals.2009.170.941
 | numéro = 2}}.</ref> :
:<math>(1+o(1))\frac{\sqrt2s}{\rm e} 2^{\frac s2}\le R(s,s)\le s^{-\frac{c\log s}{\log\log s}}4^s.</math>

On a pu établir que les nombres de Ramsey ''R''(3, ''t'') sont d'ordre <math>\Theta(\tfrac{t^2}{\log t})</math> ; ce résultat est équivalent à dire que le plus petit [[Stable (théorie des graphes)|stable]] dans un [[graphe sans triangle]] à ''n'' sommets est d'ordre <math>\Theta(\sqrt{n\log n})</math>. Plus généralement, pour ''R''(''s'', ''t'') avec ''s'' fixé et ''t'' tendant vers l'infini, les meilleures bornes connues sont<ref>Dues respectivement à {{article|langue=en
 | nom1 = Bohman | prénom1 = Tom
 | nom2 = Keevash | prénom2 = Peter
 | journal = Invent. Math.
 | pages = 291-336
 | titre = The early evolution of the H-free process
 | volume = 181
 | année = 2010
 | doi = 10.1007/s00222-010-0247-x
 | numéro = 2}} et à {{article|langue=en
 | nom1 = Ajtai | prénom1 = Miklós | lien auteur1 = Miklós Ajtai
|auteur2 =[[János Komlós]]
 | nom3 = Szemerédi | prénom3 = Endre | lien auteur3 = Endre Szemerédi
 | journal = J. Combin. Theory Ser. A
 | pages = 354-360
 | titre = A note on Ramsey numbers
 | volume = 29
 | année = 1980
 | doi = 10.1016/0097-3165(80)90030-8
 | numéro = 3}}.</ref> :
:<math> c'_s \frac{t^{\frac{s+1}{2}}}{(\log t)^{\frac{s+1}{2} - \frac{1}{s-2}}} \leq R(s,t) \leq c_s \frac{t^{s-1}}{(\log t)^{s-2}}.</math>

== Un exemple à trois couleurs : ''R''(3,3,3) = 17 ==
[[Image:Sixteens.gif|droite|vignette|Les deux seules 3-colorations de ''K''{{ind|16}} ne contenant pas de triangles monochromatiques, la ''coloration sans torsion'' (en haut) et la ''coloration tordue'' (en bas).]]

''R''(3, 3, 3) est le seul nombre de Ramsey (non trivial) correspondant à plus de deux couleurs dont on connait la valeur exacte : ''R''(3, 3, 3) = 17.

;Démonstration
:Partons d'une 3-coloration (en rouge, vert et jaune) d'un graphe complet ''K{{ind|n}}'' ne contenant pas de triangle monochromatique, et fixons un sommet ''v'' ; le ''[[voisinage (théorie des graphes)|voisinage]] vert'' de ''v'', noté ''V'', est le sous-graphe de ''K{{ind|n}}'' dont les sommets sont les ''u'' tels que l'arête {''u,v}'' soit verte. ''V'' ne peut contenir d'arête verte (sinon un triangle vert serait formé de cette arête et des deux arêtes la reliant à ''v''). ''V'' est donc 2-coloré en rouge et jaune, et ne contient pas de triangle monochromatique ; comme ''R''(3, 3) = 6, ''V'' a au plus 5 sommets. Raisonnant de même sur les voisinages rouges et jaunes de ''v'', on voit qu'ils contiennent également 5 sommets au plus, et donc en définitive que le graphe complet peut avoir au plus 1 + 5 + 5 + 5 = 16 sommets ; ainsi, ''R''(3, 3, 3) ≤ 17.
:Pour montrer que ''R''(3, 3, 3) ≥ 17, il suffit d'exhiber une 3-coloration de ''K''{{ind|16}} ne contenant pas de triangles monochromatiques. À [[isomorphisme de graphes|isomorphisme]] près, il en existe exactement 2, représentés à droite (dans ces tracés, les sommets numérotés ''v''{{ind|11}} à ''v''{{ind|15}} ont été dupliqués à droite et à gauche pour faciliter la lisibilité).
:En définitive, ''R''(3, 3, 3) = 17.

[[Image:Clebsch graph.svg|vignette|droite|Le [[graphe de Clebsch]].]] Dans les deux 3-colorations précédentes, les trois sous-graphes formés des arêtes d'une seule couleur sont isomorphes au [[graphe de Clebsch]].

== Généralisations du théorème ==
[[Paul Erdős]] et [[Leo Moser]] définissent des nombres analogues (encore appelés ''nombres de Ramsey'') pour des [[graphe orienté|graphes orientés]]<ref>{{article|langue=en
 | nom1 = Erdős | prénom1 = P.
 | nom2 = Moser | prénom2 = L.
 | journal = Magyar Tud. Akad. Mat. Kutató Int. Közl.
 | mr = 0168494
 | pages = 125-132
 | titre = On the representation of directed graphs as unions of orderings
 | url = http://www.renyi.hu/~p_erdos/1964-22.pdf
 | volume = 9
 | année = 1964}}.</ref>. Ils démontrent pour tout ''n'' l'existence d'un entier ''Q'' tel que tout graphe complet orienté (encore appelé un [[tournoi (graphe)|tournoi]]) ayant ''Q'' sommets contienne un sous-graphe [[graphe orienté acyclique|acyclique]] à ''n'' sommets, et notent ''R''(''n'') le plus petit de ces entiers (l'analogie avec ''R''(''n'', ''n'' ; 2) consiste à considérer chaque direction comme une couleur ; un graphe acyclique est alors un graphe dans lequel les arêtes ont toutes « la même direction », donc un graphe monochromatique). On obtient ''R''(1) = 1, ''R''(2) = 2, ''R''(3) = 4, ''R''(4) = 8, ''R''(5) = 14, ''R''(6) = 28, 32 ≤ ''R''(7) ≤ 55 ; la détermination exacte de ''R''(8) est un autre problème que, [[#Nombres de Ramsey|comme Erdős pour ''R''(5, 5)]], on n'aimerait pas voir posé par de puissants extra-terrestres.

Le théorème de Ramsey s'étend également aux [[hypergraphe]]s. Un ''m''-hypergraphe est une généralisation des graphes consistant à appeler « arêtes » des ensembles de ''m'' sommets – les graphes ordinaires sont donc des 2-hypergraphes. Le résultat de Ramsey est que pour tout ''m'' et ''c'', et toute suite ''n''{{ind|1}}, … , ''n{{ind|c}}'', il existe un entier ''R''(''n''{{ind|1}}, … , ''n{{ind|c}}'' ; ''c'', ''m'') tel que pour toute ''c''-coloration d'un ''m''-hypergraphe complet d'ordre ''R''(''n''{{ind|1}}, … , ''n{{ind|c}}'' ; ''c'', ''m''), il existe un ''i'' et un sous-hypergraphe complet d'ordre ''n{{ind|i}}'' monochromatique de couleur ''i''. La démonstration se fait par récurrence sur ''m'', en partant du cas ''m'' = 2 des graphes ordinaires.

Enfin, de nombreuses variantes du théorème sont obtenues en exigeant des conditions supplémentaires sur les sous-graphes monochromatiques dont il garantit l'existence, ou en remplaçant les graphes complets par d'autres structures ; cet ensemble de résultats constitue la [[théorie de Ramsey]]. Ainsi, le [[théorème de van der Waerden]] (dont le [[théorème de Szemerédi]] est une généralisation) est obtenu en remplaçant « graphe complet » par « [[progression arithmétique]] » ; un autre exemple célèbre est, en identifiant les sommets du graphe ''K''{{ind|2{{exp|''n''}}}} à ceux d'un [[hypercube]], la démonstration que, pour toute 2-coloration, il existe un sous-graphe ''K''{{ind|4}} monochromatique dont les quatre sommets sont coplanaires, si ''n'' est supérieur au [[nombre de Graham]]<ref>Pour plus de détails, voir {{Lien web|langue=en|url=https://plus.google.com/117663015413546257905/posts/KJTgfjkTZCQ|auteur=[[John Baez]]|mois=1|année=2013|titre=A while back I told you about Graham's number...}}.</ref>.

== Le théorème de Ramsey infini ==
{{article connexe|Cardinal de Ramsey}}

Un résultat analogue, encore appelé '''théorème de Ramsey''' (ou '''théorème de Ramsey infini''' lorsque le contexte n'est pas clair), s'applique aux graphes infinis. Les représentations graphiques étant moins parlantes dans ce cas, les résultats de ce type sont généralement formulés dans le langage de la [[théorie des ensembles]]. On note ici ''E''{{exp|(''n'')}} (pour tout ensemble ''E'' et tout [[Entier naturel|entier]] ''n'') l'ensemble des parties de ''E'' de taille ''n'' et, en appelant « coloration finie » d'un ensemble une [[partition (mathématiques)|partition]] finie de cet ensemble, une partie est dite « monochrome » si elle est incluse dans l'une des classes de la partition (appelées « couleurs »).

{{Théorème|Théorème de Ramsey infini|Soit ''X'' un [[ensemble infini]] [[Ensemble dénombrable|dénombrable]]. Pour toute coloration finie de ''X''{{exp|(''n'')}}, il existe un [[sous-ensemble]] infini ''M'' de ''X'' tel que ''M''{{exp|(''n'')}} soit monochrome.}}

;Démonstration
:Soit ''c'' le nombre de couleurs. On raisonne par récurrence sur ''n''. Si ''n''&nbsp;=&nbsp;1, l'énoncé est vrai car dans toute partition finie d'un ensemble infini, l'un des sous-ensembles est infini. Supposons le théorème vrai pour ''n'' ≤ ''r'', et montrons-le pour ''n'' = ''r''&nbsp;+&nbsp;1. Étant donné une ''c''-coloration ''P'' de ''X''{{exp|(''r''+1)}}, soit ''a''{{ind|0}} un élément de ''X'' et ''Y'' = ''X''\{''a''{{ind|0}}<nowiki/>}. ''P'' induit une ''c''-coloration ''P{{'}}'' de ''Y''{{exp|(''r'')}} définie par : la ''P{{'}}''-couleur d'une partie ''s'' de ''Y'' est la ''P''-couleur de ''s''∪{''a''{{ind|0}}<nowiki/>}. D'après l'hypothèse de récurrence, il existe un sous-ensemble infini ''Y''{{ind|1}} de ''Y'' tel que ''Y''{{ind|1}}{{exp|(''r'')}} soit monochrome. Il y a donc un élément ''a''{{ind|0}} et un ensemble infini ''Y''{{ind|1}} tels que tous les sous-ensembles à ''r''&nbsp;+&nbsp;1 éléments de ''X'' formés de ''a''{{ind|0}} et de ''r'' éléments de ''Y''{{ind|1}} ont la même couleur. Le même argument montre qu'il y a un élément ''a''{{ind|1}} de ''Y''{{ind|1}} et un sous-ensemble infini ''Y''{{ind|2}} de ''Y''{{ind|1}} avec la même propriété, et donc, par récurrence, on obtient une suite infinie (''a''{{ind|0}}, ''a''{{ind|1}}, ''a''{{ind|2}}, …) telle que la couleur de n'importe quel sous-ensemble à ''r''&nbsp;+&nbsp;1 éléments de la forme (''a''{{ind|''i''(1)}}, ''a''{{ind|''i''(2)}}, … , ''a''{{ind|''i''(''r''&nbsp;+&nbsp;1)}}) avec ''i''(1) < ''i''(2) < … < ''i''(''r''&nbsp;+&nbsp;1) dépend seulement de ''i''(1). Il y a de plus un nombre infini de valeurs ''i''(''n'') pour lesquelles cette couleur sera la même. L'ensemble de ces ''a''{{ind|''i''(''n'')}} est par construction un ensemble ayant la propriété cherchée.

Ce théorème est à l'origine de la notion de [[cardinal de Ramsey]] (qu'on démontre être nécessairement un [[grand cardinal]]). Soit κ un [[nombre cardinal]] infini, [κ]{{exp|<ω}} l'ensemble des sous-ensembles finis de κ ; on dit que κ est un '''cardinal de Ramsey''' (ou simplement que κ est Ramsey) si, pour toute application ''f'' de [κ]{{exp|<ω}} dans l'ensemble {0, 1}, il existe un sous-ensemble ''A'' de κ ayant le même cardinal que κ qui est ''homogène'' pour ''f'', c'est-à-dire que pour tout ''n'', ''f'' est constante sur les sous-ensembles de ''A'' de cardinal ''n''. Autrement dit, il s'agit d'un cardinal (non dénombrable) pour lequel le théorème de Ramsey (reformulé convenablement et un peu renforcé) est encore vrai.

== Le cas infini implique le cas fini ==
On peut déduire le théorème fini de la version infinie en [[raisonnement par l'absurde|raisonnant par l'absurde]], ou plutôt par [[contraposition]]. Supposons que le théorème fini soit faux. Il existe des entiers ''c'', ''n'', ''T'' tels que pour tout entier ''k'', il existe une ''c''-coloration de {1, 2, … , ''k''}{{exp|(''n'')}} sans ensemble monochromatique de cardinal ''T''. Soit ''C{{ind|k}}'' l'ensemble de ces ''c''-colorations.

Pour tout ''k'', la restriction d'une coloration de ''C''{{ind|''k''+1}} à {1, 2, … , ''k''}{{exp|(''n'')}} obtenue en ignorant les ensembles contenant ''k'' + 1 est une coloration de ''C{{ind|k}}''. Définissant ''C''{{1}}''{{ind|k}}'' comme l'ensemble des colorations de ''C{{ind|k}}'' qui sont des restrictions de colorations dans ''C''{{ind|''k''+1}}, on voit que ''C''{{1}}''{{ind|k}}'' n'est pas vide, puisque ''C''{{ind|''k''+1}} ne l'est pas.

De même, la restriction d'une coloration dans ''C''{{1}}{{ind|''k''+1}} est dans ''C''{{1}}''{{ind|k}}'', ce qui permet de définir ''C''{{2}}''{{ind|k}}'' comme l'ensemble non vide de ces restrictions ; par récurrence, on peut donc définir ''C{{exp|m}}{{ind|k}}'' pour tous les entiers ''m'' et ''k''.

On a donc pour tout ''k'' la suite décroissante <math>C_k\supseteq C^1_k\supseteq C^2_k\supseteq \dots</math>, et tous les ensembles de cette suite sont non vides. De plus, ''C{{ind|k}}'' est fini (de cardinal inférieur ou égal à <math>c^{\frac{k!}{n!(k-n)!}}</math>). Il en résulte que la suite est stationnaire, et que <math>D_k=C_k\cap C^1_k\cap C^2_k\cap \dots</math> est non vide. Ainsi, toute coloration de ''D{{ind|k}}'' est la restriction d'une coloration dans ''D''{{1}}{{ind|''k''+1}}. Remontant alors en prolongeant une coloration de ''D{{ind|k}}'' à ''D''{{ind|''k''+1}}, puis à ''D''{{ind|''k''+2}}, et ainsi de suite, on construit une coloration de <math>\N^{(n)}</math> sans aucun ensemble monochromatique de cardinal ''T''. Ceci est la contradiction cherchée avec le théorème de Ramsey infini ; par [[contraposition]], ce dernier entraîne le cas fini.

D'un point de vue topologique, ce raisonnement peut s'interpréter comme un argument de [[théorème de compacité|compacité]]<ref>{{Lien web|url=https://perso.ens-lyon.fr/thomas.budzinski/enseignement/Ramsey.pdf|titre=Théorie de Ramsey|auteur=Thomas Budsinski|année=2024|site=ENS Lyon|page= 6|consulté le=10 août 2024}}.</ref>.

== Historique et applications ==

[[Frank Ramsey]] a publié ce théorème dans l'article ''On a problem of formal logic'' {{harv|Ramsey|1930}}. L'article en question est un article de [[logique mathématique]] et le théorème était au départ une étape du raisonnement. Le résultat a été popularisé par [[Paul Erdős]], notamment dans l'article ''A combinatorial problem in geometry'' {{harv|Erdős|Szekeres|1935}}<ref>Pour cette partie historique, voir le sous-chapitre 1.7 de {{Harvsp|Graham|Rothschild|Spencer|1990|p=19}}.</ref>.

Le théorème de Ramsey est utilisé entre autres en [[informatique théorique]], par exemple pour montrer des bornes sur l'efficacité des [[structure de données|structures de données]]<ref>Voir par exemple :
{{article
 | nom1 = Yao | prénom1 = Andrew Chi-Chih |lien auteur1 = Andrew Yao
 | titre     = Should Tables Be Sorted?
 | périodique  = Journal of the ACM | lien périodique = Journal of the ACM
 | volume    = 28
 | numéro    = 3
 | année     = 1981
 | passage     = 615-628
}}.</ref>.

== Notes et références ==
{{Traduction/Référence|en|Ramsey's theorem|585236006}}
{{Références}}

== Bibliographie ==
* {{article|langue=en
 |auteur=Paul Erdős|auteur2=George Szekeres
 | journal = [[Liste des journaux scientifiques en mathématiques#C|Compositio Mathematica]]
 | pages = 463-470
 | titre = A combinatorial problem in geometry
 | volume = 2
 | année = 1935
 | doi = 10.1007/978-0-8176-4842-8_3
|url=http://www.numdam.org/numdam-bin/item?id=CM_1935__2__463_0}}.
* {{Ouvrage|langue=en|prénom1=Ronald L.|nom1=Graham|lien auteur1=Ronald Graham|prénom2=Bruce Lee|nom2=Rothschild|prénom3=Joel H.|nom3=Spencer|titre=Ramsey Theory|éditeur=[[John Wiley & Sons|Wiley-Interscience]]|année=1990|numéro d'édition=2|année première édition=1980|isbn=}}
* {{article|langue=en
 | titre = On a problem of formal logic
 | nom = Ramsey | prénom = F. P.
 | url =http://www.cs.umd.edu/~gasarch/TOPICS/ramsey/ramseyorig.pdf
 | périodique = Proc. [[London Mathematical Society|London Math. Soc.]]
 | passage = 264-286
 | volume = 30
 | année = 1930}}.
* {{chapitre|auteur1=[[Martin Aigner]]|auteur2=[[Günter M. Ziegler]]|titre ouvrage=[[Raisonnements divins]]|année=2002|numéro chapitre=32|titre= Les probabilités facilitent (parfois) le dénombrement|url=https://books.google.fr/books?id=0p4z8ptz6GkC&pg=PA229|éditeur=Springer|page=229-234|ISBN=9782287597237}}`.
* {{ouvrage|auteur=[[Claude Berge]]|titre=Graphes et Hypergraphes|éditeur=[[Éditions Dunod|Dunod]]|lieu=Paris|date=1973|isbn=978-2-04-009755-4}}.

== Voir aussi ==
{{Autres projets
 | commons     = <!-- Commons -->
 | wikispecies = <!-- Wikispecies -->
 | wiktionary  = <!-- Wiktionary -->
 | wikiversity = <!-- Wikiversity -->
 | wikibooks   = en:Combinatorics/Bounds_for_Ramsey_numbers
 | wikibooks titre ={{en}} {{lang|en|Bounds for Ramsey numbers}}
 | wikisource  = <!-- Wikisource -->
 | wikiquote   = <!-- Wikiquote -->
 | wikinews    = <!-- Wikinews -->
 | meta        = <!-- Meta-Wiki -->
 | outreach    = <!-- Outreach -->
 | wikidata    = <!-- Wikidata -->
 | wikivoyage  = <!-- Wikivoyage -->
}}
=== Articles connexes ===
* [[Coloration de graphe]]
* [[Théorème des amis et des étrangers]]
* [[Graphe d'amitié]]
* [[Théorème de Paris-Harrington]]

=== Liens externes ===
* {{EncycloMath|titre=Ramsey theorem|id=p/r077240}}
<!--* {{lien brisé|consulté le=2013-12-14|url=http://www.ramseyathome.com/ramsey/|titre=Ramsey@Home}} est un projet de [[calcul distribué]] destiné à déterminer de nouvelles bornes pour diverses sortes de nombres de Ramsey.
-->
* {{MathWorld|nom_url=RamseyNumber|titre=Ramsey Number}} (bornes pour tous les nombres de Ramsey jusqu'à R(19,19))
* {{en}} [http://ginger.indstate.edu/ge/RAMSEY/index.html Ramsey Numbers – Geoffrey Exoo] (Le contre-exemple montrant que R(5,5) > 42)
* {{article|langue=en| prénom1=Norman | nom1=Do | titre= Party problems and Ramsey theory
| journal= Austr. Math. Soc. Gazette | année=2006 | volume=33 | numéro=5 | pages=306-312
| url=http://www.austms.org.au/Publ/Gazette/2006/Nov06/Nov06.pdf#page=48
}}
* {{article|langue=en
 | nom1 = Bian | prénom1 = Zhengbing
 | nom2 = Chudak | prénom2 = Fabian
 | nom3 = Macready | prénom3 = William G.
 | nom4 = Clark | prénom4 = Lane
 | nom5 = Gaitan | prénom5 = Frank
 | titre = Experimental determination of Ramsey numbers
 | journal = Physical Review Letters
 | volume = 111
 | pages = 130505-1 - 130505-6
 | année = 2013
 | doi = 10.1103/PhysRevLett.111.130505|arxiv=1201.1842}}

{{Portail|mathématiques|informatique théorique}}

[[Catégorie:Théorème de la théorie des graphes|Ramsey]]
[[Catégorie:Théorème de combinatoire]]
[[Catégorie:Théorie des ensembles]]