Pith. sign in

REVIEW 2 major objections 6 minor 20 references

Tur\'an type problems for a fixed graph and a linear forest

T0 review · 2 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper determines the exact Turán number for any linear forest H plus any fixed graph F with chromatic number at least 3.

desk verdict Valuable equal-path and kP_3 results, but the general linear forest theorems rest on a bad inequality in Lemma 4.1. read the letter →

arxiv 2507.11034 v1 pith:HWUZQCSG submitted 2025-07-15 math.CO

Haixiang Zhang , Xiamiao Zhao , Mei Lu This is my paper · ORCID
classification math.CO MSC 05C3505C38
keywords Turánnumberlinearforestdisjointpathschromaticedgecontrolforbiddensubgraphsextremalgraphs
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

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.

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 (2)
  1. [Section 4.2, Lemma 4.1] 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.
  2. [Section 2.2, Lemma 2.5] 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.
minor comments (6)
  1. [Section 4.2, before Lemma 4.3] 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′.
  2. [Theorem 1.11(ii)] 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.
  3. [Throughout Sections 2 and 4] 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.
  4. [Theorems 1.11 and 1.12] 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.
  5. [Introduction and References] 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.
  6. [Proofs of Theorem 1.7 and 1.12] There are typographical errors 'subgrapgh' and 'contraction' that should be corrected to 'subgraph' and 'contradiction'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the target formulas are derived from external theorems and new structural lemmas; the only self-citations are contextual, not load-bearing.

full rationale

The paper's derivation chain is self-contained with respect to its inputs. The main theorems (1.6, 1.7, 1.9, 1.11, 1.12) express ex(n,{H,F}) as (ell-1)(n-ell+1) plus additive terms built from exact auxiliary Turan numbers such as ex(ell-1, G1(F)) and ex(ell-1, G2(F)); these are genuine extremal values of graph families defined from F, not fitted parameters, and the lower-bound constructions in Sections 2.1 and 4.1 are each checked to be {H,F}-free without invoking the target value. The upper bounds rest on new structural lemmas (Lemma 2.6 and its analogue Lemma 4.6) whose proofs use external results: Erdos-Gallai (Theorem 1.2), Bushaw-Kettle (Theorems 1.3-1.4, Lemmas 2.1 and 2.4), Lidicky-Liu-Palmer (Theorem 1.5), and Turan/Simonovits. Lemma 2.5's induction on k has an external base case (Lemma 2.4) and does not assume the bound |A| <= k*floor(ell/2)-1 as a hypothesis. The only self-citations are [13] (Lu-Kang) and [14] (Luo-Zhao-Lu, two of the present authors); both appear solely in the introduction as prior-work context and are never invoked as proof premises, so they are not load-bearing. The skeptical concern about Lemma 4.1 is a correctness issue, not circularity: the displayed chain e(G) - C(3ell',2) - ex(n,H1) >= (ell-1)(n-ell+1) - C(3ell',2) - ell_1 n >= ell'n - 6ell^2 algebraically requires n <= 6ell^2 - (ell-1)^2 - C(3ell',2), which fails exactly when n is large, so the stated lower bound is not established. Even if that bound fails, the proof derives the formula from an overly strong bound rather than assuming the formula, so the circularity score is unaffected. No step renames a known result as a new organization, and no uniqueness or ansatz is imported from the authors' own prior work. Score 0.

Assumptions & free parameters 0 free parameters · 9 assumptions · 0 invented entities

No data fitting appears; the additive constants are exact auxiliary Turan numbers or 0/1 values dictated by structural lemmas. The axioms are standard theorems in extremal graph theory plus the explicit large-n assumptions. The paper introduces no physical or mathematical entities beyond standard graph parameters (edge control number is a definition, not a postulated entity).

assumptions (9)
  • standard math Turan's theorem: ex(n, K_r) = e(T(n, r-1))
    Used for the F=K_r corollaries and to evaluate ex(|A|, G1(F)) when F is a complete graph.
  • standard math Erdos-Gallai theorem: ex(n, P_l) <= (l-2)n/2
    Used in Lemma 2.2 and Lemma 2.3 to bound edges in sets such as D and D3; cited as Theorem 1.2.
  • standard math Bushaw-Kettle theorem for ex(n, kP_l)
    Central external benchmark; used for the lower bound and for bounding edges in (k-1)P_l-free graphs in Lemma 2.2; cited as Theorem 1.3.
  • standard math Lidicky-Liu-Palmer theorem for ex(n, union of P_{l_i})
    Used in Section 4 to compare e(G) with ex(n, H') and ex(n, H_1); cited as Theorem 1.5.
  • standard math Simonovits stability theorem and Gorgol bound for disjoint unions
    Background for extremal structure and for the bound ex(m, pG) <= ... ; cited as Theorem 1.1 and [15].
  • standard math Base case |A| <= 2*floor(l/2)-1 for k=2 (from Bushaw-Kettle, Lemma 2.4)
    Used as the base of the induction in Lemma 2.5; cited as [3].
  • domain assumption The complete bipartite graph K_{k*floor(l/2)-1, n-k*floor(l/2)+1} is kP_l-free
    Used to set the lower bound e(G) >= (k*floor(l/2)-1)(n-k*floor(l/2)+1) in equation (1).
  • domain assumption n is sufficiently large (explicit bounds in each theorem)
    All exact formulas are stated for n above explicit thresholds; the finite-n behavior may differ, as the paper notes with the still-open Yuan-Zhang conjecture.
  • domain assumption F is a finite simple graph with chi(F) >= 3 and, when beta1(F)=1, no isolated vertices
    The paper reduces to the no-isolate case for beta1(F)=1 by deleting isolated vertices; this is stated before Theorem 1.7.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Tur\'an type problems for a fixed graph and a linear forest." pith.science (2026). https://pith.science/paper/HWUZQCSG

@misc{pith2026250711034,
  author       = {Pith},
  title        = {Pith review of: Tur\'an type problems for a fixed graph and a linear forest},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HWUZQCSG}},
  note         = {Machine review of arXiv:2507.11034}
}
abstract

Let $\mathscr{F}$ be a family of graphs. A graph $G$ is $\mathscr{F}$-free if $G$ does not contain any $F\in \mathscr{F}$ as a subgraph. The Tur\'an number, denoted by $ex(n, \mathscr{F})$, is the maximum number of edges in an $n$-vertex $\mathscr{F}$-free graph. Let $F $ be a fixed graph with $ \chi(F) \geq 3 $. A forest $H$ is called a linear forest if all components of $H$ are paths. In this paper, we determined the exact value of $ex(n, \{H, F\}) $ for a fixed graph $F$ with $\chi(F)\geq 3$ and a linear forest $H$ with at least $2$ components and each component with size at least $3$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 19 canonical work pages

  1. [1]

    Alon and P

    N. Alon and P. Frankl. Tur´ an graphs with bounded matching number. Journal of Com- binatorial Theory, Series B , 165:223–229, 2024

    work page 2024

  2. [2]

    Bielak and S

    H. Bielak and S. Kieliszek. The Tur´ an number of the graph 2P5. Discussiones Mathemat- icae Graph Theory, 36(3):683–694, 2016

    work page 2016

  3. [3]

    Bushaw and N

    N. Bushaw and N. Kettle. Tur´ an numbers of multiple paths and equibipartite forests. Combinatorics, Probability and Computing , 20(6):837–853, 2011

    work page 2011

  4. [4]

    J. Deng, J. Hou, and Q. Zeng. The Tur´ an number of three disjoint paths. Discussiones Mathematicae Graph Theory, 44(4):1513–1537, 2024. 24

    work page 2024

  5. [5]

    C. Dou, B. Ning, and X. Peng. The number of edges in graphs with bounded clique number and circumference. arXiv preprint arXiv:2410.06449 , 2024

    arXiv 2024

  6. [6]

    Erd˝ os and T

    P. Erd˝ os and T. Gallai. On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hungar, 10:337–356, 1959

    work page 1959

  7. [7]

    Fang and L

    X. Fang and L. You. The Tur´ an number of P9 ∪ P7. Computational and Applied Mathe- matics, 43(5):291, 2024

    work page 2024

  8. [8]

    Feng and Y

    L. Feng and Y. Hu. The Tur´ an number of the graph 3P5. Filomat, 34(10):3395–3410, 2020

    work page 2020

Show all 20 references
  1. [9]

    D. Gerbner. On Tur´ an problems with bounded matching number. Journal of Graph Theory, 106(1):23–29, 2024

    2024

  2. [10]

    I. Gorgol. Tur´ an numbers for disjoint copies of graphs. Graphs and Combinatorics , 27(5):661–667, 2011

    2011

  3. [11]

    Y. Lan, T. Li, Y. Shi, and J. Tu. The Tur´ an number of star forests. Applied Mathematics and Computation, 348:270–274, 2019

    2019

  4. [12]

    Lidick` y, H

    B. Lidick` y, H. Liu, and C. Palmer. On the Tur´ an number of forests.Electron. J. Combin., 20(2): Paper 62, 2013

    2013

  5. [13]

    Lu and L

    Y. Lu and L. Kang. Extremal problems for star forests and cliques. arXiv preprint arXiv:2404.05942, 2024

    2024

  6. [14]

    H. Luo, X. Zhao, and M. Lu. Tur´ an number of complete bipartite graphs with bounded matching number. Discrete Mathematics, 347:113959, 2024

    2024

  7. [15]

    Simonovits

    M. Simonovits. A method for solving extremal problems in graph theory, stability prob- lems. In Theory of Graphs (Proc. Colloq., Tihany, 1966) , 279–319. 1968

    1966

  8. [16]

    P. Tur´ an. On the theory of graphs. Colloquium Mathematicae, 3(1):19–30, 1954

    1954

  9. [17]

    Yin and Y

    J.-H. Yin and Y. Rao. Tur´ an number forpSr. Journal of Combinatorial Mathematics and Combinatorial Computing , 97:241 – 245, 2016

    2016

  10. [18]

    Yuan and X.-D

    L.-T. Yuan and X.-D. Zhang. The Tur´ an number of disjoint copies of paths. Discrete Mathematics, 340(2):132–139, 2017

    2017

  11. [19]

    Yuan and X.-D

    L.-T. Yuan and X.-D. Zhang. Tur´ an numbers for disjoint paths.Journal of Graph Theory, 98(3):499–524, 2021

    2021

  12. [20]

    Zhang and L

    L.-P. Zhang and L. Wang. The Tur´ an numbers of special forests. Graphs and Combina- torics, 38(3):84, 2022. 25

    2022

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.