Neue Ansätze zur Zerlegung von Graphen in der Minorentheorie

• Antragsteller: Dr. Jan Kurkofka
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung seit 2025
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 566118291

Der Minorensatz für Graphen wurde 20 Jahre lang auf 500 Seiten von Robertson und Seymour bewiesen und ist einer der tiefgreifensden Sätze der Mathematik. Ein Graph X ist ein Minor eines Graphen G, wenn man X aus G durch Löschen von Ecken oder Kanten und durch Kontrahieren von Kanten zu Ecken erhalten kann. In der Minorentheorie werden Graphenklassen studiert, die unter Minorenbildung abgeschlossen sind. Ein Beispiel ist die Klasse der planaren Graphen: Graphen, die in der Ebene ohne kreuzende Kanten gezeichnet werden können. Ein grundlegendes Resultat der Theorie ist der Satz von Kuratowski, laut dem ein Graph planar ist genau dann, wenn er weder den vollständigen Graphen auf fünf Ecken noch den Graphen auf 3 vs 3 Ecken mit allen möglichen Zwischenkanten als Minor enthält. Der Minorensatz ist eine Erweiterung des Satzes von Kuratowski: Er besagt, dass jede Minoren-abgeschlossene Graphenklasse durch eine Liste von nur endlich vielen verbotenen Minoren charakterisiert wird. Beispiele für Minoren-abgeschlossene Klassen reichen von topologischen Klassen wie Graphen, die in einer gegebenen Fläche eingebettet werden können, bis hin zu Graphen mit begrenzter Baumweite, welche eine wichtige Rolle in der Komplexitätstheorie spielen. Der Minorensatz hat eine bahnbrechende Folgerung in der Informatik: für jede Minoren-abgeschlossene Graphenklasse gibt es einen effizienten Algorithmus, der Zugehörigkeit zu der Klasse entscheidet. Die Minorentheorie hat weite Auswirkungen in der Mathematik und Informatik. Mein Ziel ist, die Grenzen der Minorentheorie zu erweitern, indem ich neue Struktursätze beweise, welche Anwendungen an großen Herausforderungen in der Informatik, Data Science und Algebra ermöglichen: 1. Entwicklung neuer vielseitiger Werkzeuge zur Findung der verbotenen Minoren für Minoren-abgeschlossene Graphenklassen. Während Courcelle et al. bewiesen haben, dass es keinen Algorithmus gibt, der, gegeben einen Ausdruck (in MSO) welcher eine Minoren-abgeschlossene Graphenklasse beschreibt, die verbotenen Minoren dieser Klasse findet, ist das Problem, die verbotenen Minoren für bestimmte Klassen zu finden - und dadurch einen effizienten Zugehörigkeitstest zu erhalten - von großer Bedeutung in der Informatik. 2. Data Science stellt die Mathematik vor neue Herausforderungen. Eine zentrale Herausforderung besteht darin, die Struktur großer spärlicher Netzwerke zu untersuchen, die aus Anwendungen wie Infrastruktur, sozialen Netzwerken oder biologischen Netzwerken stammen. Das volle Potenzial der Minorentheorie in diesem Bereich muss noch erschlossen werden. 3. In der Algebra wird seit Langem nach einer Erweiterung der Bass-Serre-Theorie auf endliche Gruppen gesucht. Gruppen können durch geometrische Repräsentationen wie Cayleygraphen mit Werkzeugen der Kombinatorik untersucht werden. Die Erweiterung der Minorentheorie zu mehr Explizitheit und Inklusion spärlicher Netzwerke ermöglicht Anwendungen auf Gruppen.

• DFG-Verfahren: Sachbeihilfen