Seminar über Wahrscheinlichkeitstheorie:
Dynamik zufälliger Graphen

Kontakt

Prof. Dr. R. Neininger
Prof. Dr. A. Wakolbinger
Dipl. Math. H. Sulzbach

Organisatorisches

Termin: Do 14-16 Uhr, Ort: 711 groß, Beginn: 18.10.07.
Voraussetzungen: Elementare Stochastik und Stochastische Prozesse oder Höhere Stochastik.
Bei der Vorbereitungszeit für den Vortrag sollte man mit ca. 6 Wochen rechnen. Spätestens 4 Wochen vor dem Vortragstermin sollte die/der Vortragende bei dem Betreuer vorbeikommen. Spätestens 2 Wochen vor dem Vortagstermin muss ein Thesenblatt (Handout) mit den wichtigsten Aussagen abgegeben werden. Dieses wird dann vor dem Vortrag an die Seminarteilnehmer ausgeteilt.
Zusätlich muss eine Ausarbeitung des Vortrags (in Maschinenschrift 4-8 Seiten) nach dem Vortrag, spätetens in der letzten Semesterwoche abgegeben werden. Diese sollte die Aussagen kommentieren und Beweise enthalten, wobei auf technische Finessen verzichtet werden kann. Es ist empfehlenswert, diese, wie auch das Handout, am Computer mit dem Programm "LaTex" zu erstellen. Natürlich werden auch handschriftliche Ausarbeitungen und Handouts akzeptiert. Näheres zu LaTex siehe unten.

Vorträge

25.10.07: Teilgraphen in G(n,p)
Christine Schottmüller

Einführung, vollständige Teilgraphen der Größe 4, second moment method, Threshold für bestimmte Teilgraphen.

Spencer: Seiten 17-23,
Bollobas: Seiten 78-85.

Handout (.pdf)

01.11.07: Zusammenhang von G(n,p)
Paul Knihs

Bedingungen für Zusammenhang, Anzahl isolierter Ecken, Asymptotik im kritischen Bereich.

van der Hofstad: Seiten 108-112,
Spencer: Seiten 17-27.

Handout (.pdf), Ausarbeitung (.pdf)

08.11.07: Die größte Zusammenhangskomponente
Henning Sulzbach

Überblick über die Größe von Zusammenhangskomponenten.

v.d. Hofstad: Auszüge aus den Kapiteln 3, 4, 5.

Handout (.pdf)

22.11.07: Cliquenzahl und chromatische Zahl
Ralph Neininger

Konzentration und Asymptotik der Cliquenzahl und chromatischen Zahl, Martingale, Ungleichung von Azuma-Hoeffding.

Spencer: Seiten 51-55.

29.11.07: Die Janson-Ungleichungen und Anwendungen I
Markus Huber

Ungleichungen von Janson, Probabilitische Methode, Asymptotik der chromatischen Zahl im Fall p = 1/2.

Spencer: Seiten 51-55, 81-86.

Handout (.pdf), Ausarbeitung (.pdf)

06.12.07: Die Janson-Ungleichungen und Anwendungen II
Markus Huber, Das "Preferential Attachment" Modell I
Christoph te Kampe

Erweiterte Janson-Ungleichung, Dreiecke in G(n,p) - Modell, Eckengrade.

van der Hofstad: Seite 155-179.

Handout (.pdf), Ausarbeitung (.pdf)

13.12.07: Das "Preferential Attachment" Modell II
Christoph te Kampe

Fortsetzung, weitere Ergebnisse.

van der Hofstad: Seite 155-179,
Handout (.pdf)


20.12.07: Small worlds
Timo Baumgratz

typischer Abstand zwischen 2 Knoten im kontinuierlichen Modell.

Durrett: Seiten 132-139.

Handout (.pdf), Ausarbeitung (.pdf)


24.01.08: The Lovasz Local Lemma
Brooks Ferebee

Handout (.pdf)


16.01.08: Rhein-Main Kolloquim Stochastik: "Zufällige Netzwerke"

15.15 Uhr - 16.15 Uhr: Prof. Dr. Remco van der Hofstad (TU Eindhoven)

Titel: Universality of distances in power-law random graphs

16.15 Uhr - 16.45 Uhr: Kaffee und Tee

16.45 Uhr - 17.45 Uhr: PD Dr. Mihyun Kang (HU Berlin)

Titel: Evolution, phase transition and giant component of random graphs.



Literatur

Bollobás, B. (2001) Random graphs. Second edition.
Cambridge Studies in Advanced Mathematics, 73. Cambridge University Press, Cambridge. xviii+498 pp.
ISBN: 0-521-80920-7; 0-521-79722-5

Durrett, R. (2007) Random graph dynamics.
Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge. x+212 pp.
ISBN: 978-0-521-86656-9; 0-521-86656-1

van der Hofstad, R. (2007) Random Graphs and Complex Networks.
Lecture Notes, TU Eindhoven.

Janson, S. Luczak, T. und Rucinski, A. (2000) Random graphs.
Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York. xii+333 pp.
ISBN: 0-471-17541-2

Spencer, J. (1994) Ten lectures on the probabilistic method. Second edition.
CBMS-NSF Regional Conference Series in Applied Mathematics, 64. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA. vi+88 pp.
ISBN: 0-89871-325-0

LaTex

Nachfolgender Text und Beispieldateien sind von einer älteren Seminarseite übernommen und wurden von Martin Hutzenthaler erstellt, vielen Dank an dieser Stelle.

Das folgende ist für LaTeX-Anfänger auf Windows gedacht.

Das Standard LaTeX Programm für MiKrosoft heißt MiKTeX. Hier kann man es sich herunterladen. Desweiteren benötigt man einen Editor. Es sollte im MiKTeX-Paket ein LaTeX-Editor dabei sein. Eine Suche im Netz nach besseren Editoren lohnt sich eventuell. Nach der Installation kann es los gehen.

LaTeX ist ein Programm, welches eine Quelldatei, übliche Dateiendung .tex, in eine pdf-Datei übersetzt. In einem LaTeX-Editor geschieht dies durch Drücken eines Buttons, der zB "Übersetzen" oder "Setzen" heissen könnte. Zum Test der Installation sollte man eine Minimal-Quelldatei übersetzen, beispielsweise hello_world.tex (download). Also diese Datei herunterladen, mit dem Editor öffnen und übersetzen. Das Ergebnis sollte hello_world.pdf (im selben Verzeichnis) sein, welches nur den Text "Hello World!" enthält. Falls das funktioniert hat, kann es weitergehen.

Die Quelldateien WienerHopf.tex (download) und Austauschbar.tex (download) enthalten einige Befehle und könnten für die ersten Schritte als Beispiel nützlich sein. Die zugehörigen pdf-Dateien sind WienerHopf.pdf und Austauschbar.pdf. Beide Beispieldateien binden die Datei global.tex (download) ein, welches meine LaTeX-Konfiguration enth"alt. Die Beispieldateien können nur übersetzt werden, wenn sich global.tex in demselben Verzeichnis befindet.

Es ist unumgänglich, sich ein LaTeX-Buch zu besorgen (zB aus der Bibliothek). Man kann LaTeX ohne Buch nicht lernen.