Seminar (Graph Colouring) (Wintersemester 2014/15)
- Dozent*in: Prof. Dr. Maria Axenovich, Torsten Ueckerdt
- Veranstaltungen: Seminar (0121300)
- Semesterwochenstunden: 2
Dies ist ein Lese-Seminar basierend auf dem Buch Graph Colourings and the Probabilistic Method von Michael Molloy und Bruce Reed. Jeder Student stellt einen Teil des Buches in einem eigens konzipierten Vortrag vor.
Zur erfolgreichen Teilnahme gehören:
- Anwesenheit
- Mitarbeit
- ein guter Vortrag
| Termine | ||
|---|---|---|
| Seminar: | Mittwoch 11:30-13:00 | 1C-01 |
| Mittwoch 11:30-13:00 | SR 3.68 | |
| Lehrende | ||
|---|---|---|
| Seminarleitung | Prof. Dr. Maria Axenovich | |
| Sprechstunde: Fr. 10:00-11:00 | ||
| Zimmer 1.043 Kollegiengebäude Mathematik (20.30) | ||
| Email: maria.aksenovich@kit.edu | Seminarleitung | Torsten Ueckerdt |
| Sprechstunde: | ||
| Zimmer Kollegiengebäude Mathematik (20.30) | ||
| Email: torsten.ueckerdt@kit.edu | ||
Vorraussetzungen
- Grundkenntnisse in Graphentheorie und Wahrscheinlichkeitstheorie
Durchführung
- Jeder Student gibt einen Vortrag über ein zugeteiltes Kapitel aus dem Buch.
- Jeder Student trifft sich zwei Wochen vor seinem Vortragstermin mit Herrn Ueckerdt zu einer persönlichen Vorbesprechung.
- Jeder Vortragende kann die Tafel, den Beamer und OHP-Folien benutzen. Handouts sind optional.
Zeitplan
| # | Abschnitt im Buch | Vortragender | Seiten |
| 0. | Introduction | Torsten | -- |
| 1. | First Moment Method | Johannes | 27-36 |
| 2. | The Lovasz Local Lemma and The Chernoff Bound | Matthias | 39-46 |
| 3. | Hadwiger's Conjecture | Xizhe | 49-53 |
| 4. | Total Colouring Revisited | Daniel | 67-75 |
| 5. | Talagrand's Inequality | Annika | 79-89 |
| 6. | Talagrand's Inequality | Jennifer | 79-89 |
| 7. | Azuma's Inequality | Fabian | 91-103 |
| 8. | Strucutral Decomposition | Felix | 157-167 |
| 9. | Chi, Omega and Delta | Torsten | -- |
| 10. | Near Optimal Total Colouring I | Alexander | 185-191 |
| 11. | Generalizations of the Local Lemma | Annette | 221-229 |
| 12. | Finding Fractional Colourings | Valentin | 239-246 |
| 13. | Conditional Expectation and Algorithmic Local Lemma | Oussama | 287-291, 295-300 |