Kombinatorik auf endlichen Strukturen

Waldmann, Johannes

Teilnehmerkreis:

Schwerpunktvorlesung in Theoretischer Informatik, für Studenten der Informatik oder Mathematik.

Übersicht:

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. Oft gilt:

Für jede Zahl n existiert eine Zahl m, so daß jedes Objekt X mit size(X) >= m wenigstens ein Unter-Objekt Y mit P(Y) und size (Y) >= n enthält.

Ein tatsächliches Y mit P(Y) ist im Allgemeinen schwer in X zu lokalisieren. Oft finden wir für m nur Schranken, die meist nicht scharf sind.

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

• Grundlagen der Ramsey-Theorie (auf Graphen)
• Anwendungen und Erweiterungen der Ramsey-Theorie (in Arithmetik und Geometrie)

• Wohl-Quasi-Ordnungen (WQO) auf Bäumen (Satz von Kruskal)
• Anwendungen von WQOs in der Termersetzung (Pfadordnungen)
• WQOs auf Graphen (Arbeiten von Robertson/Seymour)

• Vermeidbare Muster in unendlichen Wörtern (Thue-Wörter)
• Endlichkeits- und Regularitätsbedingungen für Monoide (Burnside-Probleme)

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 (gelöste und ungelöste) sowie sinnreiche kombinatorische Beweistechniken.

Literatur:

• Aigner, Ziegler: Proofs from The Book, Springer, 1998, (Kapitel 20 und 21)
• Baader, Nipkow: Term Rewriting and All That, Cambridge University Press, 1998 (Kapitel 5)
• Bollobas: Graph Theory, Springer, 1979, (Kapitel 6)
• Diestel: Graphentheorie, Springer, 1996, (Kapitel 6, 7 und 10)
• Graham, Rothshild, Spencer: Ramsey Theory, Verlag John Wiley & Sons, 1990
• Lothaire: Algebraic Combinatorics on Words, http://www-igm.univ-mlv.fr/~berstel/Lothaire/
• Luca, Varricchio: Finiteness and Regularity in Semigroups and Formal Languages, Springer, 1998
• Rozenberg, Salomaa (Hrsg.): Handbook of Formal Languages, Springer, 1997 (Band 1, Kapitel 6 und 11)

Erwartete Vorkenntnisse:

Grundlagen in (diskreter) Mathematik und formalen Sprachen

Scheinvergabe:

Für das Lösen einiger Übungsaufgaben.

Sonstiges:

Weiter Informationen zur Vorlesung: http://www.informatik.uni-leipzig.de/~joe/edu/ss00/kombinat/

Beschreibung editieren

Diese Seite wird direkt aus einer objektorientierten SGML-Datenbank extrahiert. Dabei wird das von Sergej Melnik in Java geschriebenes SGML-Management-Tool eingesetzt, das an der Abteilung Datenbanken entwickelt worden ist.