Phasenübergänge und kritische Phänomene in Zufallsgraphen

Ein zentrales Thema der diskreten Mathematik ist die Theorie der Zufallsgraphen. Den Schwerpunkt dieses Projekts bilden Zufallsgraphenprozesse und zufälligen Hypergraphen. Langzeit- bzw. globalen Abhängigkeiten zwischen Kanten erschweren die Analyse des asymptotischen Verhaltens dieser Modelle und deshalb bedarf es neuer Methoden um zufriedenstellende Ergebnisse zu erzielen. In diesem Projekt sollen analytische und probabilistische Ansätze weiterentwickelt und daraufhin mit deren Hilfe das Langzeitverhalten solch komplexer Modelle von Zufallsgraphen untersucht werden. Das Hauptaugenmerk des Projekts liegt auf den beiden folgenden, eng verwandten Themen. (1) Zufallsgraphenprozesse -- Entwicklung einer universellen, analytischen Methodik für das Studium des Phasenübergangs -- Kritische Phänomene und die Verteilung der Größen der Komponenten. (2) Zufällige Hypergraphen -- Ansätze basierend auf der Erkundung von Komponenten durch Breiten- und Tiefensuche -- deren Anwendung auf zufällige Hypergraphen, insbesondere im super-kritischen Bereich. Im Mittelpunkt des ersten Teils dieses Projekts steht die Erforschung von Entwicklungsprozessen von Zufallsgraphen inspiriert durch das sogenannte paradigm of the power of multiple choices. Anstatt klassische probabilistische Idee zu benutzen, ist vorgesehen, auf Grundlage der Methode der Charakteristiken, eine analytische Methodik zu entwickeln um Lösungen quasi-linearer partieller Differentialgleichungen zu bestimmen und deren lokale Eigenschaften zu untersuchen. Diese analytische Methodik soll daraufhin dazu eingesetzt werden das Verhalten zufälliger Graphen, bei denen sequentiell eine von mehreren zufällig ermittelten Kanten ausgewählt wird, im Detail zu beschreiben. Das vorgeschlagene Projekt ist von grundlegender Bedeutung, da bisher nur einige spezielle Modelle solcher zufälliger Graphen und bestimmte Eigenschaften verstanden werden konnten und darüber hinaus auch noch kein universeller, analytischer Ansatz existiert, welcher eine umfassende Analyse komplizierterer Modelle erlauben würde. Das Ziel des zweite Teil dieses Projekts besteht darin zwei Ansätze zur Analyse super-kritischer Zufallsgraphen mit Hilfe von Erkundungs-Prozessen in den Komponenten weiterzuentwickeln: Einer davon basiert auf der Breitensuche und verwendet einen dualen Prozess (kürzlich überarbeitet von Bollobas und Riordan) und der andere basiert auf der Tiefensuche (ein moderner Ansatz von Krivelevich and Sudakov). Beide Ansätze wurden bisher nur dazu verwendet den klassischen Erdos-Renyi Zufallsgraph zu analysieren, führen dort jedoch zu einfachen und sehr kurzen Beweisen. Im vorgeschlagenen Projekt sollen diese Ansätze weiterentwickelt und für super-kritische Hypergraphen adaptiert werden, da diese zur Zeit noch unzureichend erforscht sind. Hierbei werden fortschrittlichere Methoden vonnöten sein, insbesondere aus der Theorie der Galton-Watson Prozesse und der Theorie der Martingale.

Die Zielsetzung des Projektes war es, das asymptotische Verhalten von Zufallsgraphenprozessen sowie zufälliger Hypergraphen zu untersuchen. Zu diesem Zweck sollten analytische und wahrscheinlichkeitstheoretische Ansätze weiterentwickelt werden. Das Projekt wurde in Gänze erfolgreich durchgeführt und die wissenschaftlichen Ziele wurden erreicht. Die wesentlichen Erfolge des Projektes lassen sich in den folgenden fünf Punkten zusammenfassen: (1) Die wissenschaftlichen Zielsetzungen des Projektes wurde erfolgreich erfüllt. (2) Sämtliche dem Projekt entsprungenen Forschungsergebnisse wurden in führenden Zeitschriften mit Peer-Review Verfahren sowie in Tagungsbänden internationaler Konferenzen veröffentlicht, beziehungsweise zur Veröffentlichung eingereicht. Der Gesamtumfang beläuft sich auf 20 Artikel. (3) Die wichtigsten Ergebnisse werden laufend im Rahmen bedeutender Fachkonferenzen präsentiert. (4) Die Forschungsergebnisse haben eine Doktorarbeit hervorgebracht. (5) Zudem wurden existierende Zusammenarbeiten der Projektleiterin und ihren Teammitgliedern mit führenden Experten auf dem Gebiet vertieft und weitere Kooperationen geknüpft. Bei den wichtigsten Forschungsergebnissen des Projektes handelt es sich um (a) das Auftreten einer "giant Component" von höherem Zusammenhang in zufälligen Hypergraphen, (b) die Ermittlung der Schwellenwahrscheinlichkeit für Jigsaw-Percolation auf zufälligen Hypergraphen, (c) der Phasenubergang von Bootstrap-Prozessen auf inhomogenen Zufallsgraphen, (d) Analyse der Art und Weise, in welcher der k-Core in einem Zufallsgraphen eingebettet ist. Seit die Theorie von Zufallsgraphen vor einem halben Jahrhundert eingeführt wurde, hat sie in der Zwischenzeit ihren Weg in andere Wissenschaften gefunden und sich dort als üppiger Quell von Modellen erwiesen, mit Hilfe derer sich die grundlegenden Eigenschaften einer großen Bandbreite komplexer Strukturen und Phänomene beschreiben lassen, welche in vielen verschiedenen Bereichen auftreten (z.B. in Umwelt- oder Sozialwissenschaften sowie in Bezug auf von Menschenhand geschaffene Netzwerke oder das Gehirn).