Schriftzug: Fachbereich Mathematik 
  UHH > Fakultäten > MIN-Fakultät > Mathematik > Personen > Mathias Schacht   STiNE |  KUS-Portal |  Sitemap Suchen Hilfe there is no english version of this page  

Vorlesung: Probabilistic Method and Random Graphs

Dozent: Prof. Mathias Schacht

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

  1. Grundlagen aus der Stochastik (16.10.) - §1 in [MV])
  2. Einführende Beispiele (19.10. - 26.10.) - §2 in [MV])
  3. 1. Momentmethode (29.10. - 02.11.) - §3 und 4 in [MV] und §18.5 in [Ju]
  4. 2. Momentmethode (06.11. - 20.11.) - §5 in [MV], §3.1 in [JŁR], §4.7 in [AS]
  5. Local Lemma (23.11. - 30.11.) - §6 in [MV], §5 in [AS]
  6. 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

 
  zurück Seitenanfang  Impressum 2013-01-25, Mathias Schacht