Théorie de Ramsey
En mathématiques, et plus particulièrement en combinatoire, la théorie de Ramsey, nommée d'après Frank Ramsey, tente typiquement de répondre à des questions de la forme : « combien d'éléments d'une certaine structure doivent être considérés pour qu'une propriété particulière se vérifie ? »
Quelques exemples
Le premier exemple de résultat de cette forme est le principe des tiroirs, énoncé par Dirichlet en 1834.
Supposons, par exemple, que n chaussettes soient rangées dans m tiroirs. Existe-t-il une valeur de l'entier n à partir de laquelle nous puissions être sûrs qu'il existe au moins un tiroir contenant au moins deux chaussettes ? La réponse donnée par le principe des tiroirs est que c'est le cas dès que n > m. Le théorème de Ramsey généralise ce principe.
Un résultat typique dans la théorie de Ramsey commence par considérer une certaine structure mathématique, qui est alors découpée en morceaux. Quelle doit être la grandeur de la structure d'origine afin d'assurer qu'au moins un des morceaux possède une certaine propriété ?
Par exemple, considérons un graphe complet d'ordre n, c'est-à-dire ayant n sommets reliés à chaque autre sommet par une arête (un graphe complet d'ordre 3 s'appelle un triangle). Colorons maintenant chaque arête en rouge ou bleu. Quelle grandeur n doit-il avoir afin d'assurer, quelle que soit la coloration choisie, l'existence d'au moins un triangle bleu ou un triangle rouge ? On peut démontrer que la réponse est 6. Ce résultat peut se reformuler de la manière suivante : à une soirée à laquelle se rendent au moins six personnes, il y a au moins trois personnes qui se connaissent mutuellement ou au moins trois qui sont étrangères les unes aux autres.
Principaux résultats
Parmi les résultats de la théorie de Ramsey on peut distinguer les exemples suivants[1], à commencer par le théorème de Ramsey.
Théorème de Ramsey fini
Le résultat précédent est un cas particulier du théorème de Ramsey, qui indique que pour toute suite finie (n1, ..., nc) d'entiers, il existe un entier R tel que si les arêtes de KR (le graphe complet d'ordre R) sont colorées avec c couleurs, alors il y a une couleur i telle que KR contienne un sous-graphe complet d'ordre ni et monochrome de couleur i.
Le cas particulier ci-dessus correspond à c = 2 et n1 = n2 = 3.
Cinq autres théorèmes
D'autres théorèmes principaux de la théorie de Ramsey sont :
- Le théorème de van der Waerden[2] : pour tous entiers c et n, il existe un entier[3] W tel que si l'ensemble {1, 2, … , W} est coloré avec c couleurs, il contient une progression arithmétique monochrome de longueur n.
- Le théorème de Schur énonce que, pour toute partition de l'ensemble des entiers strictements positifs en un nombre fini c de parties, l'une des parties contient trois entiers x, y, z tels que x + y = z, et plus précisément, qu'il existe un nombre S(c) tel que ce résultat soit vrai pour l'ensemble {1, 2, ..., S(c)}.
- Le théorème de Rado.
- Le Théorème de Hales-Jewett : Pour tous entiers n et c donnés, il existe un nombre H tels que si les n × n × n × ... × n cellules d'un cube de dimension H sont colorées avec c couleurs, il doit exister une rangée, une colonne, etc. de longueur n dont les cellules sont toutes de la même couleur. Si par exemple, vous jouez au morpion dans un damier à k dimensions de côté n, avec k suffisamment grand c'est-à-dire avec « beaucoup de directions », la victoire étant attribuée au joueur qui aligne n pions le premier, il ne peut pas y avoir de parties nulles, même s'il y a un grand nombre de joueurs ou si n est grand.
- Le théorème de Graham-Leeb-Rothschild.
Théorème d'indécidabilité de Paris et Harrington
Le théorème de Paris et Harrington[4] montre qu'une variante du théorème de Ramsey fini est un énoncé indécidable de l'axiomatique de Peano. Historiquement, ce théorème de 1977 a donné le premier exemple d'énoncé « proprement » arithmétique (c.-à-d. non issu d'un codage « gödelien ») indécidable dans l'arithmétique de Peano, 46 ans après le théorème d'incomplétude de Gödel. Depuis on en connaît d'autres, comme le théorème de Goodstein. Ce résultat fut jugé assez important pour être inséré dans le Handbook of Mathematical Logic, alors en cours de publication[4], et se voulant une synthèse de la discipline.
Théorème de Ramsey infini
On note [A]n l'ensemble des sous-ensembles de taille n de A.
Théorème — Soit A un ensemble infini dénombrable et n un entier. Pour toute coloration de [A]n par un nombre fini de couleurs, il existe un sous ensemble infini B de A tel que [B]n soit monochrome.
Puisque tout ensemble infini contient une partie dénombrable, on peut se contenter de supposer que A est infini.
La version infinie du théorème implique la version finie.
Ce théorème a connu diverses généralisations, notamment sur les partitions récursives[5].
Il est aussi à l'origine de la notion de « cardinal de Ramsey », qui est un (très !) grand cardinal. Un cardinal infini κ (vu comme un ensemble) est dit « de Ramsey » si pour toute partition de l'ensemble des parties finies de κ en deux classes, il existe dans κ une partie A de cardinal κ et « homogène », c'est-à-dire telle que pour tout n, [A]n soit inclus dans l'une des deux classes.
Utilisations
La théorie de Ramsey est utilisée en informatique théorique, notamment en théorie du calcul distribué[6],[7].
Notes et références
- Ce choix de six théorèmes est issu de Ronald L. Graham, Bruce Lee Rothschild et Joel H. Spencer, Ramsey Theory, Wiley-Interscience, , 2e éd. (1re éd. 1980), chap. 1, p. 9.
- (en) Eric W. Weisstein, « Van der Waerden's Theorem », sur MathWorld.
- (en) Eric W. Weisstein, « Van der Waerden Number », sur MathWorld.
- (en) Jeff Paris et Leo Harrington, « A Mathematical Incompleteness in Peano Arithmetic », dans Jon Barwise, Handbook of Mathematical Logic, North-Holland (1re éd. 1977) (DOI 10.1016/S0049-237X(08)71130-3, lire en ligne), p. 1133-1142.
- (en) Carl Jockusch, « Ramsey's Theorem and Recursion Theory », Journal of Symbolic logic, vol. 37, 1972, p. 268-280. Voir en particulier le théorème 5.1 p. 275.
- Pour un exemple et une liste d'autres utilisations (paragraphe 3), voir (en) Moni Naor et Larry Stockmeyer, « What can be computed locally? », SIAM Journal on Computing, vol. 24, no 6, , p. 1259-1277 (lire en ligne [PDF]).
- (en) William Gasarch, « Application of Ramsey Theory to computer science », sur Université du Maryland.
Voir aussi
Articles connexes
Bibliographie
- (en) Wang Hao, Popular Lectures on Mathematical Logic, Dover, 1993 (ISBN 0-486-67632-3), p. 25-27 et p. 83-86.Aborde certains résultats de décidabilité et d'indécidabilité des versions finie et infinie du théorème, dans l'axiomatique de Peano et une de ses extensions.
- (en) Bruce M. Landman et Aaron Robertson, Ramsey Theory on the Integers, AMS, , 2e éd. (ISBN 978-0-82189867-3, lire en ligne)
- (en) Hans Jürgen Prömel, Ramsey Theory for Discrete Structures, Springer, (ISBN 978-3-31901315-2, lire en ligne)
- (en) Alexander Soifer (préf. Branko Grünbaum, Peter Johnson et Cecil C. Rousseau), The Mathematical Coloring Book, Springer, (ISBN 9780387746425, lire en ligne)
- (en) Alexander Soifer (ed.), Ramsey Theory: Yesterday, Today, and Tomorrow, Birkhäuser, coll. « Progress in Mathematics », (ISBN 978-0817680916, lire en ligne).
