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 Informatik

Ort 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

WocheVortragende(r)Thema
20.04.SteffenMenger's Theorem
27.04. fällt aus OscarKuratowski's Theorem
04.05.MichaelSzemerédi's regularity lemma
11.05Stefan Szemerédi's regularity lemma
18.05ChristianRamsey theory
25.05.DeniThe probabilistic method
08.06.NiklasThe probabilistic method
15.06.MatthiasWQO and the graph minor theorem for trees
22.06.JannoTree-Decompositions
29.06.AlexanderTree-Decompositions
06.07.MartinTree-width and forbidden minors
13.07 fällt ausAchimGraph minor theorem
13.07 verschobenMarkusLinearity of grid minors
20.07 verschobenLyubomirGraph separators
27.07YangExpander 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!

Vorlagen

Einige mit LaTeX-Beamer erzeugte Beispielfolien finden sich hier. Zum Kompilieren benötigt man diese Quellen. Lesenswert ist zudem die Anleitung für das Beamerpaket. Im wesentlichen für Linux: Einige Hinweise und Quelldateien zum Schreiben einer LaTeX-Arbeit gibt es hier. Neben den wichtigsten Textelementen werden auch der Formelsatz sowie das Erzeugen und Einbinden von Metapost-Abbildungen behandelt. Außerdem liegt ein einfaches, aber praktisches Makefile bei.