A Polynomial Erdős-Pósa bound for Eulerian digraphs

@misc{galby2026polynomial,
  title = {{A Polynomial Erdős-Pósa bound for Eulerian digraphs}},
  author = {Esther Galby and Roohani Sharma and Bart van der Steenhoven},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.06250},
  eprint = {2611.06250},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.06250},
  note = {CC BY 4.0},
}

TY  - UNPB
TI  - A Polynomial Erdős-Pósa bound for Eulerian digraphs
AU  - Esther Galby
AU  - Roohani Sharma
AU  - Bart van der Steenhoven
PY  - 2026
DA  - 2026/11/04
PB  - arXiv
DO  - 10.48550/arxiv.2611.06250
UR  - https://arxiv.org/abs/2611.06250
AB  - In [Combinatorica 1996], Reed, Robertson, Seymour and Thomas proved Younger's conjecture dating back to 1973 that states that directed cycles have the Erdős-Pósa property. Specifically, they showed that every directed graph D contains either k arc-disjoint cycles or a set of at most f(k) arcs that intersect every directed cycle. The function f, depending only on k, is however notoriously large--in fact, not even elementary. The first improvement on this function was only very recently provided by Hatzel, Kreutzer, Milani, and Muzi [FOCS 2024] who showed that f can be taken to be an exponential tower of height $8$. In this work, we improve this function to O(k^4) in the case where the digraph is Eulerian. This also answers an open question by Wahlström [Springer Monographs in Mathematics 2018] who asked explicitly when Eulerian digraphs have a polynomial Erdős-Pósa property. The only other known result about Erdős-Pósa on Eulerian digraphs is a result from Seymour [Combinatorica 1996] who showed that f(k)=k when the Eulerian digraph admits a linkless embedding in 3-space, and such an equality is not possible for general Eulerian digraphs. We also complement our positive result, by showing that the result of Seymour cannot be extended to give a linear bound (O(k)) on general Eulerian digraphs, by showing that even on Eulerian digraphs the lower bound for the Erdős-Pósa property is Ω(k log k).
ER  -