Vortragsankündigung, Bereichsseminar Theoretische Informatik

Dr. J. Waldmann, Institut für Informatik, Universität Leipzig

Struktur und Endlichkeit


Termine: dienstags, 15 Uhr, Seminarraum HG 3-68
Wir beobachten bei verschiedensten Gelegenheiten, daß es keine "beliebig große" Unordnung gibt:

Sei P eine Eigenschaft von Objekten, und size(X) die Größe des Objekts X. Dann gilt: Für jede Zahl n existiert ein m, so daß jedes Objekt X mit size(X) >= m wenigstens ein Unter-Objekt Y mit P(Y) und size (Y) >= n enthält.

Das hängt natürlich von P und von der Unter-Objekt-Relation ab.

Ein tatsächliches Y mit P(Y) ist im Allgemeinen schwer in X zu lokalisieren. Oft finden wir für m nur Schranken, die aber nicht scharf sind. Manchmal reicht uns schon die Aussage für n und m gleich abzählbar unendlich.

Ich möchte das an verschiedenen Beispielen erläutern.


Ein klassischer Fall ist die Ramsey-Theorie auf Graphen. Dabei sind die Objekte kantengefärbte Graphen, und P ist Einfarbigkeit.

Von dort gibt es Verbindungen zur Arithmetik: wir betrachten bestimmte Multigraphen auf Zahlen, die Summen oder arithmetische Folgen kodieren (Satz von van der Waerden).

Wechseln wir von Graphen zu Bäumen (Termen), nehmen wir als Unter-Objekte die homöomorph eingebetteten Terme. (Genauer: die Objekte sind Mengen von Bäumen, und P kodiert die Einbettung.) Das führt zu Higmans Lemma und Kruskals Satz über Wohlquasiordnungen. Den wenden wir an, um mit Simplifikationsordnungen Terminationsbeweise für Ersetzungssysteme zu führen.

Arbeiten von Robertson und Seymor übertragen das wieder auf Graphen.

Wählen wir eine andere Unter-Objekt-Beziehung (Faktor statt Einbettung), dann sind bestimmte Muster doch vermeidbar. Solche Untersuchungen bilden tatsächlich einen der Anfänge der Theorie die formalen Sprachen (Thue und Morse, um 1900).

Von dort gibt es wiederum Verbindungen zur Algebra: wir fragen, wann eine endlich erzeugte (Halb-)Gruppe, die nicht mehr frei ist, sondern zusätzlichen Bedingungen genügt, endlich wird. Das ist das Burnside-Problem.


Wir erhalten so, aus einem speziellen Blickwinkel, Einsichten in einige wesentliche Entwicklungen der diskreten Mathematik und Theoretischen Informatik in den letzten 100 Jahren. Wir sehen dabei viele harte Probleme und sinnreiche kombinatorische Beweistechniken. Ich möchte zu diesem Thema im Sommersemester 2000 eine Schwerpunktvorlesung halten.
http://www.informatik.uni-leipzig.de/~joe/ mailto:joe@informatik.uni-leipzig.de