Albert-Ludwigs-Universität Freiburg
	Institut für mathematische Logik und Grundlagen der Mathematik

Vorlesung: Zufällige Strukturen

Zeit und Ort: Mi 16-18 Uhr, SR318, Eckerstr. 1
 

``Mit welcher Wahrscheinlichkeit ist ein zufällig gewählter endlicher Graph zusammenhängend?''

 ``Wieviele Dreiecke können wir in einem zufälligen Graphen erwarten?''

Derartige Fragen wollen wir zunächst präzisieren, dazu benötigen wir geeignete Wahrscheinlichkeitsmaße auf endlichen Graphen und anderen Strukturen. Wir wollen dann grundlegende Techniken im Umgang mit zufälligen Strukturen studieren. Ein Ziel der Vorlesung ist es, allgemeine Sätze der folgenden Gestalt zu beweisen (sog. 0-1 Gesetze):

Sei E eine Eigenschaft endlicher Strukturen, die sich in einer gewissen formalen Sprache (zum Beispiel der Logik der 1.Stufe) formulieren läßt. Dann haben entweder fast alle Strukturen die Eigenschaft E oder fast alle Strukturen haben die Eigenschaft E nicht.}

Es können also allein aus der sprachlichen Beschreibung einer Eigenschaft Schlußfolgerungen über ihr Auftreten gezogen werden. Die Untersuchung zufälliger Strukturen ist aber nicht allein Selbstzweck, sondern hat zahlreiche Anwendungen in der Kombinatorik, Zahlentheorie, Geometrie und Informatik. Zum einen kann man die Existenz von Objekten mit gewissen Eigenschaften oft dadurch nachweisen, daß man zeigt, daß ein geeignet gewßhltes zufälliges Objekt die gewünschte Eigenschaft besitzt. Zum anderen verwendet man Algorithmen, die bloß ``fast immer'' das richtige Ergebnis liefern. Ein zweites Ziel der Vorlesung ist es, einen Eindruck von verschiedenen Anwendungen der sog. probabilistischen Methode zu vermitteln.

Vorausgesetzt werden Kenntnisse der Stochastik, etwa im Umfang einer einführenden Vorlesung. Die notwendigen Logikkenntnisse werden in der Vorlesung bereitgestellt.

Literatur zur Vorlesung

Alon, Spencer, Erdös: The Probabilistic Method, 1992.

Bollobás: Random Graphs, 1985.

Palmer: Graphical Evolution, 1985.

Spencer: Random Graphs (The Ohio State Lectures), 1993.
 

Diestel: Graphentheorie, 1996.

Ebbinghaus, Flum, Thomas: Mathematische Logik, 3. Auflage 1992.

Feller: An Introduction to Probability Theory and Its Applications, Volume I, 3. Auflage 1968.

21.1.1999 Markus Frick