Forschungsinstitut für Diskrete Mathematik

Seminar Diskrete Optimierung

Wintersemester 2003/04


Thema: Graph colouring and the probabilistic method


Grundlage des Seminars werden Kapitel aus den folgenden Büchern sein:

- M. Molloy und B. Reed: Graph colouring and the probabilistic method. Algorithms and Combinatorics. 23. Berlin, Springer (2002).

- N. Alon und J. Spencer: The probabilistic method. With an appendix on the life and work of Paul Erdös. 2nd ed. Wiley-Interscience Series in Discrete Mathematics and Optimization. Chichester, Wiley (2000).

Termin: freitags 16:15 - 17:45 im Seminarraum des Instituts


Nr. Datum Name Thema Betreuung
1 17. 10. Roman Scherzer First Moment Method Ulrich Brenner
2 24. 10. Robert Spindler Lovász Local Lemma Sven Peyer
3 31. 10. Fabio Hake Algorithmical Aspects Ulrich Brenner
4 7. 11. Hendrik Ewe Chernoff Bound Stephan Held
5 14. 11. Christian Schulte Assignments using Fractional Colourings Dirk Müller
6 21. 11. Björn Bales Talagrand's Inequality Sven Peyer
7 28. 11. Jennifer Wolf Total Colouring Jens Maßberg
8 5. 12. Elias Schäfer Discrepancy Stephan Held
9 19. 12. Sanaz Kamali Codes, Games and Entropy Jürgen Werber
10 16. 1. Ilia Achkinazi Azuma's Inequality Ulrich Brenner

Scheinkriterien:

erfolgreicher Seminarvortrag, regelmäßige Teilnahme an den Veranstaltungen und aktive Mitarbeit
B. Korte
D. Rautenbach
J. Vygen