Betrachten Sie das folgende Problem: Gegeben sei ein vollständiger Graph, und es gilt, jede Kante des Graphen entweder rot oder blau zu färben. Ist es möglich, einen vollständigen Untergraphen gewisser Größe zu finden, dessen Kanten die gleiche Farbe besitzen? Ein Spezialfall dieses Problems ist gut bekannt: Auf einem Fest mit vielen Gästen gibt es stets drei Gäste, die sich entweder gegenseitig kennen oder gegenseitig nicht bekannt sind.

Frank Plumpton Ramsey (1903 - 1930), ein englischer Mathematiker, beschäftigte sich mit dem oben skizzierten Problem. Für natürliche Zahlen s und t definieren wir die Zahl R(s, t) als die kleinste Zahl so, daß jede Rot-Blau-Kantenfärbung eines beliebigen Graphen mit mindestens R(s, t) Knoten entweder einen vollständigen roten Untergraphen mit s Knoten oder einen vollständigen blauen Untergraphen mit t Knoten enthält. Die wichtige Frage hierbei ist, ob R(s, t) stets existiert. Ramsey zeigte 1928, daß dies so ist. Der Beweis ist konstruktiv und zeigt eine obere Schranke für den Wert von R(s, t). Tatsächlich sind die genauen Werte, soweit bekannt, viel kleiner. Zum Beispiel gilt R(3, 3)= 6. Dieser Satz von Ramsey bildet den Beginn einer ganzen Theorie, die sich mit der Existenz spezieller Strukturen in beliebigen Systemen beschäftigt. Eine umgangssprachliche Interpretation des Satzes von Ramsey könnte lauten: Jedes noch so chaotische System enthält stark geordnete Teilstrukturen.

Wir werden den Satz von Ramsey und verschiedene Verallgemeinerungen dessen Aussage kennenlernen, die in den Vorträgen vorgestellt werden. Die meisten Vorträge werden einen Satz und dessen Beweis vorstellen. Grundlage des Seminars ist das Buch Ramsey Theory von Graham, Rothschild, Spencer.

Das Seminar wendet sich an alle Studenten, die sich für mathematische (kombinatorische) Themen begeistern können. Spezielles Vorwissen zum Thema wird nicht vorausgesetzt, Grundlagen dagegen schon. Es kann ein Seminarschein erworben werden.

Termine

Donnerstags, 10 Uhr s.t., Raum H 406

Leitung

Daniel Meister