{"id":"ec39f2c1-1285-4c49-9e39-dd64489deca3","arxiv_id":"2411.17322","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The Turan number ex(n,{C>=k,F}) is determined up to an additive constant for every 2-connected F with p(F) at least floor((k-1)/2)+1; the even-k formula is n times the larger of (k-2)/2 and ex(k-1,F)/(k-2), plus O_k(1).","lead":"This paper finds the maximum number of edges a large graph can have when it is forbidden from containing both a long cycle and any copy of a fixed 2-connected graph F. The answer is determined up to an additive constant, and it extends earlier results that only handled cliques as the second forbidden graph.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3's proof silently drops e(G[A]); if A is not independent the main upper bounds fail. The paper must supply the missing independence proof or the theorems are unproven as written.","rationale":"I independently examined the chain Lemma 3 -> Lemma 5 -> Theorems 4-6. The reader's weakest_assumption is exactly Lemma 3; I agree it is the load-bearing point, but I would sharpen it. The specific algebraic identity in the proof of Lemma 3 silently omits e(G[A]). The later assertion that G' is 2-connected also needs a real argument, not just 'by N_{G1}(u)=0'. Both are repairable if A is independent and shares a common neighbor set in the even case; these facts are plausible but not proved. I also agree with the reader's k=4 issue in Theorem 6: the friendship graph is not F-free for F=K3, but the p-copies construction gives the same lower bound, so that is a local fix. No independent error beyond these gaps surfaced; the algebraic upper bound in Theorem 6's block decomposition checks out. Therefore I do not recommend changing the reader's conditional verdict; the paper should be accepted only after Lemma 3, and the k=4 sentence, are repaired. I would not call this a rejection or an unconditional acceptance.","tokens_in":10598,"tokens_out":24976,"duration_ms":237631,"concrete_test":"Prove or disprove the following structural claim: if C is a longest cycle of a 2-connected graph and A = {v outside C : d_C(v)=floor(c/2)}, then A is independent; moreover, for even c all vertices of A have the same neighborhood on C. Concretely, attempt the standard cycle-extension argument: for adjacent u,v in A choose x in N_C(u), y in N_C(v) with d_C(x,y) <= 2, and use x-u-v-y plus the long arc of C to obtain a cycle longer than c. If the argument succeeds, insert e(G[A]) = 0 into Lemma 3 and add the corresponding sentence to Lemma 4; if it fails, the counterexample refutes Lemma 3 and the main upper bounds. A brute-force search over all 2-connected graphs on n <= 8 with c = 4, 5, 6 can verify the claim computationally.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Lemma 3 (Section 2), after proving that each u in A has no neighbor in G-C, the proof defines G' = G - A and states: e(G-C)+e(G-C,C) = floor(c/2)|A| + e(G'-C)+e(G'-C,C). This identity is not justified. The left side includes e(G[A]) plus edges from A to C plus edges from A to G'-C. The last set is empty by the preceding claim, and edges from A to C contribute exactly floor(c/2)|A|, but e(G[A]) is never shown to vanish. If two vertices of A are adjacent, the equality is false and the claimed bound can fail by that many edges. The paper also asserts that G' is 2-connected by N_{G1}(u)=0 without a proof; this is plausible because the cycle C survives, but the one-line justification is not sufficient. Lemma 3 is then used in Lemma 5 and in the upper-bound proofs of Theorems 4, 5, and 6, so any error here propagates to the central asymptotic formulas. The gap is likely repairable: from the longest-cycle condition one can try to show that any u,v in A with uv in E(G) yields a cycle of length at least c+1, using a pair of C-neighbors at cyclic distance at most 2. But as written, the lemma is not established.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Turán number ex(n,{C_{\\ge k},F}) for a fixed 2-connected graph F with p(F) \\ge \\lfloor(k-1)/2\\rfloor+1. The main results are Theorem 4 (odd k, 2-connected extremal number equals ex(t,H)+t(n-t)), Theorem 5 (even k, same formula up to an additive 0/1 term), and Theorem 6 (general asymptotic ex(n,{C_{\\ge k},F}) = n\\max\\{(k-2)/2, ex(k-1,F)/(k-2)\\} + O_k(1)). The proofs rely on a strengthening of Bondy's lemma (Lemma 3), a structural estimate on the edges of a longest cycle (Lemma 4), and a block decomposition argument. The paper also discusses extensions and relations to the path-plus-clique problem.","tokens_in":10805,"tokens_out":15694,"duration_ms":149861,"significance":"If the proofs are completed, this is a substantial extension of the earlier clique case of Dou--Ning--Peng [5] to a general 2-connected graph F. The asymptotic formula is clean and parameter-free, and the paper supplies explicit extremal constructions, including a block-based upper bound that reduces the problem to the finite quantity ex(k-1,F). The main weaknesses are localized gaps: Lemma 3 omits an edge-count term, the k=4 case of Theorem 6 contains a false assertion about friendship graphs, and the connectivity reduction in Theorem 6 is not justified as written. These issues appear repairable, but they currently affect load-bearing parts of the argument.","major_comments":[{"comment":"After proving N_{G-C}(u)=0 for each u\\in A, the proof sets G'=G-A and asserts e(G-C)+e(G-C,C)=t|A|+e(G'-C)+e(G'-C,C). This equality is not justified: the left side also contains e(G[A]), which has not been shown to vanish. If A is not independent, the claimed upper bound fails by e(A). The subsequent assertion that G' is 2-connected also needs a real proof, since deleting all vertices of A could expose a cut vertex on C even though each vertex of A has no neighbors in G-C. Lemma 3 is used in Lemma 5 and in the upper-bound proofs of Theorems 4-6, so this gap is load-bearing for all main results.","section":"Section 2, Lemma 3"},{"comment":"The statement 'a friendship graph is F-free' is false when F=K3, because the friendship graph contains triangles; K3 is 2-connected and nonbipartite, hence p(F)=\\infty and satisfies the hypothesis. The lower bound for K3 can be recovered from a tree, which is both triangle-free and C_{\\ge4}-free, but the printed justification is wrong and must be replaced. The same sentence should also clarify for which F the friendship construction is actually valid.","section":"Section 4, proof of Theorem 6, k=4 case"},{"comment":"The sentence 'As both F and C_{\\ge k} are 2-connected, we may assume G is connected' is not a valid statement about the family C_{\\ge k}. The connectivity reduction is in fact true for the intended reason (adding one edge between two components creates neither a copy of the 2-connected F nor a cycle), but this needs to be argued explicitly. The identity \\sum_{i=1}^w (b_i-1)=n-1 used later depends on connectedness, so as written the upper-bound proof has a gap for disconnected graphs.","section":"Section 4, Theorem 6 upper bound"}],"minor_comments":[{"comment":"The first line contains a typo: 't = \\lfloor(k-1)/2\\rfloor = t-2/2' should read 't = (k-2)/2' in the even-k case.","section":"Section 4, proof of Theorem 6"},{"comment":"In the case split, one occurrence reads 'ex(k-1,H)' where the surrounding formula uses 'ex(k-1,F)'; this should be corrected to ex(k-1,F).","section":"Section 4, upper-bound estimate"},{"comment":"There is a duplicated inequality sign '\\le\\le' in the displayed estimate for c=k-2; this is a typographical error.","section":"Section 3, proof of Theorem 5"},{"comment":"The strictness argument says 'Otherwise, the subgraph of G induced by L\\cup\\{v_2,v_3\\} contains F as a subgraph'; this only follows under the equality conditions (G[L] in EX(t,H), complete bipartite between L and R, and v_2v_3 present), so the sentence should be rephrased to make the equality case explicit.","section":"Section 2, Lemma 4(2)"}],"recommendation":"major_revision","confidential_remarks":"The main results depend on Lemma 2 from the authors' companion paper [5], which is not yet published. The current paper strengthens that lemma, but the editor may wish to confirm that [5] is publicly available and that its proof of Lemma 2 is sound. The gaps identified here are localized and likely repairable within the manuscript's scope, so I do not recommend rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this paper generalizes the known ex(n,{C>=k,K_r}) results to ex(n,{C>=k,F}) for any 2-connected F with p(F) >= floor((k-1)/2)+1, up to O_k(1). For odd k the answer is boring (t n + O(1)); for even k you get the two-term max formula involving ex(k-1,F). The framework via H and p(F) is a clean way to package the reduction, and the main upper-bound machinery is a direct but competent extension of Dou-Ning-Peng [5]. I checked the chain of inequalities in Theorems 4-6 for k>=6 and they hold. Lemma 3, which the paper leans on, is fine: the recent stress-test worry about a dropped e(G[A]) does not land, because the proof first establishes N_{G1}(u)=0 for every u in A, which forces A to be independent and to have no edges to G'-C; the identity is then exact. The assertion that G' stays 2-connected is terse but true.\n\nThe real flaw is in the k=4 case of Theorem 6. The proof says a friendship graph is F-free; that is false when F=K3, which is an allowed F. The formula still holds (for F=K3 the max is 1 and a star gives the lower bound), so the error is localized and repairable, but as written the proof of that case does not establish the claim. A referee should ask for a corrected lower-bound argument for triangle-containing F.\n\nMinor issues: a typo in the proof of Theorem 6 where ex(k-1,H) should be ex(k-1,F), and a garbled line \"t = floor((k-1)/2) = t-2/2\". Also the self-citation to Lemma 2 from [5] is not circular; they prove a strengthening here.\n\nWho is this for? Extremal graph theorists working on generalized Turán problems. It is a useful, expected generalization rather than a breakthrough, but it clears up a natural open case and the reduction to finite ex values is elegant. I would send it to a competent referee. The k=4 fix should be requested, and the exposition around Lemma 3 could be expanded, but neither issue undermines the k>=6 theorems.\n\nMy recommendation: engage with it; accept for review with a request for a corrected k=4 argument.","headline":"A solid extension of the clique case to general 2-connected F; the k>=6 results look right, but the k=4 case in Theorem 6 has a false claim that needs fixing.","tokens_in":11424,"tokens_out":9409,"would_cite":true,"duration_ms":84106,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C38","05C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper determines the Turán number of the family $C_{\\ge k}\\cup\\{F\\}$ up to an additive constant for any 2-connected $F$ with $p(F)\\ge \\lfloor (k-1)/2\\rfloor+1$, extending the clique case.","keywords":["Turán number","extremal graph","cycle","2-connected graph","bipartite graph","vertex cover","Erdős-Gallai theorem","circumference"],"falsifier":"Take any 2-connected graph $G$ with a longest cycle $C$ of length $c$ ($4\\le c\\le n-1$) and let $A$ be the set of vertices outside $C$ with $\\lfloor c/2\\rfloor$ neighbours on $C$; if $e(G-C)+e(G-C,C)>\\lfloor c/2\\rfloor|A|+(\\lfloor c/2\\rfloor-\\frac12)(n-c-|A|)$, or if $G-A$ is not 2-connected, then Lemma 3 fails and with it the upper-bound proofs of Theorems 4, 5 and 6.","tokens_in":10318,"feed_emoji":"📐","tokens_out":16811,"duration_ms":135537,"temperature":0.7,"pith_summary":"This paper determines, up to an additive constant, the maximum number of edges in an $n$-vertex graph that contains neither a cycle of length at least $k$ nor a copy of a fixed 2-connected graph $F$, for all sufficiently large $n$. The answer is governed by the larger of two densities: the edge density imposed by the cycle restriction alone, and the edge density of the best $(k-1)$-vertex graph with no copy of $F$. For odd $k$ the first density always dominates, and for even $k$ both compete. The result holds when $F$ is nonbipartite or when $F$ is bipartite with a vertex-cover colour class parameter $p(F)\\ge \\lfloor (k-1)/2\\rfloor+1$, and it extends an earlier exact result for $F$ being a clique. A sympathetic reader should care because it turns a two-constraint extremal problem into a comparison of two simple quantities for a broad class of forbidden graphs.","feed_headline":"Forbidden cycles plus F: the Turán number is one maximum","feed_subtitle":"For even k, the extremal edge count is n times the larger of two densities, up to an additive constant.","key_machinery":"The load-bearing technical object is a strengthened classical inequality for longest cycles (Lemma 3): if $C$ is a longest cycle of length $c$ in a 2-connected graph $G$, and $A$ is the set of vertices outside $C$ having $\\lfloor c/2\\rfloor$ neighbours on $C$, then $e(G-C)+e(G-C,C)\\le \\lfloor c/2\\rfloor|A|+(\\lfloor c/2\\rfloor-\\frac12)(n-c-|A|)$. This is proved from a two-case bound from the authors' earlier work and from the assertion that $G-A$ remains 2-connected. The second ingredient (Lemma 4) caps the edges inside the cycle: once $|A|$ is large enough, the neighbour set $L$ of a vertex in $A$ must be $H$-free, where $H$ is the family of subgraphs of $F$ induced by vertex covers, giving $e(G[C])\\le \\mathrm{ex}(t,H)+t^2$ for even $c$ and $e(G[C])\\le \\mathrm{ex}(t,H)+t(t+1)+1$ for odd $c$, with $t=\\lfloor (k-1)/2\\rfloor$; in the odd case the inequality is strict when every extremal $t$-vertex $H$-free graph contains one of the graphs $H'=\\{F-\\{u,v\\}:uv\\in E(F)\\}$. For Theorem 6 the remaining work is a block decomposition: every block has longest cycle at most $k-1$, and each block is charged either at density $\\frac{k-2}{2}$ per vertex or at density $\\frac{\\mathrm{ex}(k-1,F)}{k-2}$, so the maximum of the two densities bounds the whole graph.","core_discovery":"Let $C_{\\ge k}$ be the family of cycles of length at least $k$, and let $F$ be a 2-connected graph with $p(F)\\ge \\lfloor (k-1)/2\\rfloor+1$, where $p(F)$ is the smallest possible colour class size in a proper 2-colouring of $F[S]$ as $S$ ranges over vertex covers of $F$, and $p(F)=\\infty$ for nonbipartite $F$. Writing $\\mathrm{ex}(n,\\{C_{\\ge k},F\\})$ for the maximum number of edges in an $n$-vertex graph with no such cycle and no copy of $F$, the paper proves that for sufficiently large $n$, $\\mathrm{ex}(n,\\{C_{\\ge k},F\\})=\\frac{k-1}{2}n+O_k(1)$ when $k$ is odd, and $\\mathrm{ex}(n,\\{C_{\\ge k},F\\})=n\\max\\{\\frac{k-2}{2},\\frac{\\mathrm{ex}(k-1,F)}{k-2}\\}+O_k(1)$ when $k$ is even. The proof first solves the 2-connected version: $\\mathrm{ex}_{2\\text{-conn}}(n,\\{C_{\\ge k},F\\})=\\mathrm{ex}(t,H)+t(n-t)$ for odd $k$, and the same plus an integer $\\ell\\in\\{0,1\\}$ for even $k$, where $t=\\lfloor (k-1)/2\\rfloor$ and $H$ is the family of induced subgraphs of $F$ on vertex covers. The even-$k$ formula then follows by decomposing an extremal graph into blocks and charging each block against one of the two densities.","pith_inferences":["The authors leave implicit a stability statement: near-extremal graphs for even $k$ should be either split-like graphs $T \\vee I_{n-t}$ with $T \\in \\mathrm{EX}(t,H)$ or windmills of $(k-1)$-vertex $F$-free blocks joined at a cut vertex; proving this would turn the asymptotic formula into a structural one.","For non-2-connected $F$, the paper leaves a gap between the general upper bound and the windmill lower bound when $\\frac{\\mathrm{ex}(k-1,F)}{k-2}>\\frac{k-2}{2}$; a natural test is whether the windmill construction still attains the lower bound for such $F$.","The $p(F)$ condition is deployed only through the cycle-edge lemma, so any weakening of that lemma would automatically enlarge the family of bipartite graphs for which the exact asymptotic formula holds.","One could probe the sharpness of the $O(1)$ term by computing the even-$k$ additive constant $\\ell$ in the 2-connected theorem for small parameters; the paper leaves open whether $\\ell=1$ ever occurs."],"forward_implications":["For every 2-connected nonbipartite $F$ and every even $k\\ge 6$, forbidding all cycles of length at least $k$ and copies of $F$ costs exactly $n\\max\\{\\frac{k-2}{2},\\frac{\\mathrm{ex}(k-1,F)}{k-2}\\}+O(1)$ edges, so the extremal density is one of two explicit numbers.","For odd $k$, the cycle constraint alone is decisive: $\\mathrm{ex}(n,\\{C_{\\ge k},F\\})=\\frac{k-1}{2}n+O(1)$ for every $F$ satisfying the $p(F)$ condition.","The 2-connected version of the problem is solved almost exactly: $\\mathrm{ex}_{2\\text{-conn}}(n,F)=\\mathrm{ex}(t,H)+t(n-t)+\\ell$ with $\\ell\\in\\{0,1\\}$, and $\\ell=0$ whenever every extremal $t$-vertex $H$-free graph contains a member of $H'$.","The upper bound in Theorem 6 does not actually require $F$ to be 2-connected, so the displayed upper bound holds for all graphs $F$, while the lower bound needs 2-connectivity.","The result extends the earlier exact determination for $F=K_r$ to a general 2-connected $F$ under the $p(F)$ balance condition, so the same comparison-of-densities phenomenon is universal."],"supporting_citations":[{"why":"Supplies the two-case bound (Lemma 2) from which Lemma 3 is derived, the construction $T\\vee I_{n-t}$, and the previous results for $F=K_r$ that this paper extends.","marker":"[5]"},{"why":"Provides the classical bound on edges outside a longest cycle that Lemma 2 and Lemma 3 sharpen, and it is the base inequality for the outside-cycle estimates.","marker":"[3]"},{"why":"Gives the upper bound $\\mathrm{ex}(n,C_{\\ge k})\\le \\frac{(k-1)(n-1)}{2}$, used in the odd-$k$ case, in Lemma 5, and for bounding the smallest blocks in Theorem 6.","marker":"[6]"}],"fun_headline_variants":["Forbidden cycles plus F: Turán number solved up to constant","Exact extremal edge count for cycles and a general graph","Odd/even split: Turán number for cycles and F determined","2-connected F forbidden with cycles: Turán number asymptotics","Even k: n max density; odd: (k-1)/2 n"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proofs of Theorems 4 and 5 rest on the inequality in Lemma 3, which is inherited from a previous two-case bound and on the claim that deleting the set $A$ of outside vertices with the most neighbours on a longest cycle leaves a 2-connected graph; if either the transferred inequality or the 2-connectivity claim fails, the main upper bounds collapse.","fun_headline_variants_meta":{"raw":{"variants":["Forbidden cycles plus F: Turán number solved up to constant","Exact extremal edge count for cycles and a general graph","Odd/even split: Turán number for cycles and F determined","2-connected F forbidden with cycles: Turán number asymptotics","Even k: n max density; odd: (k-1)/2 n"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000747,"raw_usage":{"total_tokens":3409,"prompt_tokens":1106,"completion_tokens":2303,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":722,"completion_tokens_details":{"reasoning_tokens":2211}},"tokens_in":722,"tokens_out":2303,"duration_ms":19024,"temperature":1.0,"reasoning_tokens":2211,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:17:28.465026+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take any 2-connected graph $G$ with a longest cycle $C$ of length $c$ ($4\\le c\\le n-1$) and let $A$ be the set of vertices outside $C$ with $\\lfloor c/2\\rfloor$ neighbours on $C$; if $e(G-C)+e(G-C,C)>\\lfloor c/2\\rfloor|A|+(\\lfloor c/2\\rfloor-\\frac12)(n-c-|A|)$, or if $G-A$ is not 2-connected, then Lemma 3 fails and with it the upper-bound proofs of Theorems 4, 5 and 6.","supporting_citations":[{"cited_title":"Bondy, Large cycles in graphs, Discrete Math., 1(2) 1971/72, 121–132","cited_arxiv_id":null,"evidence_quote":"Provides the classical bound on edges outside a longest cycle that Lemma 2 and Lemma 3 sharpen, and it is the base inequality for the outside-cycle estimates."},{"cited_title":"Erd˝ os and T","cited_arxiv_id":null,"evidence_quote":"Gives the upper bound $\\mathrm{ex}(n,C_{\\ge k})\\le \\frac{(k-1)(n-1)}{2}$, used in the odd-$k$ case, in Lemma 5, and for bounding the smallest blocks in Theorem 6."}],"review_version":1}