Théorème de Ramsey et nombres de Ramsey
Le théorème de Ramsey garantit que tout graphe complet bicolore suffisamment grand contient une clique monochrome, et les nombres de Ramsey quantifient la taille suffisante.
Definition
Le nombre de Ramsey R(s,t) est le plus petit entier n tel que toute coloration en rouge et bleu des arêtes du graphe complet à n sommets contient une clique rouge de s sommets ou une clique bleue de t sommets.
Scope
Ce sujet aborde la forme graphique du théorème de Ramsey, la définition des nombres de Ramsey R(s,t), les cas classiques de petite taille tels que R(3,3)=6, la borne supérieure d'Erdos-Szekeres et la borne inférieure probabiliste d'Erdos, ainsi que l'extension aux nombres de Ramsey multicolores et d'hypergraphes. Il constitue le cœur quantitatif de la théorie de Ramsey.
Core questions
- Quelle doit être la taille d'un graphe complet pour forcer l'existence d'une clique monochrome de taille donnée ?
- Quelles sont les valeurs exactes et les bornes connues pour les nombres de Ramsey ?
- Comment les arguments probabilistes fournissent-ils des bornes inférieures pour les nombres de Ramsey ?
- Comment le théorème se généralise-t-il à plusieurs couleurs et aux hypergraphes ?
Key concepts
- Théorème de Ramsey pour les graphes
- Nombre de Ramsey R(s,t)
- Cliques monochromes
- Borne d'Erdos-Szekeres
- Bornes inférieures probabilistes
- Nombres de Ramsey multicolores et d'hypergraphes
Key theories
- Borne supérieure d'Erdos-Szekeres
- Les nombres de Ramsey sont finis et bornés par R(s,t) étant au plus le coefficient binomial de s+t-2 parmi s-1, une borne basée sur une récurrence qui prouve le théorème de Ramsey avec des estimations explicites.
- Borne inférieure probabiliste d'Erdos
- En comptant les cliques monochromes attendues dans une coloration aléatoire, Erdos a montré en 1947 que le nombre de Ramsey diagonal R(s,s) croît au moins exponentiellement, une application fondatrice de la méthode probabiliste.
Clinical relevance
La méthode probabiliste introduite par les bornes inférieures des nombres de Ramsey est devenue un outil central en combinatoire et en informatique théorique, et les garanties de type Ramsey sous-tendent les bornes inférieures dans les domaines de la communication et des structures de données.
History
Erdos et Szekeres ont redécouvert et quantifié le théorème de Ramsey en 1935 lors de l'étude des polygones convexes ; la borne inférieure de coloration aléatoire d'Erdos en 1947 a lancé la méthode probabiliste.
Key figures
- Frank Ramsey
- Paul Erdos
- George Szekeres
Related topics
Seminal works
- graham1990
Frequently asked questions
- Pourquoi R(3,3) est-il égal à six ?
- Parmi six personnes, trois sont mutuellement des connaissances ou trois sont mutuellement des étrangers, tandis que cinq personnes peuvent être arrangées de manière à éviter les deux situations ; six est donc le seuil exact.
- Les nombres de Ramsey exacts sont-ils connus ?
- Seule une poignée sont connus exactement ; même R(5,5) reste un problème ouvert, les connaissances actuelles ne le réduisant qu'à un intervalle, car l'espace de recherche croît trop rapidement pour être résolu par calcul.