Wednesday, February 7, 2024

2024-02-14 / 16:30 ~ 17:30

IBS-KAIST 세미나 - 이산수학: Packing even directed circuits quarter-integrally

by Sebastian Wiederrecht(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.

Events for the 취소된 행사 포함