{"id":"a4e6fe88-c5a6-4511-9995-7741c04b8bb6","arxiv_id":"2607.06869","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Every graph contains k vertex-disjoint cycles of distinct lengths or has a set of O(k^6 polylog(k)) vertices whose removal leaves at most k-1 cycle lengths.","lead":"The paper proves that every graph either contains k vertex-disjoint cycles all of different lengths, or has a small set of vertices whose removal leaves at most k-1 distinct cycle lengths. This is a new variant of the classic Erdős-Pósa theorem, adapted to cycles that must differ in length rather than just exist.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"No significant objection identified. Lemma 2.4's weight argument on prism symmetric differences checks out under careful verification.","rationale":"The paper's central claim (Theorem 1.3) rests on two pillars: the bounded-treewidth case (Lemma 2.2, via the subtree coloring Lemma 2.1) and the high-treewidth case (Corollary 2.6, via Lemma 2.4 and Theorems 2.3/2.5). Both pillars are verified as correct. Lemma 2.1 is a clean induction on trees. Lemma 2.4's weight argument, while compact, is verified by explicit calculation of the symmetric difference weights and the sign-switching trick between C1 and C2. The SDR step in Corollary 2.6 is justified by Hall's theorem. The lower bounds correctly establish tightness of g(k)=k−1 and necessity of f(k)∈Ω(k log k). The additive combinatorics construction (Section 5) provides a genuine barrier to improvement via ladders. The surface embedding result (Theorem 1.4) follows from a correct application of local treewidth bounds to radial graphs. All external dependencies (Birmelé-Bondy-Reed, Chekuri-Chuzhoy, Eppstein, Visser-Bodlaender, Korhonen-Lokshtanov) are well-established independent results. The gap between O(k^6 polylog(k)) and the conjectured O(k log k) is transparently acknowledged and supported by Theorem 1.5. No circularity, no internal inconsistency, no unsupported claims. The reader's verdict of ACCEPT at HIGH confidence is appropriate.","tokens_in":23423,"tokens_out":3700,"duration_ms":109518,"concrete_test":"Independently verify Lemma 2.4 by brute force: for small k (e.g., k=3,4,5), enumerate all possible positive integer weight assignments w:E(H)→[1,W] on the 6k-prism H for small W (e.g., W≤5), compute |Λ(G)| for each subdivision G, and confirm that |Λ(G)|≥k in every case. If any counterexample is found, the lemma fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader correctly identifies Lemma 2.4 as the most non-trivial combinatorial step. I traced through the proof carefully. The 6k-prism has cycles C1 (top), C2 (bottom), and 4-cycles Ci for i∈[3k] using vertices a_{2i-1}, a_{2i}, b_{2i}, b_{2i-1}. The partition into I+, I-, I0 by sign of w(C1△Ci)−w(C1) is sound. For |I+|≥k (or |I−|≥k), nested subsets A1⊂...⊂Ak give strictly monotone weights since each detour has the same sign, yielding k distinct cycle weights. For the |I0|≥k case, the key claim is w(C2△Ci)−w(C2)>0 when w(C1△Ci)−w(C1)=0. This follows because the zero condition gives w(a_{2i-1}a_{2i}) = w(a_{2i-1}b_{2i-1})+w(b_{2i-1}b_{2i})+w(b_{2i}a_{2i}), and substituting into w(C2△Ci)−w(C2) yields a sum of four positive edge-weights. The Ci's are vertex-disjoint for distinct i, so symmetric differences with multiple Ci's are valid cycles with additive weight changes. The SDR argument in Corollary 2.6 (each Gi has ≥k distinct lengths, so Hall's condition holds for selecting k distinct representatives across k subgraphs) is also correct. The lower bounds (Theorems 3.1, 3.2) and the additive combinatorics barrier (Theorem 1.5) are sound. I find no significant concern with the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"glm-5.2","summary":"The paper proves an Erdős-Pósa-type theorem for vertex-disjoint cycles of distinct lengths: for every k, every graph G either contains k vertex-disjoint cycles of pairwise different lengths, or admits a hitting set X of size O(k^6 polylog(k)) such that G−X has at most k−1 cycle lengths (Theorem 1.3). An analogous result for coloured faces of embedded graphs is also proved (Theorem 1.4), and a construction from additive combinatorics shows that subdivided ladders can have surprisingly small cycle spectra (Theorem 1.5), suggesting barriers to improving the main bound. The proof of the main theorem proceeds via a clean modular chain: a coloured-subtree lemma (Lemma 2.1) handles bounded-treewidth graphs; a prism cycle-length lemma (Lemma 2.4) combined with the Chekuri-Chuzhoy high-treewidth partition theorem handles the high-treewidth case. Lower bounds (Theorems 3.1, 3.2) show that both the k−1 bound on remaining cycle lengths and an Ω(k log k) lower bound on the hitting set size are best possible.","tokens_in":24137,"tokens_out":886,"duration_ms":188822,"significance":"This is a significant contribution to the Erdős-Pósa literature. The problem of packing cycles of distinct lengths does not fit into the standard packing-covering hypergraph framework, making the dual certificate (bounding the cycle spectrum after deletion) a novel conceptual contribution. The proof is modular and relies on well-established external results (Birmelé-Bondy-Reed, Chekuri-Chuzhoy, Eppstein, Hennecart-Robert-Yudin) without circularity. The lower bound construction using additive combinatorics (Theorem 1.5) is a notable feature: it provides a concrete barrier showing that the prism-based approach cannot be straightforwardly improved via ladders, and it identifies a genuine obstruction. The algorithmic versions (Appendices A, B) add practical value. The surface embedding result (Theorem 1.4) extends the framework to a natural topological setting with a clean proof via radial graphs and local treewidth.","major_comments":[],"minor_comments":[{"comment":"The abstract states the hitting set bound as O(k^2 d g) while Theorem 1.4 states O(k^2 d(g+1)). These should be made consistent; the (g+1) form is more precise for g=0.","section":null},{"comment":"In the proof of Lemma 2.4, the notation w(C1△Ci) is introduced without explicitly defining the symmetric difference of cycles as an edge set. A brief clarifying sentence would help the reader.","section":null},{"comment":"Theorem 5.5 introduces the constant D = C/(1+C) < 0.4403, but the value of C is defined earlier in Section 5 as log 2 / log(1+√2) < 0.7865. A forward reference or restatement would improve readability.","section":null},{"comment":"The reference [CM26] (Chudnovsky and Maier) is cited as a 2026 arXiv preprint; the authors should verify and update this reference if a published version is available.","section":null},{"comment":"In Theorem 1.3, the algorithmic runtime O(18^{k^5} poly(k) |V(G)|^7) is stated but the derivation is deferred to Appendix A. A brief forward pointer in the main text would be helpful.","section":null},{"comment":"Conjecture 6.1 proposes an optimal bound of O(k log k), which is a natural and important target. This conjecture is currently somewhat buried at the end of Section 6; the authors might consider highlighting it more prominently.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The paper is well-written and the proofs are correct as far as I can verify. The key combinatorial lemma (Lemma 2.4) is short but non-trivial; I traced through the symmetric-difference weight argument and it is sound. The lower bound construction (Theorem 1.5) is a nice application of additive combinatorics and provides a genuine barrier to improvement. I recommend minor revision for presentation issues only."},"author_rebuttal":null,"desk_editor":{"model":"glm-5.2","letter":"The paper proves the first Erdős-Pósa-type theorem for packing vertex-disjoint cycles of distinct lengths. The main result (Theorem 1.3): every graph either contains k vertex-disjoint cycles of different lengths, or has a hitting set of size O(k^6 polylog(k)) leaving at most k−1 cycle lengths. This is genuinely new — the distinct-length constraint doesn't fit the standard hypergraph packing-covering framework, and the authors are explicit about that. They also prove a surface-embedded analogue (Theorem 1.4) and construct lower bounds via additive combinatorics (Theorem 1.5) showing that subdivided ladders can have surprisingly few cycle lengths, which is a real barrier to improving the bounds via prism/ladder arguments alone. The lower bounds in Section 3 are clean: g(k) = k−1 is tight, and f(k) ∈ Ω(k log k) is necessary. The proof structure is modular and easy to follow. Lemma 2.1 (coloured subtrees on tree-decompositions) feeds Lemma 2.2 (bounded treewidth case). The high-treewidth case goes through Birmelé-Bondy-Reed's prism theorem and Lemma 2.4, which shows every subdivision of the 6k-prism has at least k distinct cycle lengths. I checked Lemma 2.4 carefully — the symmetric-difference weight argument and the I+/I−/I0 case split are correct. The zero case is the subtle part: w(C1△Ci)−w(C1) = 0 implies w(C2△Ci)−w(C2) > 0, which follows from substituting the zero condition into the C2 expression and getting a sum of positive edge-weights. The SDR argument in Corollary 2.6 is also sound. The gap between O(k^6 polylog(k)) and the conjectured O(k log k) is large, but the paper is transparent about it and provides evidence that closing it requires genuinely new ideas. The additive combinatorics construction is a nice touch — it refutes the natural approach of replacing prisms with ladders. The surface embedding result (Theorem 1.4) feels somewhat secondary but is a natural extension using Eppstein's local treewidth bounds. The algorithmic aspects (Appendices A and B) are competent but not the main attraction. No circularity concerns — all key external results (Chekuri-Chuzhoy, Birmelé-Bondy-Reed, Eppstein, Hennecart-Robert-Yudin) are by independent authors. This is for graph structure theorists and anyone working on Erdős-Pósa-type problems. It deserves a serious referee. The main theorem is correct and the problem is natural; the bounds are far from tight but the paper knows this and explains why.","headline":"First Erdős-Pósa theorem for cycles of distinct lengths; clean modular proof, honest about the gap between O(k^6 polylog(k)) and the conjectured O(k log k).","tokens_in":24530,"tokens_out":672,"would_cite":true,"duration_ms":176204,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"glm-5.2","headline":"Find k disjoint cycles of distinct lengths or delete O(k^6) vertices","keywords":["Erdős-Pósa theorem","cycle spectrum","vertex-disjoint cycles","treewidth","prism","graph minors","surface embedding","additive combinatorics"],"falsifier":"Construct a subdivision of the 6k-prism with fewer than k distinct cycle lengths, which would refute Lemma 2.4 and break the proof of Corollary 2.6 and hence the main theorem. The authors' lower bound construction (Theorem 1.5) shows that ladders can have few cycle lengths, but prisms have more structure (two base cycles connected by rungs), and the lemma exploits this.","tokens_in":23645,"feed_emoji":"🔄","tokens_out":1359,"duration_ms":206266,"temperature":0.7,"pith_summary":"The paper proves an Erdős-Pósa-type theorem for cycles of distinct lengths. The classic Erdős-Pósa theorem says that every graph either contains k vertex-disjoint cycles or has a small set of vertices whose removal kills all cycles. Here the requirement is stronger: the k cycles must all have different lengths. The authors show that every graph either contains k vertex-disjoint cycles of pairwise distinct lengths, or there is a set of O(k^6 polylog(k)) vertices whose removal leaves a graph with at most k-1 different cycle lengths. The proof splits into two regimes. For graphs of low treewidth, a combinatorial lemma on tree-decompositions provides the packing or the hitting set. For graphs of high treewidth, the authors use the fact that high treewidth forces a subdivision of a large prism (a cylinder-like graph), and they prove that every subdivision of a 6k-prism contains at least k distinct cycle lengths via a weight argument on symmetric differences of cycles. A high-treewidth partition theorem then yields k disjoint subgraphs each contributing distinct lengths. The paper also proves an analogous result for coloured faces of graphs embedded on surfaces, and constructs lower bounds using additive combinatorics showing that subdivided ladders can have surprisingly few cycle lengths.","feed_headline":"Find k disjoint cycles of distinct lengths or delete O(k^6) vertices","feed_subtitle":"An Erdős-Pósa-type theorem shows every graph either packs k cycles of different lengths or has a small hitting set shrinking its cycle count","key_machinery":"The proof combines three ingredients: (1) a tree-decomposition lemma (Lemma 2.1) showing that coloured subtrees of a tree either contain k disjoint members of distinct colours or admit a hitting set of size k-1; (2) the prism subdivision lemma (Lemma 2.4), which uses a weight argument on symmetric differences of cycles in the 6k-prism to guarantee k distinct cycle lengths; and (3) the Chekuri-Chuzhoy high-treewidth partition theorem, which decomposes a high-treewidth graph into k disjoint subgraphs each of treewidth Ω(k^2), each containing a subdivided 6k-prism. The lower bound construction uses a result of Hennecart-Robert-Yudin from additive combinatorics about sets whose sumset is much sm","core_discovery":"The central discovery is that the Erdős-Pósa duality between packing and covering extends to the setting where cycles must have distinct lengths, with the cycle spectrum Λ(G) (the set of all cycle lengths appearing in G) serving as the covering certificate. The key mechanism is Lemma 2.4: every subdivision of the 6k-prism contains at least k distinct cycle lengths. The proof partitions the 3k square cycles of the prism into three classes based on whether their symmetric difference with one of the two base cycles has positive, negative, or zero weight differential. A pigeonhole argument guarantees one class has size at least k, and within that class, nested symmetric differences produce a mon","pith_inferences":["The fact that the problem does not reduce to a standard hypergraph packing-covering problem (as the authors note) suggests that the cycle spectrum serves as a genuinely new type of dual certificate, and the framework might extend to other packing problems where the objects to be packed are constrained by a global property like distinctness.","The gap between the current O(k^6 polylog(k)) bound and the conjectured O(k log k) is substantial. The bottleneck is the high-treewidth regime and the use of the 6k-prism. A subgraph certificate that guarantees k distinct cycle lengths at lower treewidth than Ω(k^2) would directly improve the bound.","The additive combinatorics construction showing that sumset-difference set gaps produce ladders with few cycle lengths hints at a deeper connection between additive structure in graphs and cycle length diversity, which could be a productive direction for related extremal questions."],"forward_implications":["The theorem provides a structural certificate for graphs lacking many vertex-disjoint cycles of distinct lengths: the cycle spectrum of the remaining graph is small, which is a different kind of dual certificate than the usual forest condition in the classic Erdős-Pósa theorem.","The lower bound construction using additive combinatorics (Theorem 1.5) shows that subdivided ladders can have as few as k^α cycle lengths for α ≈ 0.79, which means the prism-based approach cannot be directly improved to give better bounds without fundamentally different subgraph certificates.","The surface embedding result (Theorem 1.4) extends the packing-covering duality to coloured faces at prescribed distances, with bounds depending polynomially on the genus, which could find applications in topological graph theory problems involving face packings.","The conjectured optimal bound of O(k log k) for the hitting set size, if true, would simultaneously match the lower bound from the classic Erdős-Pósa theorem and the lower bound on the cycle spectrum, making the result tight in both parameters."],"fun_headline_variants":["Cycles of distinct lengths satisfy Erdős-Pósa duality","Erdős-Pósa theorem extends to cycles of different lengths","Pack k distinct-length cycles or hit them with O(k^6) vertices","Distinct cycle lengths obey packing-covering duality","Every graph packs k different-length cycles or has small hitting set"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The load-bearing lemma is that every subdivision of the 6k-prism contains at least k distinct cycle lengths. The proof is short and uses a pigeonhole argument on the signs of weight differentials of symmetric differences between square cycles and a base cycle. If this lemma failed, the high-treewidth case of the main theorem would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Cycles of distinct lengths satisfy Erdős-Pósa duality","Erdős-Pósa theorem extends to cycles of different lengths","Pack k distinct-length cycles or hit them with O(k^6) vertices","Distinct cycle lengths obey packing-covering duality","Every graph packs k different-length cycles or has small hitting set","Cycle spectrum as covering certificate in Erdős-Pósa duality","Find k disjoint cycles of different sizes or remove few vertices","Erdős-Pósa duality holds for cycles with distinct lengths","Distinct-length cycles admit polynomial Erdős-Pósa bounds","Either k disjoint distinct-length cycles or a small vertex deletion","Erdős-Pósa for cycle spectra: pack or cover distinct lengths","Graphs either pack k different-length cycles or nearly lose them all"]},"model":"glm-5.2","effort":"low","cost_usd":0.0,"raw_usage":{"total_tokens":1461,"prompt_tokens":675,"completion_tokens":786,"prompt_tokens_details":null},"tokens_in":675,"tokens_out":786,"duration_ms":36035,"temperature":1.0,"reasoning_tokens":583,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-09T23:49:34.089791+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"Construct a subdivision of the 6k-prism with fewer than k distinct cycle lengths, which would refute Lemma 2.4 and break the proof of Corollary 2.6 and hence the main theorem. The authors' lower bound construction (Theorem 1.5) shows that ladders can have few cycle lengths, but prisms have more structure (two base cycles connected by rungs), and the lemma exploits this.","supporting_citations":[],"review_version":1}