Vortragsankündigung, Bereichsseminar Theoretische Informatik,
Dienstag, den 30. Mai 00, 15:15 - 16:45, Raum 3-68, Hauptgebäude
Dr. J. Waldmann, Institut für Informatik, Universität Leipzig
Wozu bewies F. P. Ramsey den Satz von F. P. Ramsey?
Die Ramsey-Theorie untersucht Aussagen der Form:
jede beliebige Färbung einer genügend großen Struktur
enthält große einfarbige Teilstrukturen.
In dieser Allgemeinheit sieht man die Dinge jedoch erst seit ca. 30 Jahren
(in Arbeiten von Erdös, Graham, Rothschild, Spencer).
Der Theorie zugrunde liegt ein Satz von F. P. Ramsey von ca. 1930.
Ich erläutere weniger dessen Beweis
als vielmehr seinen ursprünglichen Zweck:
er hilft bei einem Entscheidungsverfahren
für einen Teil der Prädikatenlogik erster Stufe
(nämlich All-Formeln mit Identität).
Der Vortrag ergänzt die Vorlesungen
Logik (Prof. Herre)
und Kombinatorik (Dr. Waldmann).
Kenntnisse der Ramsey-Theorie
sind zum Verständnis jedoch nicht erforderlich.
http://www.informatik.uni-leipzig.de/~joe/
mailto:joe@informatik.uni-leipzig.de