Seminar Kombinatorik

Sommersemester 2003

RWTH Aachen

Veranstalter:	Detlef Sieling

Kombinatorische Probleme haben vielfältige Anwendungen sowohl innerhalb als auch außerhalb der Informatik. Hier einige Beispiele für solche Probleme: Wieviele Lottoreihen muss man tippen um garantiert 3 Richtige zu haben? Wieviele Kanten muss ein Graph mindestens haben, damit er garantiert ein Dreieck enthält? Wieviele Einsen kann es in einer 0-1-Matrix der Größe n x n maximal geben, wenn diese Matrix keine a x b-Submatrix enthält, die nur aus Einsen besteht? Diese Fragen haben gemeinsam, dass nach einer Minimal- oder Maximalgröße von Objekten unter gewissen Nebenbedingungen gefragt wird; daher spricht man auch von extremaler Kombinatorik. Die Lösungen für derartige kombinatorische Probleme spielen eine wesentliche Rolle in vielen Beweisen der theoretischen Informatik.

In dem Seminar sollen Methoden und Ergebnisse aus der extremalen Kombinatorik zusammen mit ihren Anwendungen in der Informatik bearbeitet werden. Grundlage hierzu ist das Buch Extremal Combinatorics von S. Jukna (Springer, 2001). Neben der Vorstellung der einzelnen Ergebnisse und Methoden ist es auch ein Ziel dieses Buchs, für die dargestellten Aussagen besonders elegante Beweise vorzustellen. In den einzelnen Kapiteln des Buchs werden weitgehend unabhängig voneinander verschiedene kombinatorische Methoden behandelt. In jedem Vortrag des Seminars sollen ein bis zwei Kapitel des Buchs aufgearbeitet und vorgestellt werden.

22.4.2003 - Detlef Sieling