2024 Workshop on (Mostly) Matroids

Erdős-Pósa property of tripods in directed graphs

23 Aug 2024, 13:55

25m

S236 (IBS Science Culture Center)

Presentation (25 min)

Speaker

Meike Hatzel

Description

Let $D$ be a directed graphs with distinguished sets of sources $S\subseteq V(D)$ and sinks $T\subseteq V(D)$.
A tripod in $D$ is a subgraph consisting of the union of two $S$-$T$-paths that have distinct start-vertices and the same end-vertex, and are disjoint apart from sharing a suffix.

This talk presents a proof that tripods in directed graphs exhibit the Erdős-Pósa property.
More precisely, there is a function $f:\mathbb{N}\to \mathbb{N}$ such that for every digraph $D$ with sources $S$ and sinks $T$, if $D$ does not contain $k$ vertex-disjoint tripods, then there is a set of at most $f(k)$ vertices that meets all the tripods in $D$.

One of the tools applied to obtain this result is the matroid intersection theorem for gammoids.
The presented work is joint with Marcin Briański, Karolina Okrasa and Michał Pilipczuk.