- This event has passed.
Sebastian Wiederrecht, Packing even directed circuits quarter-integrally
February 14 Wednesday @ 4:30 PM - 5:30 PM KST
Room B332,
IBS (기초과학연구원)
We prove the existence of a computable function $f\colon\mathbb{N}\to\mathbb{N}$ such that for every integer $k$ and every digraph $D$ either contains a collection $\mathcal{C}$ of $k$ directed cycles of even length such that no vertex of $D$ belongs to more than four cycles in $\mathcal{C}$, or there exists a set $S\subseteq V(D)$ of size at most $f(k)$ such that $D-S$ has no directed cycle of even length.
This is joint work with Maximilian Gorsky, Ken-ichi Kawarabayashi, and Stephan Kreutzer.