Erdös-Posa Eigenschaften auf abelschen Gruppen

Abstract or Introduction

Erdös-Pósa Eigenschaften wurden erstmals in den 1960er-Jahren von Paul Erdös und Lajos Pósa untersucht und bilden eine Verallgemeinerung für Matchings. In dieser Arbeit wird die Größe des Hitting Sets in der Simonovits Frame-Technik genauer untersucht und für den Fall k = 2 auf den optimalen Wert von 3 verbessert, falls keine zwei disjunkten geraden A-Wege existieren. Schließlich wird die Frage der Erdös-Pósa-Eigenschaften für Kreise gerader Länge untersucht und ein elementarer Beweis dafür geführt. Zwar ist schon länger bekannt, dass die Erdös-Pósa-Eigenschaft für gerade Kreise erfüllt ist, allerdings konnte hierfür noch kein elementarer Beweis gegeben werden. Außerdem werden die Erdös-Pósa-Eigenschaften für A-Wege auf beliebigen abelschen Gruppen untersucht und dabei unterschieden, ob die Kanten mit einer Orientierung versehen oder ungerichtet sind.

Dabei stellen sich erstaunliche Unterschiede heraus. Während in der ungerichteten Version auf fast allen endlichen abelschen Gruppen die Erdös-Pósa-Eigenschaft für A-Wege der Länge 0 bezüglich der Gruppe nicht erfüllt ist, kann diese für alle endlichen Gruppen nachgewiesen werden, wenn die Kanten mit einer Orientierung versehen sind und die Länge eines Weges aus der Anzahl der Kanten, die in Richtung der Orientierung durchlaufen werden, abzüglich der Anzahl der Kanten, die entgegen der Orientierung durchlaufen werden, gebildet wird.