{"id":"3555caa1-da26-4f95-8349-8c0e15548554","arxiv_id":"2511.03085","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every odd k and n≥2k-3, the extremal number of edges without a (0 mod k)-cycle is exactly (k-1)(n-k+1).","lead":"This paper proves that 2-connected graphs with sufficiently large minimum degree contain k cycles whose lengths form an arithmetic progression, and determines the maximum number of edges in an n-vertex graph with no cycle whose length is a multiple of any odd integer k. The extremal result closes a long-standing Turán-type problem for cycles modulo k.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Unproven finite assertion in Lemma 3.11 — that every proper hypo-Petersen graph has cycles of lengths 5 through 9 — is load-bearing for the k=5 case of Theorem 1.10 but is only justified by a figure reference.","rationale":"The reader's weakest-assumption analysis identifies the same load-bearing concern: Lemma 3.11 relies on an unverified finite assertion about proper hypo-Petersen graphs. I agree that this is the single most serious gap. The proof of Theorem 1.10 for odd k uses Theorem 1.4, which for k=5 depends on Theorem 1.3, which for k∈{4,5} depends on Lemma 3.11. Thus a false or unproven finite check would undermine the main new extremal result. The paper's other potential issue, the application of Theorem 1.4 in the proof of Theorem 1.10 for k=3 (where Theorem 1.4 is not stated), is a minor and easily fixable slip, since a 0 mod 3 cycle for 2-connected min-degree-3 graphs is already provided by Theorem 4.6(1). The hypo-Petersen check, by contrast, is not easily replaced by an existing theorem; it is a concrete omitted proof. The rest of the argument is detailed and appears coherent, and the paper is honest about the overlap with [16], so a conditional accept with a request to supply the finite verification is the appropriate disposition. The proposed concrete test — brute-force cycle enumeration of all proper hypo-Petersen graphs — would settle the concern definitively.","tokens_in":36471,"tokens_out":25384,"duration_ms":206341,"concrete_test":"Enumerate all graphs arising from the construction H=G[{x_i,y_i,z_i}] with edges x_i y_i, y_i z_{i+2}, z_{i+2} x_{i+2} (indices modulo 5), allowing y_i = z_i, and filter out the 10-vertex Petersen graph. For each such graph, compute all cycle lengths and verify that 5, 6, 7, 8, and 9 all occur. The graphs have at most 15 vertices, so a brute-force cycle enumeration is trivial. If any proper hypo-Petersen graph lacks one of these lengths, Lemma 3.11 is false; if all pass, the gap can be closed by a case table or a short computational appendix.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The weakest point is Lemma 3.11's assertion: 'every proper hypo-Petersen graph contains cycles of consecutive lengths from 5 to 9, see Figure 4.' This is a finite graph-theoretic check, but it is asserted without proof, without a reference, and without enough detail in the text to verify. The contradiction that finishes Lemma 3.11 — and hence Theorem 1.3 for k∈{4,5} — depends on H being a proper hypo-Petersen graph and therefore containing a 5-cycle, 6-cycle, 7-cycle, 8-cycle, and 9-cycle. Claim 2.3 only rules out H being the Petersen graph; it does not establish the cycle-length property. Since Theorem 1.3 for k=5 feeds directly into Theorem 1.4 (k odd) and then into Theorem 1.10 for odd k=5, a failure of this check would invalidate the central extremal result for k=5. The nearby ad-hoc verification in Claim 2.2 at least lists five explicit cycles in the text; the hypo-Petersen statement gives only a figure. This is a genuine gap, not a matter of disagreement with the literature.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves stability versions of theorems of Gao–Huo–Liu–Ma on cycle lengths in graphs of given minimum degree. For a 2-connected graph with minimum degree at least k≥4, it shows (Theorem 1.3) that the graph contains k admissible cycles unless it is K_{k+1} or K_{k,n-k}; (Theorem 1.4) that it contains cycles of all even lengths modulo k under the same exceptions; and (Theorem 1.7) a non-bipartite version covering all residues, with the Petersen graph as the only extra exception for k=3. It also proves Theorem 1.6 for even k with minimum degree k−1. The main extremal application is Theorem 1.10: every n-vertex graph with more than (k−1)(n−k+1) edges contains a (0 mod k)-cycle, for k≥3 and n≥2k−3. This yields the corollary ex(n,C_{0 mod k})=(k−1)(n−k+1) for every odd k, matching the lower bound given by K_{k−1,n−k+1}. The proofs are built from established theorems on admissible paths and cycles, a connectivity lemma, and a detailed induction, with a substantial case analysis for the exceptional small cases k=4,5.","tokens_in":36766,"tokens_out":7152,"duration_ms":62660,"significance":"If the proof is correct, the paper resolves the extremal number for (0 mod k)-cycles for all odd k, a problem with a long history going back to Burr and Erdős. Theorem 1.10 is the first general determination of this extremal number beyond small k. The paper is well structured, gives explicit extremal constructions, and uses a mix of classical results (Woodall, Bondy, Gao–Huo–Liu–Ma, etc.) and original arguments. It also transparently acknowledges the overlap of Lemma 5.4 with a recent result of Lin–Wang–Zhou. The main caveat is that one finite, load-bearing assertion in Lemma 3.11 is left unproved, with only a figure reference. This is a gap that needs to be closed before the central claims can be fully accepted, but it appears to be fixable within the scope of the manuscript.","major_comments":[{"comment":"The assertion 'every proper hypo-Petersen graph contains cycles of consecutive lengths from 5 to 9, see Figure 4' is load-bearing but is not proved. It is used to finish the contradiction in Lemma 3.11 after H=G[{x_i,y_i,z_i}] is shown to be a proper hypo-Petersen graph, and this underpins Theorem 1.3 for k∈{4,5}. Since Theorem 1.4 is deduced from Theorem 1.3, the k=5 case of Theorem 1.10 also depends on it. Claim 2.3 only rules out the Petersen graph; it does not establish any cycle-length property of the other graphs in Figure 3. The reference to Figure 4 is not a proof, and Figure 4 appears to depict a single representative rather than all proper hypo-Petersen graphs. Please provide a complete, machine-checkable verification—for instance an explicit cycle list for each graph in Figure 3—or cite a published result that establishes this cycle spectrum.","section":"Section 3, Lemma 3.11 (after Figure 3)"}],"minor_comments":[{"comment":"The statement 'One can check that the assertion holds for r≤3' is another finite check. Although it is much smaller than the hypo-Petersen check, please expand it or give the explicit resulting path lists, since this lemma is used in the proof of Lemma 3.4.","section":"Lemma 3.1"},{"comment":"The formula for ex(n,C_{2 mod k}) is stated without proof, with the comment that it follows 'by the same arguments' and can also be obtained from [13]. Since this result is not used in the paper, please provide a proof sketch or a precise reference to make the statement self-contained.","section":"Introduction, after Corollary 1.11"},{"comment":"Please include adjacency lists or a compact description of the hypo-Petersen graphs in Figure 3, so that the finite claims about them are reproducible without relying solely on drawings.","section":"Figures 3 and 4"}],"recommendation":"major_revision","confidential_remarks":"The only serious obstacle is the unproved finite assertion in Lemma 3.11. If the authors supply a complete, checkable verification of the hypo-Petersen cycle-length claim (or a published reference), I would support acceptance. The rest of the proof appears sound; I did not find internal inconsistencies, and the main extremal theorem is a significant contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Key point: Theorem 1.10 is the real news — ex(n,C_{0 mod k})=(k-1)(n-k+1) for odd k, a problem open since the 1970s. The stability theorems (1.3, 1.4, 1.6, 1.7) are also substantial, lowering the minimum degree in Gao-Huo-Liu-Ma from k+1 to k with tight exceptions. The paper is honest about overlap: Lemma 5.4 is deducible from Lin-Wang-Zhou, and ex(n,C_{2 mod k}) follows from [13]. That is good practice.\n\nThe proof architecture is coherent: Theorems 1.3 through 1.4 feed into 1.10, and the case analysis is detailed. I read the main chain carefully and saw no circularity. The argument is a serious piece of work.\n\nThe soft spot is exactly the one flagged. In Lemma 3.11, after constructing the hypo-Petersen graph H, the text says 'every proper hypo-Petersen graph contains cycles of consecutive lengths from 5 to 9, see Figure 4.' That sentence is load-bearing: it produces the contradiction that finishes the k=4,5 case, and Theorem 1.3 for k=5 is used for the odd-k case of Theorem 1.10. For k=5, if this fails, the extremal result falls. The paper gives a figure, not a proof or a reference. Finite graph checks are routinely omitted, but this one is central and should be either proven in an appendix or done by a short computer verification with code included. The nearby Claim 2.2 at least lists five explicit cycles; the hypo-Petersen statement deserves the same.\n\nOther than that, the weaknesses are minor: the proofs are long and hard to fully verify, but the building blocks are published theorems. The acknowledgement of [16] is appropriately placed and does not undermine Lemma 5.4's role.\n\nVerdict: send to peer review, but require the authors to fix the hypo-Petersen gap before acceptance. The paper likely advances the field; the gap is a verification issue, not a conceptual one.","headline":"Strong stability and extremal results for mod-k cycles, but a load-bearing finite check in the k=4,5 case is asserted rather than proved.","tokens_in":37341,"tokens_out":2028,"would_cite":true,"duration_ms":20761,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C38"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves a sharp extremal theorem: any graph on n≥2k−3 vertices with more than (k−1)(n−k+1) edges contains a cycle whose length is a multiple of k, and for odd k this bound is exact.","keywords":["cycle lengths","admissible cycles","minimum degree","extremal number","cycles modulo k","Turán number","2-connected graphs","stability"],"falsifier":"Enumerate the finite family of proper hypo-Petersen graphs in Figure 3 and compute their cycle-length sets; if one misses any length from 5 to 9, the proof's Claim 2.3 contradiction disappears. A second, direct check: search for an n-vertex graph with n≥2k−3 and e(G)>(k−1)(n−k+1) that has no 0-mod-k cycle for k=4 or 5.","tokens_in":36368,"feed_emoji":"🔄","tokens_out":7376,"duration_ms":69582,"temperature":0.7,"pith_summary":"This paper establishes a sharp extremal result for cycle lengths modulo k: if a graph on n vertices has more than (k−1)(n−k+1) edges, and n is at least 2k−3, then some cycle has length divisible by k. For odd k this bound is exact, giving the first determination of the extremal number for cycles of length 0 mod k beyond the previously known case k=3. The proof goes through a stability analysis of earlier theorems on cycle lengths in graphs of given minimum degree: under minimum degree k, 2-connectivity already forces k admissible cycles and cycles in every even residue class mod k, with only two exceptional graphs. A parallel result for even k lowers the minimum degree to k−1 when only even residue classes are asked for. The extremal theorem then follows by a short induction that first improves the degree and connectivity, then applies the modulo-cycle theorem.","feed_headline":"Odd k: exact edge limit for no 0-mod-k cycle","feed_subtitle":"Graphs with more than (k−1)(n−k+1) edges must contain a cycle whose length is divisible by k.","key_machinery":"The engine is a pair of lemmas (2.3 and 2.4) that turn the absence of the desired cycle structure into a connectivity guarantee: a 2-connected graph with minimum degree at least k−r that lacks k admissible cycles (or lacks cycles in some even residue class mod k) must be at least (k+2)/2−r connected. With high connectivity in hand, the proof combines the paper's path-concatenation lemmas (2.5 and 2.6) — which glue arithmetic progressions of path lengths across a separator into long progressions of cycle lengths — with known admissible-path theorems. For the hard minimum-degree cases k=4,5, the argument passes through a structural analysis of 5-cycles and the 'hypo-Petersen' family, small gra","core_discovery":"On the paper's own terms, the central discovery is Theorem 1.10: for every integer k≥3 and every graph G on n≥2k−3 vertices, e(G)>(k−1)(n−k+1) forces a cycle of length 0 mod k. As a corollary, for odd k the extremal number is exactly ex(n,C_{0 mod k})=(k−1)(n−k+1) when n≥2k−3, the lower bound coming from the complete bipartite graph K_{k−1,n−k+1}, which avoids 0-mod-k cycles. This is the first time this extremal number is known for a general family of odd moduli; previous exact values covered only k=3 (and k=2,4 separately). The main structural step is a stability strengthening: 2-connected graphs of minimum degree at least k contain k admissible cycles and cycles of every even length modulo","pith_inferences":["Beyond the paper: if Theorem 1.10 is correct, the still-open even-k case of the 0-mod-k extremal constant will need different extremal graphs — the bipartite K_{k−1,n−k+1} that is extremal for odd k contains a 0-mod-k cycle when k is even, and the known k=4 value is already smaller than k−1.","Beyond the paper: the proof's k=4,5 case currently rests on a visual check of the finite hypo-Petersen family; a short computer enumeration of those graphs' cycle lengths would turn that step into a verified finite fact and remove the only non-textual dependency in the chain leading to Theorem 1.10.","Beyond the paper: a natural next question is whether exact formulas for other residue classes, such as cycles of length ℓ mod k with even ℓ, hold at the same thresholds; the present arguments provide a template but do not settle the general case.","Beyond the paper: the threshold n≥2k−3 in Theorem 1.10 stitches together two regimes — for smaller n the extremal problem is the known odd-cycle Turán problem — and a unified formula may be provable by the same induction."],"forward_implications":["For every odd k and every n≥2k−3, the exact maximum number of edges in a graph with no cycle of length divisible by k is (k−1)(n−k+1); the complete bipartite graph K_{k−1,n−k+1} shows the bound cannot be lowered.","The constant c_{0,k} in the linear-edge problem for 0-mod-k cycles equals k−1 for every odd k; before this, exact constants were known only for k≤4.","Theorems 1.3 and 1.4 upgrade earlier minimum-degree conditions from k+1 to k for 2-connected graphs, with only two specified exceptions, so results relying on those earlier theorems now work at one lower degree.","For even k≥4, a 2-connected graph of minimum degree k−1 on at least k+2 vertices already contains cycles of every even length modulo k.","2-connected non-bipartite graphs of minimum degree at least k contain cycles of every residue class modulo k, apart from K_{k+1} and, for k=3, the Petersen graph."],"fun_headline_variants":["Exact edge limit for avoiding 0-mod-k cycles","Odd k: max edges without a cycle length divisible by k","Stability proves exact ex(n, C_{0 mod k}) for odd k","For odd k, n≥2k-3: (k-1)(n-k+1) edges force 0-mod-k","Odd moduli: extremal number for no k-divisible cycle"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The argument that minimum degree 4 or 5 already forces admissible cycles depends on an unproved finite check: every proper hypo-Petersen graph (all drawn in Figure 3) contains cycles of consecutive lengths 5 through 9; if any such graph lacks one of those lengths, Theorem 1.3 fails for k=4 or 5, and Theorem 1.10, which reduces to Theorem 1.4, fails with it.","fun_headline_variants_meta":{"raw":{"variants":["Exact edge limit for avoiding 0-mod-k cycles","Odd k: max edges without a cycle length divisible by k","Stability proves exact ex(n, C_{0 mod k}) for odd k","For odd k, n≥2k-3: (k-1)(n-k+1) edges force 0-mod-k","Odd moduli: extremal number for no k-divisible cycle"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000357,"raw_usage":{"total_tokens":1807,"prompt_tokens":810,"completion_tokens":997,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":554,"completion_tokens_details":{"reasoning_tokens":892}},"tokens_in":554,"tokens_out":997,"duration_ms":9526,"temperature":1.0,"reasoning_tokens":892,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T23:59:59.376287+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate the finite family of proper hypo-Petersen graphs in Figure 3 and compute their cycle-length sets; if one misses any length from 5 to 9, the proof's Claim 2.3 contradiction disappears. A second, direct check: search for an n-vertex graph with n≥2k−3 and e(G)>(k−1)(n−k+1) that has no 0-mod-k cycle for k=4 or 5.","supporting_citations":[],"review_version":1}