Recognition: unknown
The ErdH{o}s-P\'osa property for prime-length cycles fails (and beyond)
Pith reviewed 2026-05-08 16:58 UTC · model grok-4.3
The pith
Prime-length cycles do not have the 1/t-integral Erdős-Pósa property for any natural number t, even in planar graphs.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
For every natural number t and every subset L of the natural numbers whose lower density is zero, the cycles whose lengths belong to L do not possess the 1/t-integral Erdős-Pósa property, even when restricted to planar graphs. Separately, when L is merely porous, the same cycles fail the classical Erdős-Pósa property in projective planar graphs.
What carries the argument
Explicit constructions of planar (or projective planar) graphs that contain many vertex-disjoint cycles of lengths drawn from the sparse set L while keeping the minimum hitting-set size large relative to the packing number.
If this is right
- Any cycle-length family that has the 1/t-integral Erdős-Pósa property in the plane must have positive lower density.
- The ordinary Erdős-Pósa property imposes the stricter requirement that the complement of the length set cannot contain arbitrarily long consecutive blocks.
- Prime cycles are a concrete zero-density example that fails all integral versions of the property.
- The same density obstructions apply inside any minor-closed class that contains all planar graphs.
- Questions about sufficiency of positive density or about non-minor-closed host classes remain open but must respect these lower bounds.
Where Pith is reading between the lines
- The arithmetic sparseness of allowed lengths is the decisive obstruction rather than planarity itself.
- It is natural to ask whether every positive lower-density set of lengths recovers the integral Erdős-Pósa property inside planar graphs.
- Similar counterexamples may exist on higher-genus surfaces or in other minor-closed families once the density condition is met.
- Algorithmic consequences include the impossibility of constant-factor approximations for hitting sparse cycle families in planar graphs via the duality gap.
Load-bearing premise
It is possible to embed arbitrarily many cycles of lengths from a zero-density set L inside a single planar graph without creating short hitting sets for those cycles.
What would settle it
An explicit planar graph together with a constant c such that every set of more than c vertex-disjoint prime-length cycles can be hit by at most c vertices.
read the original abstract
We prove that for every $t \in \mathbb{N}$, prime-length cycles do not have the $\frac{1}{t}$-integral Erd\H{o}s-P\'osa 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\H{o}s-P\'osa 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\H{o}s-P\'osa 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].
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proves that for every natural number t, the family of prime-length cycles does not have the 1/t-integral Erdős-Pósa property, even when restricted to planar graphs. It establishes a more general result: for any subset L of natural numbers with lower density zero, cycles whose lengths lie in L fail to have the 1/t-integral Erdős-Pósa property in planar graphs. Additionally, for any porous set L (where the complement contains arbitrarily long consecutive integers), the standard (non-integral) Erdős-Pósa property fails for L-cycles even in projective planar graphs. These results partially answer a question of Gollin, Hendrey, Kwon, Oum, and Yoo.
Significance. If the explicit constructions are correct and preserve the required planarity or projective planarity, the result is significant for the study of Erdős-Pósa properties. It supplies concrete counterexamples showing that sparsity conditions on cycle lengths (lower density zero or porosity) suffice to destroy both integral and non-integral packing-covering relations in planar and near-planar graphs. The generalization beyond primes and the restriction to planar graphs strengthen the negative answer to the cited open question; the constructions themselves may serve as useful test cases for related conjectures.
major comments (1)
- Construction of the counterexample graphs (detailed after the statement of the main theorems): the argument that the graphs remain planar (or projective planar) while containing arbitrarily many vertex-disjoint L-cycles whose lengths realize the zero-density set L must be made fully explicit. The lower-density-zero condition alone does not automatically guarantee an embedding; an explicit minor-exclusion argument or inductive embedding construction is needed to confirm that the maximum number of vertex-disjoint L-cycles stays bounded while the minimum vertex cover grows faster than any constant multiple of the fractional packing number.
minor comments (3)
- Notation for the integral Erdős-Pósa property (Definition 2.3): clarify whether the 1/t-integral version is defined via t-integral packings or via the standard fractional packing scaled by 1/t; the current wording leaves the precise integrality gap ambiguous.
- Figure 1 (or the illustrative example for a porous set): the drawing does not clearly indicate the projective-planar embedding; adding a few crossing labels or a separate projective-plane diagram would improve readability.
- Reference list: the citation to Gollin et al. (Math. Ann. 2025) should include the full title and page range for consistency with other references.
Simulated Author's Rebuttal
We thank the referee for the careful reading of our manuscript and for the positive evaluation of its significance. We address the single major comment below and will incorporate the suggested clarifications in a revised version.
read point-by-point responses
-
Referee: Construction of the counterexample graphs (detailed after the statement of the main theorems): the argument that the graphs remain planar (or projective planar) while containing arbitrarily many vertex-disjoint L-cycles whose lengths realize the zero-density set L must be made fully explicit. The lower-density-zero condition alone does not automatically guarantee an embedding; an explicit minor-exclusion argument or inductive embedding construction is needed to confirm that the maximum number of vertex-disjoint L-cycles stays bounded while the minimum vertex cover grows faster than any constant multiple of the fractional packing number.
Authors: We agree that a more explicit verification of planarity (and projective planarity) is warranted. The current manuscript presents the graphs via an explicit recursive construction starting from a planar grid and successively attaching paths of prescribed lengths from L at designated boundary vertices, but the embedding argument is only sketched. In the revision we will add a self-contained inductive proof that each graph in the family admits a planar embedding: at each step the new paths are routed along the outer face without introducing crossings, using the fact that the attachment points lie on a single facial cycle. The same construction, with an additional cross-cap, yields the projective-planar examples for porous sets. We will also include a direct computation showing that the maximum number of vertex-disjoint L-cycles is unbounded while the minimum vertex cover is at least t times larger than any fixed multiple of the fractional packing number, thereby confirming the failure of the 1/t-integral Erdős-Pósa property. These additions will not alter the statements or proofs of the main theorems. revision: yes
Circularity Check
Explicit counterexample constructions yield non-circular non-existence proof
full rationale
The paper establishes non-existence of the 1/t-integral Erdős-Pósa property for cycles of lengths in any lower-density-zero set L (including primes) by exhibiting explicit families of planar graphs. These constructions directly realize bounded packing number while the covering number grows arbitrarily, without any fitted parameters, self-referential definitions, or load-bearing self-citations that reduce the central claim to prior inputs. The cited prior work (Gollin et al.) merely poses the open question being answered; the new result supplies independent, falsifiable counterexamples whose planarity is part of the explicit construction rather than an imported uniqueness theorem or ansatz. No equation or derivation step collapses to a renaming or statistical forcing of the target statement.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math Standard definitions of graphs, cycles, planarity, projective planarity, and the (integral) Erdős-Pósa property.
- standard math The mathematical definition of lower density zero and porosity for subsets of natural numbers.
Reference graph
Works this paper leans on
-
[1]
Etienne Birmel\' e , J. Adrian Bondy, and Bruce A. Reed. The E rdős- P ósa property for long circuits. Combinatorica , 27(2):135--145, 2007. https://doi.org/10.1007/s00493-007-0047-0 doi:10.1007/s00493-007-0047-0
-
[2]
Frames, A -paths, and the E rdős- P ósa property
Henning Bruhn, Matthias Heinlein, and Felix Joos. Frames, A -paths, and the E rdős- P ósa property. SIAM Journal on Discrete Mathematics , 32(2):1246--1260, January 2018. https://doi.org/10.1137/17M1148542 doi:10.1137/17M1148542
-
[3]
E rdős- P ósa from ball packing
Wouter Cames van Batenburg, Gwena\" e l Joret, and Arthur Ulmer. E rdős- P ósa from ball packing. SIAM J. Discrete Math. , 34(3):1609--1619, 2020. https://doi.org/10.1137/19M1309225 doi:10.1137/19M1309225
-
[4]
Recherches analytiques sur la th \'e orie des nombres premiers
Charles-Jean de la Vall \'e e Poussin. Recherches analytiques sur la th \'e orie des nombres premiers. Annales de la Soci \'e t \'e Scientifique de Bruxelles , 20:183--256, 281--362, 363--397, 1896. Also published as a book by Hayez, Bruxelles, 1897
-
[5]
On Independent Circuits Contained in a Graph
Paul Erd o s and Lajos P \'o sa. On Independent Circuits Contained in a Graph . Canadian Journal of Mathematics , 17:347--352, 1965. https://doi.org/10.4153/CJM-1965-035-8 doi:10.4153/CJM-1965-035-8
-
[6]
Pascal Gollin, Kevin Hendrey, O-joung Kwon, Sang-il Oum, and Youngho Yoo
J. Pascal Gollin, Kevin Hendrey, O-joung Kwon, Sang-il Oum, and Youngho Yoo. A unified Erd o s-P \'o sa theorem for cycles in graphs labelled by multiple abelian groups. Math. Ann. , 393(2):2507--2559, 2025. https://doi.org/10.1007/s00208-025-03293-5 doi:10.1007/s00208-025-03293-5
-
[7]
Packing Even Directed Circuits Quarter-Integrally
Maximilian Gorsky, Ken-ichi Kawarabayashi, Stephan Kreutzer, and Sebastian Wiederrecht. Packing Even Directed Circuits Quarter-Integrally . In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 692--703, Vancouver BC Canada, June 2024. ACM. https://doi.org/10.1145/3618260.3649682 doi:10.1145/3618260.3649682
-
[8]
The Structure of (Even) Directed Cycles
Maximilian Gorsky. The Structure of (Even) Directed Cycles . PhD thesis, Technische Universit \"a t Berlin, September 2024. URL: https://doi.org/10.14279/depositonce-21276
-
[9]
Sur la distribution des z \'e ros de la fonction (s) et ses cons \'e quences arithm \'e tiques
Jacques Hadamard. Sur la distribution des z \'e ros de la fonction (s) et ses cons \'e quences arithm \'e tiques. Bulletin de la Soci \'e t \'e Math \'e matique de France , 24:199--220, 1896. URL: http://www.numdam.org/item/BSMF_1896__24__199_1
-
[10]
A half-integral Erd os-P\'osa theorem for directed odd cycles
Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon, and Qiqin Xie. A half-integral Erd os-P\'osa theorem for directed odd cycles. Journal of Combinatorial Theory, Series B , 172:115--145, May 2025. https://doi.org/10.1016/j.jctb.2024.12.008 doi:10.1016/j.jctb.2024.12.008
-
[11]
F. Mousset, A. Noever, N. S kori\' c , and F. Weissenberger. A tight E rdős- P ósa function for long cycles. J. Combin. Theory Ser. B , 125:21--32, 2017. https://doi.org/10.1016/j.jctb.2017.01.004 doi:10.1016/j.jctb.2017.01.004
-
[12]
Bruce A Reed. Mangoes and Blueberries . Combinatorica , 19(2):267--296, February 1999. https://doi.org/10.1007/s004930050056 doi:10.1007/s004930050056
-
[13]
Recent techniques and results on the Erd o s -- P \'o sa property
Jean-Florent Raymond and Dimitrios M Thilikos. Recent techniques and results on the Erd o s -- P \'o sa property. Discrete Applied Mathematics , 231:25--43, November 2017. https://doi.org/10.1016/j.dam.2016.12.025 doi:10.1016/j.dam.2016.12.025
-
[14]
On the presence of disjoint subgraphs of a specified type
Carsten Thomassen. On the presence of disjoint subgraphs of a specified type. Journal of Graph Theory , 12(1):101--111, March 1988. https://doi.org/10.1002/jgt.3190120111 doi:10.1002/jgt.3190120111
-
[15]
A conjecture on triangles of graphs
Zsolt Tuza. A conjecture on triangles of graphs. Graphs Combin. , 6(4):373--380, 1990. https://doi.org/10.1007/BF01787705 doi:10.1007/BF01787705
-
[16]
Packing cycles in undirected group-labelled graphs
Robin Thomas and Youngho Yoo. Packing cycles in undirected group-labelled graphs. Journal of Combinatorial Theory, Series B , 161:228--267, July 2023. https://doi.org/10.1016/j.jctb.2023.02.011 doi:10.1016/j.jctb.2023.02.011
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.