Asymptotische Eigenschaften von Graphen auf Flächen

Seit Erdos und Rényi vor fünf Jahrzehnten die Theorie von Zufallsgraphen begründeten, standen zahlreiche Typen von Zufallsgraphen im Fokus des Interesses. Ein Beispiel hierfür sind Zufallsgraphen auf einer gegebenen Fläche, insbesondere ebene Zufallsgraphen. Graphen mit Einbettungen in 2-dimensionale Flächen, zum Beispiel ebene Graphen und Triangulierungen, gehören zu den meist untersuchten Objekten in der Graphentheorie, abzählenden Kombinatorik, diskreten Wahrscheinlichkeitstheorie und statistischen Physik. Die Hauptziele dieses Projektes sind es, die asymptotischen Eigenschaften und das Grenzverhalten (wie Evolution, Phasenübergänge, kritisches Verhalten und die Verteilung der Komponentengrößen) von Zufallsgraphen auf einer Fläche zu untersuchen und die abzählenden und algorithmischen Aspekte (wie Zusammenhang, Symmetrien, Zerlegungen und zufällige Erzeugung) unbeschrifteter Graphen auf einer Fläche zu studieren. Das Projekt setzt sich die Lösungen wichtiger und herausfordernder offener Probleme zum Ziel, welche angesichts der aktuellen Entwicklungen im Bereich der Zufallsgraphen und der unbeschrifteten Graphen auf einer Fläche in den Mittelpunkt des Interesses rücken. Der Inhalt des Projektes lässt sich in drei Themenbereiche unterteilen, die jedoch eng verbunden sind. Die folgenden Ziele sollen erreicht werden. I. Zufallsgraphen auf Flächen Die Struktur der Komponenten komplexer ebener Zufallsgraphen Das kritische Verhalten von Zufallsgraphen auf einer Fläche Die Schranke für die chromatische Zahl ebener Zufallsgraphen II. Abzählung der unbeschrifteten Graphen auf Flächen Die asymptotische Anzahl unbeschrifteter ebener Graphen Die asymptotische Anzahl unbeschrifteter Graphen auf Flächen positiven Geschlechts Eine systematische Strategie für eine konstruktive Zerlegung entlang von Symmetrien III. Walsh-Boltzmann Sampler für unbeschriftete Graphen auf einer Fläche Walsh-Boltzmann Sampler für unbeschriftete ebene Graphen Walsh-Boltzmann Sampler für unbeschriftete Graphen auf Flächen positiven Geschlechts Eine Strategie zur Zerlegung unter Einbeziehung von Symmetrien und Cycle-pointing Im Gegensatz zu klassischen Zufallsgraphen nach Erdos-Rényi werden durch zusätzliche Bedingungen wie Planarität, Geschlecht oder Symmetrie große Schwierigkeiten bei der Analyse solcher Graphen aufgeworfen, welche nur durch ein Zusammenspiel der probabilistischen, strukturellen und algorithmischen Methoden der Graphentheorie sowie der abzählenden und der analytischen Kombinatorik zu bewältigen sind. Um die Ziele des Projektes zu erreichen, wird es notwendig sein, existierende Ansätze zu erweitern und neue Techniken zu entwickeln, welche Methoden aus der Probabilistik und Graphentheorie mit Methoden der analytischen Kombinatorik (wie Singularitätsanalyse oder Sattelpunktmethode) und der Algorithmik (wie Boltzmann Sampler) verbinden.

Die wissenschaftlichen Ziele des Projektes waren es, asymptotische Eigenschaften und das Grenzverhalten von Zufallsgraphen auf zweidimensionalen Flächen zu untersuchen sowie enumerative und algorithmische Aspekte unbeschrifteter Zufallsgraphen auf einer solchen Fläche zu studieren. Diese Ziele wurden erreicht und das Projekt erfolgreich durchgeführt. Die wichtigsten Errungenschaften des Projektes sind dabei die folgenden fünf Punkte. (1)Die wissenschaftlichen Zielsetzungen des Projektes wurden erfüllt. (2)Die im Rahmen des Projektes erzielten Forschungsergebnisse wurden in angesehenen Fachzeitschriften mit Peer-Review-Verfahren veröffentlicht beziehungsweise sind zur Veröffentlichung dort eingereicht. Insgesamt sind aus diesem Projekt 18 Forschungsartikel hervorgegangen. (3)Die Forschungsergebnisse des Projektes haben eine Doktor- und eine Masterarbeit hervorgebracht und werden die Grundlage für eine Habilitationsschrift bilden. (4)Die Forschungsergebnisse wurden und werden zudem auf wichtigen Fachkonferenzen präsentiert. (5)Neben diesen unmittelbaren wissenschaftlichen Erfolgen besteht ein zusätzlicher positiver Effekt des Projektes auf Kooperationen der Projektleiterin mit führenden Experten. Hierbei wurden einerseits bereits existierende Kooperationen vertieft und andererseits neue Kooperationen ins Leben gerufen. Die wesentlichen Forschungsergebnisse des Projektes betreffen (a) Triangulierungen und kubische Graphen auf Flächen; (b) Zufallsgraphen auf Flächen; (c) den Genus von Erdos- Rényi Zufallsgraphen; (d) Kohomologiegruppen zufälliger Simplizialkomplexe. Mögliche Anwendungen in anderen wissenschaftlichen Disziplinen liegen in der Untersuchung grundlegender Aspekte großer Netzwerke (z.B. Nervenzellen im Gehirn, menschengemachte und natürliche Netzwerke, ökologische Netzwerke, soziale Netzwerke etc.). Diesbezüglich haben sich in der Vergangenheit zahlreiche Modelle von Zufallsgraphen als nützlich erwiesen.