FWF - Surfaces - Asymptotische Eigenschaften von Graphen und Flächen

Projektkurzfassung “Asymptotische Eigenschaften von Graphen auf Flächen” Seit Erdős 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 Zufallsgraphen 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 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 Erdős-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.