Speaker
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\colon \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.
