Ramseys Theorem und Ramsey-Zahlen

Ramseys Theorem garantiert, dass jeder ausreichend große zweifarbige vollständige Graph eine monochromatische Clique enthält, und Ramsey-Zahlen quantifizieren, wie groß „ausreichend“ ist.

Definition

Die Ramsey-Zahl R(s,t) ist die kleinste ganze Zahl n, sodass jede Rot-Blau-Färbung der Kanten des vollständigen Graphen mit n Eckpunkten eine rote Clique mit s Eckpunkten oder eine blaue Clique mit t Eckpunkten enthält.

Scope

Dieses Thema behandelt die Graphenform von Ramseys Theorem, die Definition der Ramsey-Zahlen R(s,t), die klassischen kleinen Fälle wie R(3,3)=6, die obere Schranke von Erdos-Szekeres und die probabilistische untere Schranke von Erdos sowie die Erweiterung auf Mehrfarben- und Hypergraphen-Ramsey-Zahlen. Es bildet den quantitativen Kern der Ramsey-Theorie.

Core questions

• Wie groß muss ein vollständiger Graph sein, um eine monochromatische Clique gegebener Größe zu erzwingen?
• Welche exakten Werte und Schranken für Ramsey-Zahlen sind bekannt?
• Wie liefern probabilistische Argumente untere Schranken für Ramsey-Zahlen?
• Wie verallgemeinert sich das Theorem auf mehrere Farben und auf Hypergraphen?

Key concepts

• Ramseys Theorem für Graphen
• Ramsey-Zahl R(s,t)
• Monochromatische Cliquen
• Erdos-Szekeres-Schranke
• Probabilistische untere Schranken
• Mehrfarben- und Hypergraphen-Ramsey-Zahlen

Key theories

Erdos-Szekeres obere Schranke

Ramsey-Zahlen sind endlich und durch R(s,t) begrenzt, das höchstens dem Binomialkoeffizienten von s+t-2 über s-1 entspricht, eine rekursionsbasierte Schranke, die Ramseys Theorem mit expliziten Schätzungen beweist.

Erdos' probabilistische untere Schranke

Durch Zählen der erwarteten monochromatischen Cliquen in einer Zufallsfärbung zeigte Erdos 1947, dass die diagonale Ramsey-Zahl R(s,s) mindestens exponentiell wächst, eine grundlegende Anwendung der probabilistischen Methode.

Clinical relevance

Die probabilistische Methode, die durch die unteren Schranken der Ramsey-Zahlen eingeführt wurde, entwickelte sich zu einem zentralen Werkzeug in der Kombinatorik und der theoretischen Informatik, und Ramsey-ähnliche Garantien untermauern die unteren Schranken in der Kommunikation und bei Datenstrukturen.

History

Erdos und Szekeres entdeckten Ramseys Theorem 1935 wieder und quantifizierten es, während sie konvexe Polygone untersuchten; Erdos' untere Schranke durch Zufallsfärbung von 1947 begründete die probabilistische Methode.

Key figures

• Frank Ramsey
• Paul Erdos
• George Szekeres

Seminal works

• graham1990

Frequently asked questions

Warum ist R(3,3) gleich sechs?

Unter sechs beliebigen Personen sind entweder drei gegenseitig bekannt oder drei gegenseitig unbekannt, während fünf Personen so angeordnet werden können, dass beides vermieden wird; sechs ist also die genaue Schwelle.

Sind exakte Ramsey-Zahlen bekannt?

Nur eine Handvoll sind exakt bekannt; selbst R(5,5) ist noch offen, wobei das aktuelle Wissen es nur auf einen Bereich eingrenzt, da der Suchraum zu schnell wächst, um ihn rechnerisch zu bestimmen.