Hauptseminar im Sommersemester 2004

Extremal Combinatorics

Kontaktpersonen:

Daniel Mölle (moelle@informatik.rwth-aachen.de)
Stefan Richter (richter@informatik.rwth-aachen.de)
Peter Rossmanith (rossmani@informatik.rwth-aachen.de)

Einordnung

Theoretische Informatik

Ort und Zeit

Jeweils freitags ab 13:15 Uhr im Seminarraum 4013 (I1).

Inhalt

Extremal Combinatorics ist der Titel eines Buches von Stasys Jukna, welches als Grundlage dieses Seminars dienen wird. Es handelt sich selbstverständlich um einen Bereich der Kombinatorik, wobei sich extremal auf das Interesse an extremen, also maximalen oder minimalen, Lösungen kombinatorischer Aufgabenstellungen bezieht. Ein typisches Beispiel ist der Satz von Ramsey; er besagt, daß ein Graph ausreichender Größe entweder eine Clique oder eine unabhängige Menge einer gegebenen Größe besitzt. Die Frage ist natürlich, wie groß der Graph sein muß. Man kann diese Fragestellung so veranschaulichen: Wie groß muß eine Gruppe von Menschen mindestens sein, damit sich drei von ihnen paarweise kennen oder paarweise nicht kennen? (Ein Kreis der Länge 4 zeigt hier, daß 4 noch nicht groß genug ist. Reicht 5?) Die Seminarthemen bestehen aus solchen Fragestellungen, die für die Informatik, insbesondere für die Analyse von Algorithmen, interessant sind.

Voraussetzungen

Vordiplom. Vorkenntnisse im Gebiet Diskrete Mathematik sind hilfreich, und man sollte überhaupt Spaß an Mathematik haben.

Hinweise

Themenverteilung

Das Seminar ist auf 14 TeilnehmerInnen ausgelegt, die jeweils einen etwa 60-minütigen Vortrag halten sollen. Bei diesem Seminar wird besonders viel Wert auf die präzise, detaillierte Darstellung der kombinatorischen Probleme und ihrer Lösungen gelegt (Anwendungen und Beispiele müssen herausgestellt, Beweise und Lösungswege sorgfältig nachvollzogen werden). Daher sind die zu verteilenden Themen im Einzelnen nicht besonders umfangreich:

Nr.TerminThemaKapitelVortragende(r)Dateien
1.23.04.04 Einleitungsvortrag: Abzählen Wichtiges aus 1 und 2 Anna Lea Dyckhoff Ausarbeitung, Folien
2.30.04.04 Das Einschluss-Ausschluss-Prinzip 3 (komplett) Philipp Kranen Ausarbeitung, Folien
3.07.05.04 Das Schubfach-Prinzip 4.1, 4.2, 4.4, 4.6 Yan Zhang Ausarbeitung, Folien
4.14.05.04 Systems of Distinct Representatives 5.1, 5.2.1, 5.3, 5.4 Peter Fritz Ausarbeitung, Folien
5.21.05.04 Colorings 6.1, 6.2.1, 6.3 Gregor Hink Ausarbeitung, Folien
6.28.05.04 Sunflowers 7.1, 7.2, 7.3.2 Daniel Brammertz Ausarbeitung, Folien
7.11.06.04 Blocking Sets 10.1, 10.2, 10.4 Bettina Akkapurathu Ausarbeitung, Folien
8.18.06.04 Witness Sets / Das Diktator-Paradox 12.1, 12.3, 12.4 Azadeh Nikookhesal Ausarbeitung, Folien
9.25.06.04 The Linear Algebra Method 14.1, 14.5 Kilic Mahir Ausarbeitung, Folien
10.02.07.04 The Probabilistic Method 17 (komplett) Wladimir Fridman Ausarbeitung, Folien
11.09.07.04 Die Linearität des Erwartungswerts 20.1 bis 20.4, 20.6 Mark Walecki-Mingers Ausarbeitung, Folien
12.16.07.04 The Second Moment Method 22 (komplett) Christoph Schmidt Ausarbeitung, Folien
13.23.07.04 Entropie 23 (komplett) Michael Förster Ausarbeitung, Folien
14.30.07.04 Random Walks 24.1, 24.2, 24.4.1 Dumbiri Gbenoba Ausarbeitung, Folien