The Erdős-Pósa property for prime-length cycles fails (and beyond)
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.04938
curl -X POST /api/v1/records/arxiv/2605.04938/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.04938/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'