Vorlesung Einführung in die Kombinatorik, WS 97/98

	Albert-Ludwigs-Universität Freiburg
	Institut für mathematische Logik und Grundlagen der Mathematik

Vorlesung: Einführung in die Kombinatorik

M. Grohe

Zeit und Ort: Mi 14-16 Uhr, SR404, Eckerstr. 1

Übungen: Do 14-15 Uhr, SR318, Eckerstr. 1

Kombinatorische Fragestellungen begegnen einem häufig zunächst als mathematische Knobelaufgaben. Ein bekanntes Beispiel ist das Kirkmansche Schulmädchenproblem:

Fünfzehn Schulmädchen laufen jeden Tag in fünf Dreiergruppen über den Schulhof. Ist es möglich, diese Gruppen so zu wählen, daß im Verlauf einer Woche jedes Paar von Mädchen genau einmal gemeinsam in einer Gruppe läuft?

Natürlich geht es in der Vorlesung nicht um das Lösen solcher Rätsel, aber es lassen sich viele auch theoretisch wichtige Probleme an ihnen verdeutlichen. Kombinatorik beschäftigt sich damit, mathematische Objekte gemäß gewisser Regeln anzuordnen. Man interessiert sich zunächst dafür, ob eine bestimmte Anordnung existiert. Über die reine Existenz hinaus möchte man in der Regel auch ein Verfahren finden, eine solche zu berechnen. Schließlich mag man die ambitioniertere Frage stellen, wieviele solcher Anordnungen existieren.

Kombinatorische Fragestellungen tauchen in vielen Bereichen der Mathematik auf. Ihre Rolle in der Entwicklung der theoretischen Informatik hat die Bedeutung der Kombinatorik in den letzten Jahren stark zunehmen lassen. Ziel der Vorlesung ist es vor allem, Techniken zur Lösung kombinatorischer Probleme zu vermitteln. Dabei werden unter anderem Themen wie Graphentheorie, endliche Geometrie und Kodierungstheorie zur Sprache kommen.

Vorausgesetzt werden eine gewisse mathematische Fertigkeit sowie Kenntnisse in linearer Algebra. Die Vorlesung sollte somit für Studenten ab dem dritten Semester zugänglich sein.

Lösung des Schulmädchenproblems

Kurzskript

Kapitel 1

Kapitel 2 (Version vom 29.10.1997)

Kapitel 3 (Version vom 5.11.1997)

Kapitel 4 (Version vom 19.11.1997)

Kapitel 5 (Version vom 14.1.1998)

Kapitel 6 (Version vom 28.1.1998)

Kapitel 7 (Version vom 4.2.1998)

Literatur

Übungsblätter

Blatt 1

Blatt 2 (29.10.1997)

Blatt 3 (12.11.1997)

Blatt 4 (26.11.1997)

Blatt 5 (10.12.1997)

Blatt 6 (7.1.1998)

Blatt 7 (21.1.1998)

28.1.1998 Martin Grohe