Erdős-Pósa from ball packing

Abstract

A classic theorem of Erdős and Pósa (1965) states that every graph has either $k$ vertex-disjoint cycles or a set of $O(k\log k)$ vertices meeting all its cycles. While the standard proof revolves around finding a large `frame' in the graph (a subdivision of a large cubic graph), an alternative way of proving this theorem is to use a ball packing argument of Kühn and Osthus (2003) and Diestel and Rempel (2005). In this paper, we argue that the latter approach is particularly well suited for studying edge variants of the Erdős-Pósa theorem. As an illustration, we give a short proof of a theorem of Bruhn, Heinlein, and Joos (2019), that cycles of length at least $\ell$ have the so-called edge-Erdős-Pósa property. More precisely, we show that every graph $G$ either contains $k$ edge-disjoint cycles of length at least $\ell$ or an edge set $F$ of size $O(k\ell \cdot \log (k\ell ))$ such that $G-F$ has no cycle of length at least $\ell$. For fixed $\ell$, this improves on the previously best known bound of $O(k^2\log k+k\ell )$.

v4: Minor change v3: Referees' comments implemented v2: Additional references to prior works