Théorie de Ramsey
La théorie de Ramsey étudie comment le désordre complet est impossible : toute structure suffisamment grande doit contenir une sous-structure hautement organisée.
Definition
La branche de la combinatoire qui s'interroge sur la taille qu'une structure doit atteindre pour garantir que toute partition ou coloration de celle-ci produise une sous-structure monochrome ou autrement prescrite.
Scope
Ce domaine couvre le théorème de Ramsey pour les graphes et les hypergraphes ainsi que ses nombres de Ramsey quantitatifs, les résultats de partition pour les entiers tels que les théorèmes de Schur, de van der Waerden et de Hales-Jewett, et la théorie structurelle abstraite de Ramsey des ensembles de paramètres. Il illustre le principe combinatoire extrémal selon lequel les systèmes suffisamment grands ne peuvent éviter l'ordre.
Sub-topics
Core questions
- Quelle doit être la taille d'une structure pour forcer l'existence d'une sous-structure ordonnée inévitable ?
- Quels sont les seuils exacts ou approximatifs, les nombres de Ramsey, pour ces garanties ?
- Comment les théorèmes de partition pour les entiers garantissent-ils des motifs arithmétiques ?
- Quelles familles abstraites de structures satisfont une propriété de Ramsey ?
Key concepts
- Théorème de Ramsey
- Nombres de Ramsey
- Sous-structures monochromes
- Théorème de van der Waerden
- Théorème de Schur
- Théorème de Hales-Jewett
Clinical relevance
Les garanties de type Ramsey concernant une structure inévitable éclairent les arguments de borne inférieure en informatique théorique, l'analyse des grands réseaux et la théorie additive des nombres, tandis que l'écart entre les bornes connues alimente la méthode probabiliste.
History
Le théorème de Frank Ramsey de 1930 sur les partitions, initialement prouvé pour une question de logique, a été reconnu par Erdos et Szekeres comme le germe d'une vaste théorie de la structure inévitable qui s'est développée tout au long du XXe siècle.
Key figures
- Frank Ramsey
- Paul Erdos
- Bartel van der Waerden
Related topics
Seminal works
- graham1990
- landman2003
Frequently asked questions
- Quel est le slogan de la théorie de Ramsey ?
- Le désordre complet est impossible : tout système suffisamment grand, quelle que soit sa disposition, doit contenir une partie ordonnée significative.
- Pourquoi les nombres de Ramsey sont-ils difficiles à calculer ?
- Le nombre de colorations à vérifier croît de manière astronomique, et même de petits nombres de Ramsey tels que R(5,5) restent inconnus malgré des efforts intenses.