Ramsey-Theorie

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 wieder gefunden werden kann und eine bestimmte Eigenschaft erfüllt ist. Berühmte Sätze der Ramseytheorie haben dabei alle diese Eigenschaft gemeinsam.

Beispiele

Abb. 1

Als einfaches Beispiel gilt das Schubfachprinzip. Dieses besagt, dass beim Verteilen von k + 1 Objekten auf k Schubfächer, wenigstens eines der Schubfächer 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 Gruppe von dreien, die jeweils miteinander befreundet bzw. nicht-befreundet sind. Formulierung der Lösung als Graphenproblem. Sei $\mathcal{G}=(V,E)$ ein Graph mit n = 6 Knoten (für die Personen) und roten Kanten für Freunde bzw. grauen Kanten für nicht Freunde. Wir betrachten eine Person 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.

Berühmte Sätze der Ramseytheorie

• Das Schubfachprinzip macht Aussagen über die Anzahl der in Schubfächern befindlichen Objekte und gilt als bekanntestes Resultat 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.
• Der Satz von Van der Waerden untersucht die minimale Größe einer Menge $\{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 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