Packen und Überdecken von Graphen

• Antragsteller: Professor Dr. Felix Joos
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2017 bis 2019
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 339933727

Zerlegungen und Packungen sind zentrale Konzepte der Mathematik: Wie viele Primfaktoren besitzt eine Zahl? Wie dicht lassen sich Kugeln im Raum anordnen? Ist eine gewisse geometrische Form geeignet, um die Ebene lückenlos zu partitionieren? Inhalt dieses Projektes ist die Untersuchung solcher Fragen im Bereich der diskreten Mathematik. Ein Graph ist besteht aus einer (endlichen) Menge V von Ecken (auch Knoten genannt), sowie Verbindungen zwischen Ecken (auch Kanten genannt). Eine Zerlegung eines (großen) Graphen G ist hierbei die Aufteilung von G in viele kleinere Graphen. Diese zentralen Fragestellungen wurden schon seit dem 19. Jahrhundert untersucht und haben Anwendungen zum Beispiel in statistischer Designtheorie, Kodierungstheorie und algebraischer Designtheorie. Probabilistische Methoden haben auf diesem Gebiet in jüngster Zeit spektakuläre Fortschritte ermöglicht. Im Rahmen des Projektes sollen diese Methoden weiterentwickelt werden, um Zerlegungen in große aber dünne Graphen zu erhalten (zum Beispiel Spannbäume und Vereinigungen von Kreisen). Dies ist hauptsächlich motiviert durch eine berühmte Vermutung von Gyárfás und Lehel aus dem Jahre 1976 und das Oberwolfachproblem.Anstatt nach einer (vollständigen) Zerlegung eines gewissen Objektes zu fragen ist es oft sinnvoll, allgemeiner nach maximalen Packungen zu fragen: Wie viele Objekte mit einer gewissen Eigenschaft enthält ein (großes) anderes Objekt? (Zum Beispiel: Wie viele Kugeln passen in eine (große) Kiste?) Dieses Maximierungsproblem ist oft eng verknüpft mit einem dualen Minimierungsproblem. Diesen Zusammenhang kennt man vor allem aus dem Bereich der linearen Optimierung. In der Graphentheorie betrifft dieser Zusammenhang hauptsächlich die Dualität zwischen der Größe einer maximalen Packung und der kleinsten Anzahl an Ecken, die alle Kopien des zu packenden Graphen schneiden, das heißt alle solchen Kopien zu überdecken. Ein weiteres Ziel dieses Forschungsprojektes ist die Untersuchung der Dualität von Packungs- und Überdeckungsparametern, insbesondere der Erdös-Pósa-Eigenschaft von Graphenfamilien.

• DFG-Verfahren: Forschungsstipendien
• Internationaler Bezug: Großbritannien
• Gastgeber: Professor Dr. Deryk Osthus