Erdös-Pósa-Eigenschaften

• Antragsteller: Professor Dr. Henning Bruhn-Fujimoto
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2016 bis 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 321904558

Packungs- und Überdeckungsprobleme sind von fundamentaler Bedeutung in vielen Bereichen der Mathematik. Eines der ältesten Probleme dieser Art in der Graphentheorie sind Kreispackungen und -überdeckungen: Wie viele disjunkte Kreise gibt es in einem gegebenem Graphen (Packungsproblem)? Wie viele Ecken müssen ausgewählt werden, um jeden Kreis zu treffen (zu überdecken)? Das klassische Resultat von Erdös und Pósa stellt eine Beziehung zwischen diesen Anzahlen her: Die Größe einer Kreisüberdeckung kann durch eine Funktion der Kreispackungsgröße beschränkt werden. In einem solchen Fall sagt man, dass die Erdös-Pósa-Eigenschaft für die betrachtete Graphenklasse (hier: Kreise) gilt. So haben etwa die Kreise gerader Länge ebenfalls die Erdös-Pósa-Eigenschaft, ungerade Kreise jedoch nicht. Letzteres bedeutet, es gibt Graphen, die nur wenige disjunkte ungerade Kreise haben (tatsächlich keine zwei), in denen jedoch beliebig viele Ecken für eine Überdeckung herangezogen werden müssen.In dem beantragten Projekt möchte ich Erdös-Pósa-Eigenschaften untersuchen. Dabei interessieren mich insbesondere drei Teilgebiete, nämlich Versionen mit labels, Kantenversionen und die Rolle des Zusammenhangs. In jedem Gebiet sollen vorzugsweise möglichst breite Resultate erzielt werden, die bestehende Teilergebnisse als Spezialfälle enthalten. Bei den Versionen mit labels werden die Ecken zusätzlich mit labeln versehen, die bei der Packung respektiert werden müssen. So lassen sich stärkere Aussagen formulieren. Kantenversionen der Erdös-Pósa-Eigenschaft betrachten kantendisjunkte Packungen anstelle von eckendisjunkten Packungen, wie es gewöhnlich der Fall ist. Über kantendisjunkte Packungen ist deutlich weniger bekannt. Das dritte Teilgebiet betrifft Graphenklassen, die die Erdös-Pósa-Eigenschaft nicht haben (wie ungerade Kreise). Oftmals erhält man dennoch die Eigenschaft, sofern der umgebende Graph (moderate) hoch-zusammenhängend ist. Dies ist etwa für die kantendisjunkten ungeraden Kreise der Fall, sobald der umgebende Graph 4-zusammenhängend ist. Ist dies ein allgemeines Phänomen?

• DFG-Verfahren: Sachbeihilfen