Seminar (Graph Colouring) (Winter Semester 2014/15)
- Lecturer: Prof. Dr. Maria Axenovich, Torsten Ueckerdt
- Classes: Seminar (0121300)
- Weekly hours: 2
This is a reading seminar based on the book Graph Colourings and the Probabilistic Method by Michael Molloy and Bruce Reed. Every student presents a part of this book in a talk.
A succesful participation includes:
- presence
- participation
- a good talk
| Schedule | ||
|---|---|---|
| Seminar: | Wednesday 11:30-13:00 | 1C-01 |
| Wednesday 11:30-13:00 | SR 3.68 | |
| Lecturers | ||
|---|---|---|
| Lecturer | Prof. Dr. Maria Axenovich | |
| Office hours: Fr. 10:00-11:00 | ||
| Room 1.043 Kollegiengebäude Mathematik (20.30) | ||
| Email: maria.aksenovich@kit.edu | Lecturer | Torsten Ueckerdt |
| Office hours: | ||
| Room Kollegiengebäude Mathematik (20.30) | ||
| Email: torsten.ueckerdt@kit.edu | ||
Prerequisites
- basic knowledge of graph theory and probability theory
Procedure
- Every student gives a talk on a chapter of the book assigned to him/her.
- Every student attends two weeks before his/her talk personal meeting with Mr. Ueckerdt.
- Every speaker may use the blackboard, the beamer and overhead transparencies. Handouts are optional.
Schedule
| # | part of the book | speaker | pages |
| 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 |