Dozent: Mathias Schacht
Termine
Beginn der Vorlesung: 16.04.2008.| VL | Mittwoch | 11:15 - 12:45 | (RUD 26, 1'306) |
|---|---|---|---|
| Freitag | 09:30 - 11:00 | (RUD 26, 1'306) | |
| UE | Freitag | 11:15 - 12:45 | (RUD 26, 1'306) |
Zuordnung
- Hauptstudium, Halbkurs
- Theoretische Informatik
Inhalte und Lernziele
Die Veranstaltung behandelt fortgeschrittene Fragestellungen aus der Graphentheorie. Die ausgewählten Themen führen die Vorlesung auf möglichst einfachem Weg zu aktuellen Forschungsfragen und berühmten offenen Problemen in den jeweiligen Gebieten. Behandelt werden unter anderem:- zufällige Graphen,
- extremale Graphentheorie und Ramsey Theorie,
- das Regularitätslemma von Szemerédi.
Voraussetzungen
- Grundstudium
- Die Kenntnis des ersten Teils der Vorlesung ist wünschenswert, aber nicht notwendig.
Übungen
Den Stoff der Vorlesung können Sie besser verstehen, wenn Sie sich aktiv damit beschäftigen. Die Übungen werden Sie dabei unterstützen. Jeden Freitag gibt es ein neues Übungsblatt, das in der Übung verteilt wird. Die Lösungen werden in der darauffolgenden Woche am vor der Übung abgegeben, und dann in der Übung besprochen. Die Übungen sollen einzeln bearbeitet werden.
- Übungsblatt 1 - Abgabe 02.05.2008
- Übungsblatt 2 - Abgabe 09.05.2008
- Übungsblatt 3 - Abgabe 16.05.2008
- Übungsblatt 4 - Abgabe 23.05.2008
- Übungsblatt 5 - Abgabe 30.05.2008
- Übungsblatt 6 - Abgabe 06.06.2008
- Übungsblatt 7 - Abgabe 13.06.2008
- Übungsblatt 8 - Abgabe 27.06.2008
- Übungsblatt 9 - Abgabe 11.07.2008
Literatur
- , The Probabilistic Method, 2. Edition, Wiley Verlag, 2000
- , Random Graphs, 2. Edition, Cambridge University Press 2001
- , Extremal Graph Theory, New York: Academic Press, 1978
- , Graphentheorie, 3. Edition, Springer Verlag, 2006
- , Einführung in Graphen und Algorithmen
- , Graphen und Algorithmen 2, (Link funktioniert nur von Rechnern des Instituts für Informatik)
- , Random Graphs, Wiley Verlag, 2000
English