The Erdős-Pósa property for prime-length cycles fails (and beyond)

Abstract

We prove that for every $t\in \mathbb{N}$, prime-length cycles do not have the $\frac{1}{t}$-integral Erdős-Pósa property, even when restricted to planar graphs. We in fact prove a more general density result. For every $t\in \mathbb{N}$ and every subset $L\subseteq \mathbb{N}$ with lower density zero, the set of cycles whose length is in $L$ do not have the $\frac{1}{t}$-integral Erdős-Pósa property, even when restricted to planar graphs. We also consider a less restrictive density condition on $L$, called porous, where the complement of $L$ contains arbitrarily long sequences of consecutive integers. We prove that for every porous set $L\subseteq \mathbb{N}$, the set of cycles whose length is in $L$ do not have the Erdős-Pósa property, even when restricted to projective planar graphs. Our results partially answer a question of Gollin, Hendrey, Kwon, Oum, and Yoo [Math. Ann., 393(2):2507-2559, 2025].

6 pages, 1 figure