{"id":"bc1904dd-93e4-4ea3-a2ff-ed07a208c066","arxiv_id":"2608.06698","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every n-vertex graph with no cycle of length 0 mod 3 or 4 mod 6 has at most (11/8)n - 7/4 edges, and equality occurs exactly for the constructed graphs H_k.","lead":"An extremal graph theory paper finds the exact maximum number of edges in any graph whose cycle lengths avoid 0, 3, and 4 modulo 6. The extremal graphs are completely classified as a repeating block construction.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 6's all-n construction sets k = floor((n-2)/8), which makes r = 8k+2-n negative for n not ≡2 (mod 8); the advertised lower-bound graph H_k - {v1,...,v_r} is undefined for many n.","rationale":"The reader's verdict was CONDITIONAL, and I agree that a correction is needed, but the concrete defect is not the one flagged. I checked the two compressed steps the reader worried about. In Lemma 4.3, the parity classification is exhaustive: each row and column of B has an even number of odd entries, so the odd-position matrix can only be all-zero, two identical nonzero rows, or the complement of a permutation matrix; these are exactly Cases 1-3 up to row/column symmetry, and the arithmetic in each case contradicts equation (3). For the final 'easy to check' step about end(R): if R joins the midpoint z_{2k} to z_1, then for k≥2 the cycle R ∪ P_1[z_1,x] ∪ P_j ∪ P_{2k}[y,z_{2k}] has length 1+2+4+2=9 for any 2≤j≤2k-1, a forbidden 0 mod 3 cycle; the other non-{x,y} antipodal pairs yield similar short forbidden cycles, so that assertion is sound though terse. The genuine load-bearing issue is in Section 6: the floor/ceil slip makes the lower-bound construction undefined for all n not congruent to 2 modulo 8. Since Corollary 1.4 is part of the central claim, the manuscript must correct this; the intended ceil version is a one-line fix and preserves the stated extremal number.","tokens_in":16772,"tokens_out":38946,"duration_ms":339312,"concrete_test":"Recompute the Section 6 construction for n=3,...,9 using the displayed k = floor((n-2)/8): this gives k=0 and r=2-n<0, so the graph H_k - {v1,...,v_r} is undefined. Then repeat with k = ceil((n-2)/8) and symbolically verify that for n=8k+2-r with r=0,...,7, the number of edges of H_k - {v1,...,v_r} is exactly floor(11n/8 - 7/4), using the listed degrees of v1,...,v8 and the induced edges among them.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The proof of Corollary 1.4 in Section 6 defines k = floor((n-2)/8) and r = 8k+2-n, then asserts 0≤r≤7. This is false: for n=3,9,..., k=0 and r=2-n<0, so {v1,...,v_r} is undefined and H_k - {v1,...,v_r} does not exist. The construction is the entire lower bound for the exact extremal number for every n≥2, so Corollary 1.4 and the abstract's 'for every n' claim are not established as written. The intended definition is k = ceil((n-2)/8), equivalently k = floor((n+5)/8), which gives 0≤r≤7. With that correction the edge count checks out for r=0,...,7. The upper-bound and characterization parts of Theorem 1.3 appear unaffected by this typo, but the all-n lower bound needs the fix.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies n-vertex graphs containing no cycle of length divisible by 3 or congruent to 4 modulo 6, i.e., no (0,3,4 mod 6)-cycle. The main theorem states that every such graph satisfies e(G) ≤ (11/8)n − 7/4, with equality if and only if n = 8k+2 and G is isomorphic to an explicitly constructed graph H_k; Corollary 1.4 then asserts the exact extremal number floor((11/8)n − 7/4) for every n ≥ 2. The proof proceeds by showing planarity via exclusion of K_5 and K_{3,3} subdivisions, then uses face-counting, a structural lemma on 8-angulations, and induction on n to derive the bound and the extremal characterization. The paper also gives an all-n construction intended to attain the bound.","tokens_in":16879,"tokens_out":18905,"duration_ms":167127,"significance":"If correct, this is a valuable exact extremal result for simultaneously forbidden residue classes of cycle lengths, with a full characterization of all extremal graphs. The proof is self-contained and uses standard tools (Kuratowski, Euler's formula, Menger-type arguments, Ramsey theory), and the extremal constructions are explicit rather than asymptotic. The paper also demonstrates a genuinely new phenomenon: the coefficient 11/8 is smaller than the leading coefficients obtained by forbidding any two of the three residue classes separately. The main claims are falsifiable and the constructions are explicit, which is a strength.","major_comments":[{"comment":"The definition k = floor((n−2)/8) makes r = 8k+2−n negative for n ≡ 3,4,...,9 (mod 8); for example, n = 3 gives k = 0 and r = −1, so the expression H_k − {v_1,...,v_r} is undefined and the lower-bound construction for every n is not established as written. This is load-bearing because Corollary 1.4 and the abstract's 'for every n ≥ 2' claim depend on it. The intended definition appears to be k = ceil((n−2)/8), equivalently k = floor((n+5)/8), which gives 0 ≤ r ≤ 7 and, as the author states, the claimed edge count. Please correct the formula and verify the edge count for all r = 0,...,7.","section":"Section 6, proof of Corollary 1.4"},{"comment":"The reduction 'By considering the parity of the entries of B together with the symmetry of K_{3,3}, it suffices to examine only the following cases' is asserted rather than demonstrated. Since Proposition 4.1 depends entirely on this lemma, the parity classification should be justified explicitly: after row and column permutations, every 3×3 parity pattern with even row and column sums is indeed one of the three displayed cases, but the argument should be written out or replaced by a short enumeration. As written, a reader cannot fully verify the exhaustiveness of the case analysis.","section":"Lemma 4.3"},{"comment":"The assertion 'If end(R) ≠ {x,y}, then it is easy to check that G contains a (0,3,4 mod 6)-cycle' is the last step in the extremal classification and is not demonstrated. Since this completes the proof that G is isomorphic to H_k, please provide the short case analysis: for each of the three non-{x,y} antipodal pairs of the 8-face P_{2k} ∪ P_1, exhibit an explicit forbidden cycle using the paths Q_i already constructed.","section":"Section 5, final paragraph of proof of Theorem 1.3"}],"minor_comments":[{"comment":"The displayed congruence 'b_sum + T_id = 12 + 2b_{2,2} + 2b_{3,3} + b_{2,3} + b_{3,2} ≡ 12 + 3d ≡ 0' contains an arithmetic slip: the constant 2 from T_id = 2 + d is omitted, and the correct value is 14 + 3d ≡ 2 (mod 6). Since 2 is not in {1,3,4,5} (mod 6), the contradiction with equation (3) is still valid, but the formula should be corrected.","section":"Lemma 4.3, Case 2"},{"comment":"There are several typographical and notational slips in the introduction, e.g., the display comparing ex(k,C_ℓ)/k with c_{ℓ,k} is missing the modulus in the cycle notation, and the intended statement should be about ex(n,C_{ℓ mod k})/n. Please proofread the introduction carefully.","section":"Introduction"},{"comment":"The face counts e(B_1) = 7 and e(B_2) = 11 are used immediately after the definition but are not stated there; adding them to Definition 5.5 would improve readability.","section":"Definition 5.5"}],"recommendation":"major_revision","confidential_remarks":"The paper is promising and the central theorem appears defensible; the main obstruction is the indexing error in Section 6, which is easily corrected, and the need for fuller justification in Lemma 4.3 and the final step of the extremal characterization. I would encourage the editor to seek a revision rather than a rejection, and to ask the author to supply the missing justifications."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe headline: this paper has a real result, but as written it overclaims. The all-n construction in Section 6 has a sign error that makes the lower bound undefined for most n; the fix is one line, so the paper is revisable, but Corollary 1.4 is not established in the current version.\n\nWhat's actually new: exact extremal number and extremal graphs for forbidding (0,3,4 mod 6)-cycles. The coefficient 11/8 sits strictly below any two-residue bound, so the multi-residue phenomenon is real. The proof is self-contained, with no fitted parameters or circular dependencies. The algebraic planarity argument in Lemma 4.3 and the theta_4 classification in Lemma 3.1 are the strongest parts.\n\nSoft spots, in order of severity:\n\n1. Section 6: with k = floor((n-2)/8), the quantity r = 8k+2-n is negative for every n not congruent to 2 mod 8, so G_n = H_k - {v1,...,v_r} is undefined. The intended definition is k = ceil((n-2)/8), which gives 0 <= r <= 7 and makes the edge count work. This is a typo, but it is load-bearing for the abstract's 'for every n' claim.\n\n2. The final step of Theorem 1.3's proof says 'it is easy to check' that if end(R) != {x,y}, then G contains a forbidden cycle. After a long, detailed proof, this is too compressed. It should be expanded.\n\n3. Lemma 4.3 asserts that parity and symmetry reduce the matrix case analysis to three cases. That reduction is actually valid -- the odd entries of B form a graph on K3,3 with all degrees even, so the cases are exhaustive -- but the paper should say this rather than leave it to the reader.\n\nNone of these affect the main upper bound or the equality classification for n = 8k+2, as far as I checked. The induction is long but coherent, and I found no hidden parameters or circular reasoning.\n\nWho should read this: anyone working on extremal problems for cycle lengths modulo k. It deserves a serious referee; the referee should insist on the Section 6 fix and an expanded final step. I would accept it for review, and I would cite the main theorem once the correction is in.\n\nBest.","headline":"Real main theorem, but the all-n construction in Section 6 has a sign error that invalidates Corollary 1.4 as written; the fix is one line, so the paper is revisable.","tokens_in":17505,"tokens_out":17147,"would_cite":true,"duration_ms":148865,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C38","05C10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every n-vertex graph with no cycle of length 0, 3, or 4 modulo 6 has at most (11n − 14)/8 edges, and this bound is sharp.","keywords":["extremal graph theory","forbidden cycle lengths","cycles modulo 6","planar graphs","exact extremal number","theta-4 graphs","edge bounds"],"falsifier":"Enumerate all $3\\times 3$ matrices over $\\mathbb{Z}/6\\mathbb{Z}$ with entries in $\\{1,2,3,5\\}$, even row and column sums, and with $b_{\\mathrm{sum}} + T_\\sigma \\in \\{1,3,4,5\\}$ for every permutation $\\sigma$; Lemma 4.3 claims every such matrix is one of three displayed patterns. If a single matrix outside those patterns exists, it yields a $K_{3,3}$ subdivision with no $(0,3,4 \\bmod 6)$-cycle, refuting the planarity proposition and the bound. Equivalently, exhibit one such subdivision explicitly.","tokens_in":16479,"feed_emoji":"🕸️","tokens_out":16268,"duration_ms":137230,"temperature":0.7,"pith_summary":"This paper establishes the exact maximum number of edges in an $n$-vertex graph that contains no cycle whose length is divisible by $3$ or congruent to $4$ modulo $6$, that is, no cycle of length $0$, $3$, or $4$ modulo $6$. The answer is $\\left\\lfloor \\frac{11}{8}n - \\frac{7}{4} \\right\\rfloor$ edges for every $n \\ge 2$. Equality is achieved only when $n = 8k+2$ and the graph is isomorphic to the explicitly constructed graph $H_k$, so all extremal graphs are classified. A central step is the proof that every such graph must be planar, which turns the extremal problem into a face-counting problem. The result shows that forbidding the three residue classes simultaneously forces a strictly smaller edge density, with slope $11/8$, than forbidding any two of them, whose known lower bounds have slope $3/2$.","feed_headline":"Cycle ban yields exact edge bound: 11n/8 − 7/4","feed_subtitle":"For every n≥2 the bound is sharp and all extremal graphs are classified.","key_machinery":"The proof runs on four structural reductions. First, planarity: Lemma 4.2 shows every subdivision of $K_5$ contains a cycle of length $0 \\bmod 3$, and Lemma 4.3 shows every subdivision of $K_{3,3}$ contains a cycle of length $0$ or $4 \\bmod 6$ by a $3\\times 3$ matrix congruence argument; Kuratowski's theorem then forces every $(0,3,4 \\bmod 6)$-cycle-free graph to be planar. Second, Lemma 3.1: an $8$-angulation whose dual is bipartite, with girth $8$ and no $10$- or $12$-cycles, must be a $\\theta_4$-graph, meaning several internally disjoint paths of length $4$ sharing the same pair of endpoints. Third, a face-counting inequality, $3f_5 + f_7 \\le \\frac{2}{11}e + \\frac{64}{11}$, obtained from the structure of the $5$-faces and $7$-face blocks. Fourth, Euler's formula converts that inequality into $e \\le \\frac{11}{8}n - \\frac{7}{4}$. Equality forces the graph to decompose into a $\\theta_4$-graph plus antipodal paths, and the cycle restrictions then identify the extremal graph as $H_k$.","core_discovery":"The paper's central claim is a sharp edge bound: every $n$-vertex graph $G$ with no $(0,3,4 \\bmod 6)$-cycle satisfies $e(G) \\le \\frac{11}{8}n - \\frac{7}{4}$, with equality exactly when $n = 8k+2$ and $G$ is isomorphic to the explicit graph $H_k$. The graph $H_k$ is built by taking $k$ copies of a fixed eight-vertex gadget, identifying the two marked vertices of every copy into a single pair, and adding one edge between them; every cycle of $H_k$ has length $5$, $7$, $8$, $11$, or $14$. The proof shows such graphs are planar, then bounds edges through Euler's formula and a detailed census of face lengths, and finally uses a structural lemma on $8$-angulations to identify the equality case. The paper also supplies, for every $n \\ge 2$, a graph attaining $\\left\\lfloor \\frac{11}{8}n - \\frac{7}{4} \\right\\rfloor$ edges, so the extremal number is exact with no exceptional $n$.","pith_inferences":["A testable extension is to apply the same planarity-plus-face-counting template to the pairs $(0,4 \\bmod 6)$ and $(3,4 \\bmod 6)$, whose exact extremal numbers the paper leaves open; the slope-$3/2$ lower bounds suggest their true coefficients may be $3/2$ or a nearby rational.","The matrix-congruence argument that rules out $K_{3,3}$ subdivisions is purely algebraic and may generalize to $K_{3,t}$ or to other residue pairs, potentially yielding a systematic planarity criterion for multi-residue cycle bans.","Because the equality graph $H_k$ is a chain of $k$ internally disjoint length-$4$ paths between two poles with alternating antipodal chords, varying the common path length or the chord lengths gives natural candidate extremal graphs for neighbouring residue problems.","If the rigid face structure of the equality case, with only $5$-, $7$-, and $8$-faces, is typical, then exact bounds for other multi-residue bans might be provable by classifying which near-$8$-angulations admit no forbidden cycle, a finite check for each residue set."],"forward_implications":["For every $n \\ge 2$, the extremal number is exactly $\\left\\lfloor \\frac{11}{8}n - \\frac{7}{4} \\right\\rfloor$, so the upper bound is always attainable and there are no exceptional values of $n$.","Equality in the bound is fully classified: it occurs only for $n = 8k+2$ and forces $G \\cong H_k$, giving a complete list of extremal graphs.","Every graph avoiding $(0,3,4 \\bmod 6)$-cycles is planar, so the forbidden cycle lengths impose a topological restriction that can be exploited in other arguments.","Forbidding all three residue classes together is strictly stronger than forbidding any two of them, since the known lower-bound constructions for pairs have slope $3/2$, larger than $11/8$."],"supporting_citations":[{"why":"Establishes that the extremal number for non-bipartite residue pairs is linear, the regime in which the paper's bound lives.","marker":"[4]"},{"why":"Supplies the exact value 2n−4 for graphs with no 0-mod-3 cycle, used in the comparison showing that 11/8 is smaller.","marker":"[6]"},{"why":"Provides the planarity approach for C_{0 mod 4}-free graphs that the paper adapts to the multi-residue setting.","marker":"[11]"}],"fun_headline_variants":["Exact edge bound: 11n/8 - 7/4 for no (0,3,4 mod 6) cycles","11n/8 - 7/4: sharp extremal edge count for cycle-restricted graphs","Cycle ban yields exact max edges: 11n/8 - 7/4","Forbidden cycle lengths: exact edge maximum 11n/8 - 7/4","Max edges pinned: 11n/8 - 7/4 for cycle-restricted graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof depends on the claim that no matter how the nine edges of the complete bipartite graph $K_{3,3}$ are subdivided into paths, some resulting cycle has length $0$ or $4$ modulo $6$; the three-case matrix argument verifying this is asserted rather than shown in full, and a missing case would remove the planarity step and invalidate the edge bound.","fun_headline_variants_meta":{"raw":{"variants":["Exact edge bound: 11n/8 - 7/4 for no (0,3,4 mod 6) cycles","11n/8 - 7/4: sharp extremal edge count for cycle-restricted graphs","Cycle ban yields exact max edges: 11n/8 - 7/4","Forbidden cycle lengths: exact edge maximum 11n/8 - 7/4","Max edges pinned: 11n/8 - 7/4 for cycle-restricted graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00109,"raw_usage":{"total_tokens":4547,"prompt_tokens":930,"completion_tokens":3617,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":546,"completion_tokens_details":{"reasoning_tokens":3503}},"tokens_in":546,"tokens_out":3617,"duration_ms":26585,"temperature":1.0,"reasoning_tokens":3503,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:15:56.922806+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all $3\\times 3$ matrices over $\\mathbb{Z}/6\\mathbb{Z}$ with entries in $\\{1,2,3,5\\}$, even row and column sums, and with $b_{\\mathrm{sum}} + T_\\sigma \\in \\{1,3,4,5\\}$ for every permutation $\\sigma$; Lemma 4.3 claims every such matrix is one of three displayed patterns. If a single matrix outside those patterns exists, it yields a $K_{3,3}$ subdivision with no $(0,3,4 \\bmod 6)$-cycle, refuting the planarity proposition and the bound. Equivalently, exhibit one such subdivision explicitly.","supporting_citations":[{"cited_title":"Bollob´ as, Cycles modulok,Bulletin of the London Mathematical Society9 (1) (1977), 97–98","cited_arxiv_id":null,"evidence_quote":"Establishes that the extremal number for non-bipartite residue pairs is linear, the regime in which the paper's bound lives."},{"cited_title":"Chen and A","cited_arxiv_id":null,"evidence_quote":"Supplies the exact value 2n−4 for graphs with no 0-mod-3 cycle, used in the comparison showing that 11/8 is smaller."},{"cited_title":"Gy˝ ori, B","cited_arxiv_id":null,"evidence_quote":"Provides the planarity approach for C_{0 mod 4}-free graphs that the paper adapts to the multi-residue setting."}],"review_version":1}