Die probabilistische Methode

Vorlesung im Wintersemester 2004/2005

Dozent: PD Dr. Aicke Hinrichs

Vorlesungen: Mo 10-12 Ernst-Abbe-Platz 2, Raum 3517

Es ist sechs Uhr morgens. Das ganze Haus schläft.
Schöne Musik ist zu hören. Ich beweise und vermute.

Paul Erdös, in einem Brief an Vera Sos

Übungsserien und Skript

Vorlesungsankündigung:

Diese Vorlesung widmet sich der probabilistischen Methode, ohne die ein großer Teil der modernen Mathematik undenkbar ist. Oft steht der Mathematiker vor dem Problem, gewisse Objekte mit vorgegebenen guten Eigenschaften konstruieren zu müssen. Eine explizite Konstruktion ist aber schwierig, vielleicht unmöglich. Dann kann man eine probabilistische Konstruktion versuchen, indem man aus einem großen Vorrat an Objekten eines zufällig auswählt. Die probabilistische Methode (und das ist ihre Stärke und Schönheit) beweist nun, daß so ein zufällig gewähltes Objekt mit positiver Wahrscheinlichkeit die gewünschten Eigenschaften hat. Also muß so ein Objekt existieren!

Diese Methode wird mit großem Erfolg in so unterschiedlichen Gebieten wie Kombinatorik, Graphentheorie, Zahlentheorie, Geometrie, Analysis und Numerik angewendet. Man kann auch die Nutzung randomisierter Algorithmen in der Informatik dazuzählen. Das Ziel der Vorlesung ist es, den Hörern die große Anwendungsbreite und die mathematische Eleganz der probabilistischen Methode nahezubringen. Dazu werden wir in jeweils einer oder zwei Vorlesungen ein konkretes Problem aus einem der oben angeführten Gebiete behandeln.

Die Vorlesung verlangt außer einer gewissen mathematischen Reife keine Voraussetzungen, die über im Grundstudium für Mathematiker und Informatiker vermittelte Kenntnisse hinausgehen. Die notwendigen Begriffe und Resultate aus der Wahrscheinlichkeitstheorie werden an der passenden Stelle eingeführt. Für Hörer, die die probabilistische Methode auch aktiv erlernen möchten, werden Probleme und Übungsaufgaben zur selbständigen Bearbeitung angeboten. Eine separate Übung ist nicht vorgesehen, kann aber bei Bedarf von Zeit zu Zeit in die Vorlesung eingebaut werden.

Literaturempfehlungen: Die ersten beiden Bücher gibt es in der Bibliothek unter den angegebenen Signaturen. Die Lecture Notes von Matousek und Vondrak gibt es online zum Selbstausdrucken.

1. N. Alon, J. H. Spencer: The probabilistic method. John Wiley & Sons, MAT:05.::A454::1992
2. B. Bollobas: Random graphs. Cambridge University Press, MAT:05.::B692:(2):2001
3. M. Molloy, B. Reed: Graph Coloring and the Probabilistic Method. Springer-Verlag
4. J. Matousek, J. Vondrak: The probabilistic method. Lecture notes

Friedrich-Schiller-Universität    Jena      Fakultät für Mathematik & Informatik       Mathematisches Institut