Ramseytheorie

Die Ramseytheorie (nach Frank Plumpton Ramsey) ist ein Zweig der Kombinatorik innerhalb der Diskreten Mathematik. Sie behandelt die Frage, wie viele Elemente aus einer mit einer gewissen Struktur versehenen Menge ausgewählt werden müssen, damit diese Struktur in der Teilmenge wiedergefunden werden kann und eine bestimmte Eigenschaft erfüllt ist. Berühmte Sätze der Ramseytheorie haben dabei alle diese Eigenschaft gemeinsam.

Beispiele

Als einfaches Beispiel gilt das Schubfachprinzip. Dieses besagt, dass beim Verteilen von ${\displaystyle k+1}$ Objekten auf ${\displaystyle k}$ Schubfächer wenigstens eines der Schubfächer mindestens zwei Objekte enthält.

In einem weiteren Beispiel treffen 6 Personen aufeinander. Je zwei sind entweder miteinander befreundet oder nicht befreundet. Dann gibt es (stets!) eine Dreiergruppe, in der alle miteinander befreundet sind, oder eine Dreiergruppe, in der es überhaupt keine Freundschaften gibt.

Formulierung der Lösung als Graphenproblem

Abb. 1

Sei ${\displaystyle {\mathcal {G}}=(V,E)}$ ein Graph mit ${\displaystyle n=6}$ Knoten (für die Personen) und roten Kanten für Freunde bzw. grauen Kanten für Nicht-Freunde. Wir betrachten eine Person ${\displaystyle A}$. Diese hat stets mindestens drei Freunde oder Nicht-Freunde (Abb. 1). Würden nun zwei der drei gleichartigen Endknoten (im Bild rot verbunden) mit einer weiteren roten Kante verknüpft, so haben wir bereits eine Gruppe von Dreien, die alle miteinander befreundet (oder auch nicht) sind. Würden hingegen alle drei Endknoten mit drei grauen Kanten verbunden, so hätten wir auch wieder eine Gruppe von Dreien, die alle unbefreundet (befreundet) sind.

In diesem Beispiel werden Paare aus einer sechselementigen Menge in zwei disjunkte Klassen eingeordnet (Freunde und nicht Freunde). Egal, wie die Zuordnung aussieht, existiert eine homogene Dreiergruppe.

Ein anderes Beispiel ist Sim.

Berühmte Sätze der Ramseytheorie

• Das Schubfachprinzip macht Aussagen über die Anzahl der in Schubfächern befindlichen Objekte und gilt als Ausgangspunkt der Ramseytheorie.
• Der klassische Satz von Ramsey untersucht, wie groß ein Graph sein muss, damit für eine Färbung stets eine Clique in entsprechender Farbe und Größe existiert. Unendliche Versionen dieses Satzes spielen in der abstrakten Mengenlehre eine Rolle, siehe Satz von Ramsey (Mengenlehre).
• Der Satz von Van der Waerden untersucht die minimale Größe einer Menge ${\displaystyle \{1,\cdots ,n\}}$, so dass unter einer Färbung dieser Menge stets eine einfarbige arithmetische Folge bestimmter Länge zu finden ist.
• Das Färben von Ebenen, genauer gesagt, das Färben der Ebene ${\displaystyle x+y=z}$ ist unter dem Satz von Schur bekannt geworden.

Literatur

• Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer: Ramsey Theory. 2. Auflage. Wiley, New York, NY, 1990, ISBN 0-471-50046-1
• Bruce M. Landman, Aaron Robertson: Ramsey Theory on the Integers. 1. Auflage. AMS, Rhode Island, 2004, ISBN 0-8218-3199-2
• Richard Rado: Studien zur Kombinatorik. Dissertation, Berlin 1933