Seminar: Die probabilistische Methode

Viele Probleme in der Kombinatorik und Graphentheorie können elegant mit Hilfe der probabilistischen Methode gelöst werden. Die zentrale Idee der probabilistischen Methode ist es, die Existenz von gewissen Objekten nicht-konstruktiv dadurch zu zeigen, dass man nachweist, dass Objekte mit positiver Wahrscheinlichkeit die gewünschten Eigenschaften besitzen. Die Kunst besteht dann darin, geeignete Wahrscheinlichkeitsräume zu konstruieren und die Wahrscheinlichkeiten gut abzuschätzen.

graphs of high girth and high chromatic number

graphs of high girth and high chromatic number

Zum Beispiel liefert die probabilistische Methode, dass Graphen mit einem interessanten Spannungsverhältnis zwischen lokalen und globalen Eigenschaften existieren und dass in bestimmten Spielen gewisse Gewinnstrategien existieren. Andererseits kann man mit der probabilistischen Methode aber auch klassische Resultate wie den Approximationssatz von Weierstrass beweisen.

In diesem Seminar werden wir uns sowohl mit klassischen Methoden der Kombinatorik als auch mit der probabilistischen Methode befassen. Die nötigen Grundlagen aus der Wahrscheinlichkeitstheorie werden im Seminar bzw. in der Vorlesung Wahrscheinlichkeitstheorie erarbeitet.

Leistungsnachweise, die Teilnahmevoraussetzung sind Analysis I/II, Lineare Algebra I/II; Analysis III oder Wahrscheinlichkeitstheorie (es genügt, Wahrscheinlichkeitstheorie parallel im SS 2012 zu hören).