Mengers Satz liefert k im Inneren disjunkte Wege zwischen zwei Ecken a und b, es sei denn das offensichtliche Hindernis liegt vor: eine Menge von weniger als k Ecken, die jeden a-b-Weg trifft. Gilt eine solche Eigenschaft auch für andere Objekte als a-b-Wege? Gibt es etwa immer k disjunkte Kreise, es sei denn jeder Kreis trifft eine Menge von weniger als k Ecken? Die Antwort ist nein, wie man leicht am K₄ sieht. Erdös und Pósa zeigten, dass jedoch eine abgeschwächte Form immer noch gilt:

Satz (Erdös & Pósa).

In jedem Graphen G gibt es k disjunkte Kreise oder eine Eckenmenge X der Größe O(k log k), so dass G-X kreislos ist.

In dem Seminar werden wir Arbeiten behandeln, die ähnliche Eigenschaften für andere Objekte als Kreise und a-b-Wege nachweisen. Erdös-Pósa-Eigenschaften ist ein aktives und spannendes Forschungsgebiet. Das Seminar ist gut als Einstieg in eine Bachelor- oder Masterarbeit geeignet.

Anmeldung: per mail an Henning Bruhn-Fujimoto

Modus: wöchentlich (Zeit noch unbestimmt)

Anforderungen: Graphentheorie und/oder die Bereitschaft sich die entsprechenden Konzept selbständig zu erarbeiten.

Themen: kommt noch