Ramsey-Theorie
aus Wikipedia, der freien Enzyklopädie
Die Ramsey-Theorie, benannt nach Frank Plumpton Ramsey, ist ein Zweig der Kombinatorik. Sie behandelt die Frage, wie viele Elemente aus einer mit einer gewissen Struktur versehenen Menge ausgewählt werden müssen, damit eine bestimmte Eigenschaft erfüllt ist. Oder man hat eine mathematische Struktur, die in zwei Teile zerlegt wird. Wie "groß" muss die Struktur sein, damit wenigstens eines der Teile eine vorgegebene Eigenschaft besitzt?
Als einfaches Beispiel gilt das Schubfachprinzip: Angenommen, man hat n Schubfächer. Wie viele Kugeln m muss man nacheinander auf die Schubfächer verteilen, damit in wenigstens einer Schublade mindestens 2 Kugeln liegen? Offensichtlich muss für m mindestens n+1 gewählt werden.
[Bearbeiten] Beispiele
- Graph-Färbungen (Satz von Ramsey): Gegeben ist der vollständige ungerichtete Graph mit n Knoten; es ist also jedes Knotenpaar durch eine Kante verbunden. Nun werden die Kanten mit k Farben gefärbt. Wie groß muss n sein, damit ein Dreieck des Graphen, also die drei Knoten verbindenden Kanten, gleich gefärbt ist (monochrom)? Der Satz von Ramsey formuliert das Problem mit monochrom gefärbten Subgraphen beliebiger Größe.
- Satz von Van der Waerden: Für jedes natürliche l und k existiert eine natürliche Zahl N, so dass, wenn man die Zahlen 1,2,...N mit k Farben färbt, eine arithmetische Progression der Länge l existiert, deren Elemente gleich gefärbt sind.
