Seminar Anwendungen von Zufall und Wahrscheinlichkeit auf Fragen der Diskreten Mathematik Sommersemester 2014 Prof. Stefan Felsner Sprechstunde n.V. LV-Nr.: 3236 L 316

Thema:

• Probabilistic Methods
  Quelle ist das Buch von Alon/Spencer wir wollen insbesondere die neueren Entwicklungen zu LLL studieren.
• Markov Chains and Random Sampling
  Wir beschäftigen uns mit Markov Ketten die es ermöglichen ein zufälliges Element aus einer großen kombinatorischen Menge zu erzeugen (random sampling). Beispiele für solche kombinatorischen Mengen sind:
  • Menge der aufspannenden Bäume eines Graphen (siehe Bild).
  • Menge der perfekten Matchings eines Graphen.
  • Menge der linearen Erweiterungen einer Ordnung.
  Meistens ist es nicht schwer eine Markov Kette anzugeben die wenn man sie lange genug laufen läßt ein zufälliges Element ausgibt. Interessant ist die mathematische Behandlung der Frage, was ist lange genug. Dafür gibt es Techniken wie Kanonische Wege und Couplings.

Termine:

• Vorbesprechung: Donnerstag 13. Feb. 14:15, MA 641.
• Themenzuteilung bis Ende Februar.
• Verpflichtende Rücksprache zwischen 22. und 30. April
• Blitzvorträge: Anfang Mai

Literatur:

• Goffrey Grimmett, Probability on Graphs, Cambridge 2010.
• David A. Levin, Yuval Perles und Elisabeth L. Wilmer, Markov Chains and Mixing Times, AMS 2009.
• Noga Alon und Joel H. Spencer, The Probabilistic Method, John Wiley and Sons.
• Michael Molloy und Bruce Reed, Graph colouring and the probabilistic method, Springer, 2002.
• Mark Jerrum: Counting, Sampling and Intergration: Algorithms and Complexity, Birkhäuser 2003. (Elektronische Kopie von Mark Jerrum -- Direktzugriff)
• Olle Häggström: Finite Markov Chains and Algorithmic Applications, Cambr. Univ. Press, 2002.
• Kapitel aus Motwani-Rhagavan und Mitzenmacher-Upfal.
• Originalarbeiten.

Zielgruppe: