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