기초과학연구원 이산수학그룹
On March 4, 2025, Irene Muzi from the University of Hamburg gave a talk at the Discrete Math Seminar on obtaining a better bound for the Erdős-Pósa property of directed cycles. The title of her talk was “An elementary bound for Younger’s conjecture“.
In 1996, Reed, Robertson, Seymour and Thomas proved Younger’s Conjecture, which states that for all directed graphs D, there exists a function f such that if D does not contain k disjoint cycles, D contains a feedback vertex set, i.e. a subset of vertices whose deletion renders the graph acyclic, of size bounded by f(k). However, the function obtained by Reed, Robertson, Seymour and Thomas is enormous and, in fact, not even elementary. The bound had, so far, not been improved. In this talk, I will present new techniques to improve the bound from non-elementary to elementary. This is joint work with Meike Hatzel, Stephan Kreutzer and Marcelo Milani.