Ramseytheorie

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.

• 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.

• 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