Hauptseminar Graphentheorie im Sommersemester 2009
Kontaktpersonen:
| Peter Rossmanith |
| Alexander Langer (langer@informatik.rwth-aachen.de) |
| Joachim Kneis (kneis@informatik.rwth-aachen.de) |
| Stefan Richter (richter@informatik.rwth-aachen.de) |
Einordnung
Theoretische InformatikOrt und Zeit
Das Seminar findet jeden Montag um 14 Uhr im Seminarraum I1 statt.Inhalt
In diesem Seminar soll es um Graphentheorie und ihre Anwendung gehen. Dabei wird uns das Buch Graph Theory von Reinhard Diestel (PDF-Version auf verlinkter Webseite verfügbar) als Grundlage dienen. Für Anwendungen aus der Informatik werden wir unter Umständen weitere Literatur hinzuziehen.Voraussetzungen
Im Diplomstudiengang: Vordiplom. Interesse an diskreter Mathematik und theoretischer Informatik. Bereitschaft und Fähigkeit zur Begeisterung und Selbstmotivation. Von Vorteil sind Vorkenntnisse in algorithmischen Aspekten der theoretischen Informatik.Termine
| Woche | Vortragende(r) | Thema |
|---|---|---|
| 20.04. | Steffen | Menger's Theorem |
| Oscar | Kuratowski's Theorem | |
| 04.05. | Michael | Szemerédi's regularity lemma |
| 11.05 | Stefan | Szemerédi's regularity lemma |
| 18.05 | Christian | Ramsey theory |
| 25.05. | Deni | The probabilistic method |
| 08.06. | Niklas | The probabilistic method |
| 15.06. | Matthias | WQO and the graph minor theorem for trees |
| 22.06. | Janno | Tree-Decompositions |
| 29.06. | Alexander | Tree-Decompositions |
| 06.07. | Martin | Tree-width and forbidden minors |
| Achim | Graph minor theorem | |
| 13.07 verschoben | Markus | Linearity of grid minors |
| 20.07 verschoben | Lyubomir | Graph separators |
| 27.07 | Yang | Expander graphs |
Deadlines
Spätestens zwei Wochen vor dem jeweiligen Vortrag muss ein Probevortrag gehalten werden. Außerdem muss zu diesem Zeitpunkt die Ausarbeitung abgegeben werden. Spätestens einen Monat nach dem Vortrag müssen alle unsere Anmerkungen zu unserer Zufriedenheit in die Ausarbeitung eingearbeitet sein. Außerdem muss uns jeder Teilnehmer möglichst schnell ein Konzept seiner Ausarbeitung präsentieren.Unsere Hinweise zum Verfassen schriftlicher Arbeiten sind unbedingt zu beachten!