기초과학연구원 이산수학그룹
The IBS Discrete Mathematics Group welcomes Dr. Maximilian Gorsky, a new research fellow at the IBS Discrete Mathematics Group, from November 1, 2024. He received his Ph.D. from Technische Universität Berlin under the supervision of Prof. Stephan Kreutzer. He is interested in structural graph theory, (structural) matching theory, and structural digraph theory.
On April 30, 2024, Maximilian Gorsky from the Technische Universität Berlin gave a talk on the quarter-integral and third-integral Erdős-Pósa property for even directed cycles at the Discrete Math Seminar. The title of his talk was “Towards the half-integral Erdős-Pósa property for even dicycles“.
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.)