Hauptseminar im Sommersemester 2004
Extremal Combinatorics
Kontaktpersonen:
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
-
Vortrag: Die TeilnehmerInnen gestalten das Hauptseminar
durch ihre Vorträge. Im Anschluß an jeden Vortrag
besteht die Möglichkeit zu Fragen an den/die Vortragende/n
und Diskussion.
-
Ausarbeitung: Es ist eine Ausarbeitung von etwa 5-10
Seiten in
LaTeX
zu erstellen.
-
Es gibt nützliche Hinweise, wie man einen
Vortrag hält. Bitte erstellen Sie übersichtliche
Folien mit großem Schriftsatz, Grafiken und evtl.
Farben.
-
Betreuung: Die Vorträge sollen ausgehend von der
angegebenen Literatur selbstständig erarbeitet
werden. Das Konzept soll rechtzeitig in einem Vorgespräch
diskutiert werden. Dabei können auch alle Fragen und Unklarheiten
vor dem Vortrag erörtert werden.
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. | Termin | Thema | Kapitel | Vortragende(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 |
