Struktur in komplexen Graphen

• Antragsteller: Dr. Raphael Mario Steiner
• Fachliche Zuordnung: Mathematik ; Theoretische Informatik
• Förderung: Förderung seit 2026
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 580116532

Ein universelles Meta-Phänomen in der Mathematik, das in verschiedensten Teilbereichen untersucht wird (Chaostheorie, Ergodentheorie, statistische Mechanik, Kombinatorik, ...), ist das Vorhandensein und die Notwendigkeit von Struktur in sehr komplexen und scheinbar chaotischen mathematischen Systemen und Objekten. Drei wichtige Zweige der Kombinatorik betrachten dieses Phänomen von verschiedenen Blickwinkeln: (1) Die chromatische Zahl ist eines der wichtigsten Komplexitätsmaße für Graphen, welches seit fast 200 Jahren untersucht wird. Das eingangs genannte Meta-Phänom leitet einen in diesem Zusammenhang natürlicherweise zu der Frage, welche Struktur(en) man in Graphen, deren hohe Komplexität durch eine hohe chromatische Zahl zertifiziert wird, finden kann. Diese Forschungsfrage wurde und wird eingehend und aktiv untersucht und bildet ein wichtiges Teilfeld der modernen Graphentheorie, mit vielen kürzlichen Fortschritten und Durchbrüchen hin zu fundamentalen Fragestellungen. (2) Eines der grundlegendsten Resultate der Kombinatorik ist der Satz von Ramsey aus dem Jahr 1929. Er besagt dass, in jeder, noch so komplexen, Zerlegung der Kanten eines großen vollständigen Graphen in eine fixierte Anzahl von Teilmengen, immer eine dieser Teilmengen eine Kopie eines gegebenen, strukturierten, Teilgraphen enthalten muss. Der Satz von Ramsey markiert die Geburt eines viel breiteren und aktiv erforschten Teilgebiets der Kombinatorik, der Ramsey-Theorie, welche ganz allgemein Strukturen in komplexen Zerlegungen diskreter Objekte sucht. (3) Pfade und Kreise gehören zu den allgegenwärtigen Objekten in der Graphentheorie, und die damit verwandte Theorie der Hamiltonpfade und -kreise gehört zu einem ihrer ältesten Forschungszweige. Eine typische Fragestellung aus diesem Gebiet sucht nach Bedingungen, welche die Existenz von langen Pfaden und Kreisen, in einem gegebenen, möglicherweise sehr komplexen, Graphen garantieren. Trotz der Aufmerksamkeit, welches dieses Forschungsgebiet erfahren hat, bleibt das aktuelle Verständnis der Struktur von langen Pfaden und Kreisen beschränkt. Dieses Projekt hat zum Ziel, wesentliche Fortschritte bei grundlegenden offenen Fragestellungen aus jedem der oben genannten Zweige zu erzielen, und dadurch unser Verständnis von Struktur in komplexen Graphen deutlich zu erweitern sowie letztendlich einen Beitrag zur eingangs genannten Meta-Fragestellung zu leisten. Konkrete Ziele beinhalten: - Lösung mehrerer seit langem offener Probleme über Substrukturen von und Struktur in Graphen mit hoher chromatischer Zahl, inklusive Fortschritt hin zur berühmten Hadwiger-Vermutung von 1943. - Lösung zentraler Fragestellungen über Ramsey-Eigenschaften von zufälligen diskreten Strukturen. - Fortschritte bei mehreren seit langem bestehenden offenen Problemen zur Struktur längster Pfade und Kreise in Graphen, mit direkten Anwendungen auf eine berühmte Vermutung von Lovász (1969) über sogenannte Knoten-transitive Graphen.

• DFG-Verfahren: Emmy Noether-Gruppen