Tag: MaximilianGorsky

A family $\mathcal{F}$ of (di)graphs is said to have the half- or quarter-integral Erdős-Pósa property if, for any integer $k$ and any (di)graph $G$, there either exist $k$ copies of graphs in $\mathcal{F}$ within $G$ such that any vertex of $G$ is contained in at most 2, respectively at most 4, of these copies, or there exists a vertex set $A$ of size at most $f(k)$ such that $G–A$ contains no copies of graphs in $\mathcal{F}$. Very recently we showed that even dicycles have the quarter-integral Erdős-Pósa property [STOC’24] via the proof of a structure theorem for digraphs without large packings of even dicycles.

In this talk we discuss our current effort to improve this approach towards the half-integral Erdős-Pósa property, which would be best possible, as even dicycles do not have the integral Erdős-Pósa property. Complementing the talk given by Sebastian Wiederrecht in this seminar regarding our initial result, we also shine a light on some of the particulars of the embedding we use in lieu of flatness and how this helps us to move even dicycles through the digraph. In the process of this, we highlight the parts of the proof that initially caused the result to be quarter-integral.

(This is joint work with Ken-ichi Kawarabayashi, Stephan Kreutzer, and Sebastian Wiederrecht.)