12.8 Konvergenz in zufälligen Graphen

Inhalt:
Thema des Seminars ist die Analyse von euklidischen Funktionalen in zufälligen Graphen. Behandelt werden insbesondere Eigenschaften von Lösungen für Probleme der euklidischen kombinatorischen Optimierung wie z.B. das Problem der kürzesten Tour durch eine zufällige Punktmenge im ^d oder minimale Spannbäume und Matchings. Die dazu angewandte Methodik – sub- und super-additive Funktionale, isoperimetrische und Konzentrationsungleichungen – wird in dem Seminar im Detail behandelt. Es stellt sich heraus, daß in stochastischen Graphen für eine Reihe von Optimierungsproblemen präzise Asymptotiken gefunden werden können. Das ist recht überraschend, weil zu dem entsprechenden Problem für deterministische Graphen in der Regel keine Ergebnisse bekannt sind.

Literatur:

1. Yukich, J. E.: Probability Theory of Classical Euclidean Optimization Problems. Lecture Notes in Mathematics 1675. Berlin (Springer) 1998
2. Penrose, M. D.: A central limit theorem with application to percolation, epidemics and Boolean models. Ann. Prob. 29, 1515–1546, 2001
3. Penrose, M. D.; Yukich, J. E.: Central limit theorems for some graphs in computational geometry. Ann. Appl. Prob. 11, 1005–1041, 2001