FG 413: Algorithmen III (-4)

<p>Üblicherweise besagt ein mathematischer Satz, dass alle Elemente einer festgelegten Klasse eine bestimmte Eigenschaft haben. Im Gegensatz dazu hat dieses Projekt die Charakterisierung zufälliger Objekte als zentrales Thema. Gemeint ist hiermit die Suche nach strukturellen Eigenschaften, die ein zufällig aus einer Klasse ausgewähltes Element mit hoher Wahrscheinlichkeit hat.</p>

<p>Die Beantwortung der Charakterisierung zufälliger Objekte und der durch sie charakterisierten Fragestellungen dieses Projekts ist in vielen Fällen die Grundvoraussetzung für eine probabilistische Analyse eines Algorithmus. Eine solche Analyse, bei der die Leistung des Algorithmus an einer (gemäß einer stochastischen Verteilung) zufällig ausgewählten Instanz gemessen wird, beruht auf den Eigenschaften eines typischen Elements des Suchraums und ein vollständiges Bild dieser typischen Struktureigenschaften wiederum ergibt sich häufig erst dann, wenn die Evolution der zugrunde liegenden Klasse geklärt ist.</p>

<p>Ein wesentlicher Bestandteil dieses Teilprojekts besteht in der Untersuchung der Evolution von G(n,p). Der Evolutionsaspekt besteht darin, dass man wissen möchte, wie sich typischen Eigenschaften von G(n,p) mit wachsender Kantenwahrscheinlichkeit p verändern. Für viele Parameter ist das Evolutionsverhalten inzwischen geklärt. Für "komplexe" Parameter wie die Listenchromatische Zahl oder die Theta-Funktion sind wesentliche Fragen noch offen. Neuere Hilfsmittel wie z.B. die Talagrand-Ungleichung haben allerdings in jüngster Zeit erhebliche Fortschritte ermöglicht.</p>

<p>Weitaus weniger weiß man bisher über die Evolution von zufälligen Graphen mit Nebenbedigungen. In diesem Teilprojekt werden drei verschiedene Nebenbedingungen betrachtet:<br>
Erstens zufällige Graphen mit verbotenen Teilgraphen,<br>
zweitens zufällige planare Graphen und<br>
drittens sogenannte "kleine Welt"-Netzwerke.</p>

<p>Ein wesentliches Ziel bei der Untersuchung solcher Netzwerke ist die Charakterisierung (im Sinne von Charakterisierung von Objekten durch Zufall) von komplexen Netzwerken durch geeignete Zufallsmodelle.</p>