Ramsey-Theorie
Die Ramsey-Theorie untersucht, wie vollständige Unordnung unmöglich ist: Jede ausreichend große Struktur muss eine hochorganisierte Unterstruktur enthalten.
Definition
Der Zweig der Kombinatorik, der fragt, wie groß eine Struktur sein muss, um zu garantieren, dass jede Partition oder Färbung von ihr eine monochromatische oder anderweitig vorgeschriebene Unterstruktur ergibt.
Scope
Das Gebiet umfasst Ramseys Theorem für Graphen und Hypergraphen und deren quantitative Ramsey-Zahlen, Partitionsergebnisse für ganze Zahlen wie die Theoreme von Schur, van der Waerden und Hales-Jewett sowie die abstrakte strukturelle Ramsey-Theorie von Parametersätzen. Es veranschaulicht das extremal-kombinatorische Prinzip, dass ausreichend große Systeme Ordnung nicht vermeiden können.
Sub-topics
Core questions
- Wie groß muss eine Struktur sein, um eine unvermeidbare geordnete Unterstruktur zu erzwingen?
- Was sind die exakten oder ungefähren Schwellenwerte, die Ramsey-Zahlen, für diese Garantien?
- Wie garantieren Partitionstheoreme für ganze Zahlen arithmetische Muster?
- Welche abstrakten Familien von Strukturen erfüllen eine Ramsey-Eigenschaft?
Key concepts
- Ramseys Theorem
- Ramsey-Zahlen
- Monochromatische Unterstrukturen
- Satz von Van der Waerden
- Satz von Schur
- Satz von Hales-Jewett
Clinical relevance
Ramsey-artige Garantien für unvermeidbare Strukturen fließen in Argumente für untere Schranken in der theoretischen Informatik, der Analyse großer Netzwerke und der additiven Zahlentheorie ein, während die Lücke zwischen bekannten Schranken die probabilistische Methode vorantreibt.
History
Frank Ramseys Theorem von 1930 über Partitionen, ursprünglich für eine Frage in der Logik bewiesen, wurde von Erdos und Szekeres als Keim einer breiten Theorie der unvermeidbaren Struktur erkannt, die sich im 20. Jahrhundert entwickelte.
Key figures
- Frank Ramsey
- Paul Erdos
- Bartel van der Waerden
Related topics
Seminal works
- graham1990
- landman2003
Frequently asked questions
- Was ist der Slogan der Ramsey-Theorie?
- Vollständige Unordnung ist unmöglich: Jedes ausreichend große System, wie auch immer es angeordnet ist, muss einen beträchtlichen geordneten Teil enthalten.
- Warum sind Ramsey-Zahlen schwer zu berechnen?
- Die Anzahl der zu prüfenden Färbungen wächst astronomisch, und selbst kleine Ramsey-Zahlen wie R(5,5) bleiben trotz intensiver Bemühungen unbekannt.