Irene Muzi, 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.