|
Vorlesung: Probabilistic Method and Random Graphs
Termine
- 16.10.2012 (erste VL)
26.10.2012 (erste UE)
- 23.10.2012 (erste UE)
VL |
Dienstag |
12:15 - 13:45 |
Geomatikum, H6 |
|
Freitag |
14:15 - 15:45 |
Geomatikum, H5 |
UE |
Freitag |
16:00 - 17:30 |
Geomatikum, 430 |
UE |
Dienstag |
16:00 - 17:30 |
Geomatikum, 233 1643 |
Leistungsnachweis
- Bestehen der mündlichen Prüfung
- Termin nach Absprache
Zuordnung
- Vertiefungsvorlesung, Master
- 4+2 SWS
- Graphentheorie und Diskrete Mathematik
Voraussetzungen
- Grundkentnisse aus den Gebieten Graphentheorie,
Diskrete Mathematik und Stochastik sind hilfreich, aber nicht notwendig.
Überblick
Der erste Teil der Vorlesung folgt dem Buch The Probabilistic Method von Alon und Spencer
und der zweite Teil folgt ausgewählten Kapitel des Buches Random Graphs
von S. Janson, T. Łuczak und A. Ruciński. Die Vorlesungen und Übungen erfolgen in
englischer Sprache.
Inhalte
- Grundlagen aus der Stochastik (16.10.) - §1 in [MV])
- Einführende Beispiele (19.10. - 26.10.) - §2 in [MV])
- 1. Momentmethode (29.10. - 02.11.) - §3 und 4 in [MV] und §18.5 in [Ju]
- 2. Momentmethode (06.11. - 20.11.) - §5 in [MV], §3.1 in [JŁR], §4.7 in [AS]
- Local Lemma (23.11. - 30.11.) - §6 in [MV], §5 in [AS]
- Tail inequalities (04.12. - ) - §7 in [MV]
Übungen
Die Übungen werden von Silvia Messuti geleitet. In den Übungen wird der Stoff der Vorlesung
vertieft und es werden die Übungsaufgaben besprochen und von den Studierenden vorgetragen.
Literatur
- N. Alon & J. H. Spencer: The probabilistic method, Wiley, 3rd ed., 2008
- B. Bollobás: Random graphs, Cambridge University Press, 2nd ed., 2001
- S. Janson, T. Łuczak & A. Ruciński: Random graphs, Wiley, 2000
- St. Jukna: Extremal Combinatorics with Applications in Computer Science, Springer, 2. Auflage, 2011
- J. Matoušek & J. Vondrák: The probabilistic method, Vorlesungsskript, 2008
- M. Molloy & B. Reed: Graph colouring and the probabilistic method, Springer, 2002
|
|