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