{"id":"3ab09b3b-5305-41af-b265-02cef348a9ee","arxiv_id":"2507.11034","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For large n, the authors give the exact maximum edge count ex(n, {H,F}) for graphs avoiding both a linear forest H and a fixed graph F with chromatic number at least three.","lead":"The paper determines, for large graphs, the maximum number of edges possible when two forbidden patterns are banned at once: any fixed graph that needs at least three colors, and any specified linear forest made of separate paths. The exact formulas unify several recent results in extremal graph theory and give sharp constants for a wide family of forbidden pairs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.1's proof uses the wrong Erdős–Gallai bound; the claimed ℓ′n − 6ℓ² lower bound does not follow, so Theorems 1.11/1.12 for general linear forests are unproved as written.","rationale":"The reader's weakest-assumption analysis focused on Lemma 2.6 and the implicit induction in Lemma 2.5, which is a legitimate concern for the kP_l theorems. My stress-test review found a more concrete, checkable flaw in the proof of Lemma 4.1, which underpins the general linear-forest results (Theorems 1.11 and 1.12). The algebraic error is unambiguous: the proof subtracts ℓ1 n when the Erdős–Gallai bound for a path with v(H1) vertices is at most (v(H1)−2)/2 n, which is smaller by n/2 or n depending on parity. Consequently, the derived lower bound is too weak by a term linear in n, and the existence of the auxiliary set A with large neighborhood is not justified. Because the paper's central claim explicitly covers all linear forests with at least two components of size at least 3, this gap is load-bearing. I do not change the overall CONDITIONAL verdict, because the kP_l and kP3 results may still be correct and the Section 4 gap might be repairable, but the present manuscript does not prove the general-H formulas as written.","tokens_in":26661,"tokens_out":39818,"duration_ms":421102,"concrete_test":"Recompute the inequality in Lemma 4.1 using the exact Erdős–Gallai bound: for H1 odd, ex(n,H1) ≤ (v(H1)−2)n/2 = (ℓ1−1/2)n. This gives e(V(H′),V(G)\\V(H′)) ≥ (ℓ′−1/2)n − O(ℓ²), which is strictly less than ℓ′n − 6ℓ² for all n > 12ℓ². Check whether any argument in the remainder of Section 4 supplies the missing n/2 term; in particular, verify whether the conclusion |N(A)| ≥ n′ can still be obtained with n′ reduced by a factor ~(1 − 1/(2ℓ′)). If not, Theorems 1.11 and 1.12 are unproved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 4.2, Lemma 4.1, the proof derives e(V(H′), V(G)\\V(H′)) ≥ (ℓ−1)(n−ℓ+1) − C(3ℓ′,2) − ℓ1 n ≥ ℓ′n − 6ℓ². The second inequality uses ex(n,H1) ≤ ℓ1 n. But Theorem 1.2 gives ex(n,P_s) ≤ (s−2)n/2, so for H1 = P_{2ℓ1} or P_{2ℓ1+1}, ex(n,H1) ≤ (ℓ1−1)n or (ℓ1−1/2)n, respectively. Replacing ℓ1 n by the correct bound yields e(V(H′),V(G)\\V(H′)) ≥ (ℓ′−1)n − O(ℓ²) in the even case and ≥ (ℓ′−1/2)n − O(ℓ²) in the odd case, neither of which is ≥ ℓ′n − 6ℓ² when n > O(ℓ²). The stated lower bound is therefore not established. This lower bound is the sole source of the set A with |A|=ℓ′ and |N(A)| ≥ n′; without it, Lemmas 4.2–4.11 and the structural reduction for Theorems 1.11/1.12 collapse. Since the abstract claims exact values for all linear forests with at least two components of size at least 3, this gap directly affects the central claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Turán numbers for families {H, F} where F is a fixed graph with chromatic number at least 3 and H is a linear forest with at least two components, each of size at least 3. The main theorems give closed-form expressions for ex(n, {kP_l, F}) (Theorems 1.6 and 1.7), ex(n, {kP_3, F}) (Theorem 1.9), and ex(n, {H, F}) for general linear forests H (Theorems 1.11 and 1.12), with corollaries for complete graphs. The proofs combine lower-bound constructions built from Turán-type graphs and auxiliary families G1(F), G2(F), H_i(F), and upper-bound arguments based on a structural decomposition of an extremal graph into a core vertex set A and sets B, C, D, obtained through a series of lemmas in Sections 2, 3, and 4.","tokens_in":26959,"tokens_out":9943,"duration_ms":102209,"significance":"If the results are correct, the paper substantially extends earlier work by Bushaw--Kettle and by Lidický--Liu--Palmer on Turán numbers of linear forests to the setting where an additional chromatic graph F is forbidden. The formulas are explicit, the lower bounds come from natural auxiliary constructions, and Theorems 1.6 and 1.7 state explicit thresholds on n. The paper also gives new corollaries for complete graphs. However, the general-linear-forest results in Section 4 contain a concrete error in the use of the Erdős--Gallai bound, and the proof of the key auxiliary Lemma 2.5 is compressed. These issues prevent the paper from being accepted in its current form.","major_comments":[{"comment":"The proof of Lemma 4.1 claims ex(n, H1) ≤ ℓ1 n, but Theorem 1.2 gives ex(n, P_s) ≤ (s−2)n/2. For H1 = P_{2ℓ1} the correct bound is (ℓ1 − 1)n, and for H1 = P_{2ℓ1+1} it is (ℓ1 − 1/2)n. Substituting either of these into the displayed inequality yields e(V(H'), V(G)\\V(H')) ≥ (ℓ' − 1)n − 6ℓ² (even case) or ≥ (ℓ' − 1/2)n − 6ℓ² (odd case), not the stated ≥ ℓ'n − 6ℓ². This lower bound is the sole source of the set A with |A| = ℓ' and |N(A)| ≥ n'; without it, Lemmas 4.2–4.11 and Theorems 1.11 and 1.12 are not established. Since the abstract claims exact values for all linear forests with at least two components, this gap is load-bearing.","section":"Section 4.2, Lemma 4.1"},{"comment":"The proof of Lemma 2.5 is an induction on k, but the induction step is not fully written. In the paragraph after defining G′, the comparison e(G′) > ((k−1)⌊ℓ/2⌋ − 1/2)(n − ⌊ℓ/2⌋) is asserted rather than shown, and the same issue recurs when the induction hypothesis is applied to H[A\\S]. In Claim 3, the averaging argument producing A* ⊆ Sx with |N(A*) ∩ U| ≥ 2n_k is only sketched, and the final numerical inequality leading to e(G) < (n − k⌊ℓ/2⌋ + 1)(k⌊ℓ/2⌋ − 1) is not derived in detail. Because Lemma 2.5 is the key step for |A| = k⌊ℓ/2⌋ − 1 in Lemma 2.6, these omissions should be filled in before the proof can be considered complete.","section":"Section 2.2, Lemma 2.5"}],"minor_comments":[{"comment":"The statement 'Since d(y) ≥ n − c′ for any y ∈ A ∪ B, we have |N_G(A∪B)| ≥ r+h' is not immediate and should be justified, for instance by a union bound showing that the number of vertices outside A∪B missed by all of A∪B is at most |A∪B|·c′.","section":"Section 4.2, before Lemma 4.3"},{"comment":"There is a typo in the displayed formula: the expression should be max{ex(ℓ−1, G1(F)), ex(ℓ−1, G2(F)) + 1}, with the closing brace after the first argument.","section":"Theorem 1.11(ii)"},{"comment":"Several references to 'Lemma 1.2' and 'Lemma 1.5' should be 'Theorem 1.2' and 'Theorem 1.5'; examples occur in the proofs of Lemma 2.3 and Lemma 4.3.","section":"Throughout Sections 2 and 4"},{"comment":"The phrase 'n is large enough' is not quantified in Theorems 1.11 and 1.12, whereas Theorems 1.6 and 1.7 give explicit lower bounds on n. Since the proof introduces constants c and c′ depending on ℓ and h′, an explicit threshold should be stated if the results claim exact values for all sufficiently large n.","section":"Theorems 1.11 and 1.12"},{"comment":"In the introduction the citation is given as 'Lu, Liu and Kang [13]', but reference [13] lists only Y. Lu and L. Kang; the citation or the reference entry should be corrected.","section":"Introduction and References"},{"comment":"There are typographical errors 'subgrapgh' and 'contraction' that should be corrected to 'subgraph' and 'contradiction'.","section":"Proofs of Theorem 1.7 and 1.12"}],"recommendation":"major_revision","confidential_remarks":"The error in Lemma 4.1 is concrete and easily verified; it directly undermines Theorems 1.11 and 1.12, which are central to the abstract's claim. The rest of the paper, especially the kPℓ and kP3 results, may be salvageable, but Section 4 needs a corrected bound or a substantially different argument. The compressed induction in Lemma 2.5 should also be expanded regardless. I recommend major revision rather than rejection because the issue appears fixable in principle, but the current manuscript does not prove the stated general-linear-forest theorems."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague —\n\nThis paper is a mixed bag. The core new material, exact ex(n,{F,kP_ℓ}) and ex(n,{F,kP_3}) for χ(F)≥3, is a genuine extension of Bushaw–Kettle and Alon–Frankl. The lower bounds are explicit constructions, the upper-bound machinery via the auxiliary ⌊ℓ/2⌋-uniform hypergraph and the G1/G2 and H_i(F) families is coherent, and the corollaries for K_r match known results. The kP_3 case with the σ(F) parameter is particularly nice. Sections 2 and 3 look credible to me; Lemma 2.5's induction is compressed and Theorem 1.7's proof has an off-by-one feel in places, but neither struck me as load-bearing.\n\nThe problem is Section 4. Lemma 4.1's proof asserts\ne(V(H'),V(G)\\V(H')) ≥ (ℓ−1)(n−ℓ+1) − C(3ℓ',2) − ex(n,H_1) ≥ ℓ'n − 6ℓ².\nThe last inequality is false as written. Using the paper's own bound ex(n,H_1) ≤ ℓ_1 n, the left-hand side is (ℓ−ℓ_1−1)n − O(ℓ²) = (ℓ'−1)n − O(ℓ²), not ℓ'n − O(ℓ²). You can repair it by using the tight Erdős–Gallai bound ex(n,P_s) ≤ (s−2)n/2, which gives (ℓ_1−1)n and yields ℓ'n − O(ℓ²), but that is not what appears in the proof. With the displayed bound, the averaging argument that produces A with |N(A)| ≥ n' collapses, and Lemmas 4.2–4.11 plus Theorems 1.11–1.12 have no support. Since the abstract advertises exact values for every linear forest with at least two components of size at least 3, this is a load-bearing gap.\n\nMy recommendation: don't desk-reject. Sections 2–3 are likely correct and valuable, and Section 4's failure looks fixable — replace the bound and check whether the subsequent inequalities survive. But as it stands, the general linear forest claim should not be taken as proved. A serious referee should ask for a full rewrite of Lemma 4.1 and a re-verification of the dependent lemmas before publication.\n\nIf you're looking for a reading-group paper, this is a decent case study of how a small inequality error can sink a large structural argument. I'd cite only the kP_ℓ and kP_3 results once they're cleaned up.","headline":"Valuable equal-path and kP_3 results, but the general linear forest theorems rest on a bad inequality in Lemma 4.1.","tokens_in":27514,"tokens_out":5083,"would_cite":false,"duration_ms":57573,"reading_group":"maybe","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":"The paper determines the exact Turán number for any linear forest H plus any fixed graph F with chromatic number at least 3.","keywords":["Turán number","linear forest","disjoint paths","chromatic number","edge control number","forbidden subgraphs","extremal graphs"],"falsifier":"For $F=K_4$, $k=2$, $\\ell=4$, the theorem gives $\\operatorname{ex}(n,\\{K_4,2P_4\\})=3n-7$ at its stated large-$n$ range; finding any $\\{K_4,2P_4\\}$-free graph with $3n-6$ edges for a valid $n$ would refute the formula and the structural reduction behind it.","tokens_in":26450,"feed_emoji":"📐","tokens_out":15787,"duration_ms":180509,"temperature":0.7,"pith_summary":"The paper establishes the exact value of the two-family Turán number $\\operatorname{ex}(n,\\{H,F\\})$ for every linear forest $H$ with at least two components, each a path on at least three vertices, and every fixed graph $F$ with chromatic number at least three. The answer is a sharply lopsided complete bipartite graph: one side has a fixed small size determined by $H$, every vertex outside is joined to all of that side, and the only remaining freedom is a small number of extra edges inside the small side. The size of that extra set is itself a Turán number of a family of induced subgraphs of $F$, so the problem is reduced to a much smaller extremal question. This extends earlier exact results for equal-length disjoint paths and for matching-type side conditions.","feed_headline":"Exact Turán number found for a fixed graph plus a linear forest","feed_subtitle":"For every 3-chromatic F, the answer is a lopsided complete bipartite graph plus a small, exactly counted correction.","key_machinery":"The mechanism is a structural reduction. In the $kP_\\ell$ case, the paper builds an auxiliary $\\lfloor\\ell/2\\rfloor$-uniform hypergraph whose hyperedges are sets of $\\lfloor\\ell/2\\rfloor$ vertices with a large common neighborhood; any copy of $P_\\ell$ forces such a set, and the absence of $k$ disjoint $P_\\ell$ forces the hypergraph's matching number to be at most $k-1$. Lemmas 2.2--2.6 then squeeze the extremal graph into the form $|A|=k\\lfloor\\ell/2\\rfloor-1$, $B$ complete to $A$ of size at least $k\\ell+v(F)$, $C=D=\\emptyset$, and at most one edge in $B$; every subsequent edge count is read off from this skeleton. For $kP_3$, the analogous reduction uses a set $A$ of $k-1$ high-degree vertices (one from each of $k-1$ disjoint $P_3$'s), a lemma that the remaining graph has maximum degree at most one, and the parameter $\\sigma(F)$, the largest matching whose union with an independent set remains $F$-free. For general linear forests, a 'pseudo-bipartite' decomposition $A\\cup B$ with $|A\\cup B|=\\ell-1$ plays the same role.","core_discovery":"On the paper's own terms, the central discovery is that forbidding a fixed chromatic graph $F$ alongside a linear forest forces an extremal graph into a very lopsided form. For $kP_\\ell$, the extremal graph has a part $A$ of size $k\\lfloor\\ell/2\\rfloor-1$, every vertex outside $A$ is adjacent to all of $A$, the outside has no internal structure beyond possibly one edge when $\\ell$ is odd, and the edges inside $A$ must avoid the families $\\mathcal G_1(F)$ and $\\mathcal G_2(F)$ of induced subgraphs obtained by deleting a vertex set spanning, respectively, zero or at most one edge. Consequently $\\operatorname{ex}(n,\\{F,kP_\\ell\\})=(n-k\\lfloor\\ell/2\\rfloor+1)(k\\lfloor\\ell/2\\rfloor-1)+b_\\ell$, with $b_\\ell=\\max\\{1+\\operatorname{ex}(k\\lfloor\\ell/2\\rfloor-1,\\mathcal G_2(F)),\\operatorname{ex}(k\\lfloor\\ell/2\\rfloor-1,\\mathcal G_1(F))\\}$ for odd $\\ell$ and $b_\\ell=\\operatorname{ex}(k\\lfloor\\ell/2\\rfloor-1,\\mathcal G_1(F))$ for even $\\ell$. The statement splits according to the edge-control number $\\beta_1(F)$, the minimum size of an edge set that touches every edge of $F$: when $\\beta_1(F)=1$ the correction is decided by a short parity condition (property $P$ or $R$), otherwise it is given by the two small Turán numbers above. An analogous theorem for $kP_3$ uses a part of size $k-1$ and a matching parameter $\\sigma(F)$; the general linear-forest theorems use a part of size $\\ell-1$, where $\\ell$ sums $\\lfloor v(P)/2\\rfloor$ over the components. The same lopsided shape underlies all of Theorems 1.6--1.12.","pith_inferences":["The paper does not pursue the matching case $H=kP_2$, but its structural language suggests that the same lopsided reduction would reproduce the known exact results for $\\operatorname{ex}(n,\\{F,M_s\\})$ as a limiting case.","Because the correction term is itself a Turán number for induced-subgraph families of $F$, any future improvement in computing those small-case values would automatically sharpen the two-family formulas.","The parity jump—adding exactly one edge when an odd path is present—looks like a stable phenomenon; one could test whether it persists for alternate families of forbidden graphs with chromatic number at least three."],"forward_implications":["For cliques, the formulas are fully explicit: Corollary 1.8 gives $\\operatorname{ex}(n,\\{K_r,kP_\\ell\\})$ as the lopsided bipartite term plus either $\\operatorname{ex}(k\\lfloor\\ell/2\\rfloor-1,K_{r-1})$ or the binomial term, according as $r\\le k\\lfloor\\ell/2\\rfloor+1$ or not.","For $kP_3$, Theorem 1.9 yields $\\operatorname{ex}(n,\\{kP_3,F\\})=(k-1)(n-k+1)+\\lfloor (n-k+1)/2\\rfloor+\\operatorname{ex}(k-1,\\mathcal H(F))$ when $\\sigma(F)=\\infty$, and an explicit maximum over $i\\le\\sigma(F)$ otherwise.","For a general linear forest $H$, Theorems 1.11--1.12 reduce the exact value to $\\operatorname{ex}(\\ell-1,\\mathcal G_1(F))$, with the odd-component case allowing the alternative $\\operatorname{ex}(\\ell-1,\\mathcal G_2(F))+1$.","Every extremal graph in the proved range has the same skeleton: a small complete core, all outside vertices complete to the core, and at most one edge outside the core."],"supporting_citations":[{"why":"Supplies the exact $\\operatorname{ex}(n,kP_\\ell)$ and $\\operatorname{ex}(n,kP_3)$ formulas used as lower bounds and as the induction base in Lemma 2.4.","marker":"[3]"},{"why":"Gives the Erdős–Gallai bound $\\operatorname{ex}(n,P_\\ell)\\le ((\\ell-2)/2)n$ used repeatedly in the upper-bound lemmas.","marker":"[6]"},{"why":"Provides the exact Turán number for general linear forests (Theorem 1.5) that anchors the Section 4 reduction for $H$.","marker":"[12]"}],"fun_headline_variants":["Exact Turan number with a fixed graph and a linear forest","Lopsided extremal graphs proven for forbidding F and paths","Turan number settled for a fixed graph plus path forest","Exact ex(n,{F,H}) when H is a linear forest","Forbidding F and disjoint paths yields exact edge count"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof depends on a structural lemma asserting that an extremal graph can be assumed complete between a small core of a precise size and all remaining vertices, with no exceptional vertex classes and at most one stray edge among the neighbours of the core; if that reduction ever fails, the closed-form formulas do not follow.","fun_headline_variants_meta":{"raw":{"variants":["Exact Turan number with a fixed graph and a linear forest","Lopsided extremal graphs proven for forbidding F and paths","Turan number settled for a fixed graph plus path forest","Exact ex(n,{F,H}) when H is a linear forest","Forbidding F and disjoint paths yields exact edge count"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000887,"raw_usage":{"total_tokens":3927,"prompt_tokens":1144,"completion_tokens":2783,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":760,"completion_tokens_details":{"reasoning_tokens":2694}},"tokens_in":760,"tokens_out":2783,"duration_ms":24944,"temperature":1.0,"reasoning_tokens":2694,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:18:47.867930+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $F=K_4$, $k=2$, $\\ell=4$, the theorem gives $\\operatorname{ex}(n,\\{K_4,2P_4\\})=3n-7$ at its stated large-$n$ range; finding any $\\{K_4,2P_4\\}$-free graph with $3n-6$ edges for a valid $n$ would refute the formula and the structural reduction behind it.","supporting_citations":[{"cited_title":"Bushaw and N","cited_arxiv_id":null,"evidence_quote":"Supplies the exact $\\operatorname{ex}(n,kP_\\ell)$ and $\\operatorname{ex}(n,kP_3)$ formulas used as lower bounds and as the induction base in Lemma 2.4."},{"cited_title":"Erd˝ os and T","cited_arxiv_id":null,"evidence_quote":"Gives the Erdős–Gallai bound $\\operatorname{ex}(n,P_\\ell)\\le ((\\ell-2)/2)n$ used repeatedly in the upper-bound lemmas."},{"cited_title":"Lidick` y, H","cited_arxiv_id":null,"evidence_quote":"Provides the exact Turán number for general linear forests (Theorem 1.5) that anchors the Section 4 reduction for $H$."}],"review_version":1}