REVIEW 1 major objections 4 minor 31 references
The paper proves that the maximum number of edges in a 4-uniform linear hypergraph avoiding the 4-edge path is 5n/4, attained only by disjoint unions of Steiner systems S(2,4,16), and corrects an earlier proof by exhibiting counterexamples
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
For several r-uniform linear hypertrees with four edges, the maximum number of edges in a linear r-uniform hypergraph avoiding them is determined; the 4-uniform 4-edge path case is settled exactly.
T0 review reviewed 2026-08-01 challenge →
load-bearing objection Worth refereeing: P_4^4 result is clean, but the crown lower bound in Proposition 2 quietly assumes an affine plane of order r-1, which fails for r=7. the 1 major comments →
Linear Tur\'an Numbers of Uniform Hypertrees
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
Core claim
The central claim is that the linear Turán number of the 4-uniform path P_4^4 is at most 5n/4, with equality exactly when the hypergraph is a disjoint union of Steiner systems S(2,4,16). More broadly, the paper determines the linear Turán number of the broom B_4^r as (r+1)n/r when S(2,r,r^2) exists, characterizes extremal hypergraphs as disjoint unions of that Steiner system, and gives upper and lower bounds for the crown E_4^r that leave only a constant-factor gap. For the path P_4^r it constructs dense examples from S(2,r,r^2) reaching (r+1)n/r and conjectures sharpness. For r=4, it exhibits counterexamples to a structural claim (V(S_k)=V(H)) in an earlier proof, then gives a new proof: a
What carries the argument
The load-bearing objects are Steiner systems S(2,r,n): linear r-uniform hypergraphs in which every pair of vertices lies in exactly one hyperedge. They saturate the pair-counting upper bound and provide all extremal constructions, including the lower bound for the path and the equality cases for the broom and the 4-uniform path. For the P_4^4 proof, the machinery is the line graph L(H) of the hypergraph: linearity and P_4^4-freeness make L(H) a connected cograph (a graph with no induced path on 4 vertices), 5-regularity makes it 16-regular, and an edge-decomposition of L(H) into n copies of K_5 — one per vertex of H — turns a counting contradiction on the cograph's connected components into
Load-bearing premise
The crown lower bound is stated under only a divisibility condition, but its proof requires an affine plane of order r-1; such planes exist only when r-1 is a prime power, and for r=7 this fails, so the theorem as stated is not established for all r it claims to cover.
What would settle it
Find a connected 4-uniform linear hypergraph on 20 vertices with more than 25 hyperedges and no four hyperedges forming a P_4^4; the paper's proof says this is impossible, so its existence would falsify the bound. Equivalently, exhibit a connected 16-regular cograph on 25 vertices decomposable into 20 edge-disjoint K_5s, which the paper's counting rules out.
If this is right
- If correct, ex_4^lin(n, P_4^4) = 5n/4 is fully resolved for all n admitting a partition into 16-vertex blocks, with a complete equality characterization.
- The exact value ex_r^lin(n, B_4^r) = (r+1)n/r holds whenever S(2,r,r^2) exists, and disjoint unions of that Steiner system are the only extremal hypergraphs.
- The crown E_4^r has (2r-1)n/r as an upper bound, and the new lower construction shows the true value lies within a constant factor, not exactly pinned.
- For every linear r-uniform hypertree T_k^r, the construction shows the linear Turán number is at least n(k-1)/r whenever the divisibility and design-existence conditions are met.
- The counterexamples show the earlier proof of the 4-uniform path bound is not salvageable as written, so the new argument is the justification for the bound.
Where Pith is reading between the lines
- One testable extension: if the line-graph/cograph argument for r=4 generalizes to other r where S(2,r,r^2) exists, the conjectured bound (r+1)n/r for P_4^r may reduce to a similar regularity plus cograph decomposition; the key check is whether the extremal hypergraph must be (r+1)-regular.
- The gap in the crown lower bound — it needs an affine plane of order r-1, not just the stated divisibility condition — suggests the bound may fail for r=7 and motivates a search for alternative designs or a corrected hypothesis.
- The paper's recurring theme, Steiner systems as the unique extremal objects, hints that for many linear hypertrees exact Turán results might follow from design-existence theorems, making the conditional results unconditional for all sufficiently large admissible n.
- A direct project is to decide Conjecture 1 for r=5 or r=8, where S(2,r,r^2) exists, by attempting the same cograph decomposition and checking whether any non-design extremal hypergraphs appear.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies linear Turán numbers of r-uniform linear hypertrees. It proves the exact linear Turán number of the uniform star S_k^r, gives a general lower-bound construction for arbitrary linear hypertrees conditional on the existence of certain Steiner systems, determines the exact extremal value and extremal structure for the broom B_4^r, obtains an upper bound and a lower-bound construction for the crown E_4^r, and provides a lower bound for P_4^r together with a sharp bound for connected P_4^r-free hypergraphs under degree hypotheses. For r=4, the paper exhibits counterexamples to a structural claim in the earlier proof of Zhang and Wang, proves ex_4^{lin}(n,P_4^4) ≤ 5n/4, and characterizes equality as disjoint unions of S(2,4,16).
Significance. The main contribution is the sharp 4-uniform result for P_4^4, with a full extremal characterization, and the exact linear Turán number for the broom B_4^r. The paper also identifies a concrete gap in a previously published proof, which is a useful service to the area. The proofs are elementary and, apart from the issue discussed below, the trace-based case analysis in Theorem 7 appears sound. The extremal characterization via line graphs and cographs is elegant. However, one lower-bound claim, Proposition 2, is overstated because it silently assumes the existence of an affine plane of order r-1; this affects the crown lower-bound claim for infinitely many r but not the central P_4^4 theorem.
major comments (1)
- [§5, Proposition 2] Proposition 2 is stated for all r≥3 under only the divisibility condition (r−1)^2 | (n−r), but its proof begins 'Let A be an affine plane of order q' with q=r−1. An affine plane of order q exists only when S(2,q,q^2) does, and in particular only if q is a prime power or another admissible order. For r=7, q=6, the Bruck–Ryser–Chowla theorem rules out such a plane; the paper itself notes in §1.3 that no S(2,6,36) exists. Thus the construction is undefined for r=7 and for other non-prime-power values of r−1, and the claimed lower bound ex_lin_r(n,E_4^r) ≥ r(n−r)/(r−1) is not established under the stated hypotheses. This is load-bearing for the crown lower-bound claim, though it does not affect Theorem 4 or Theorem 7. I recommend restating Proposition 2 with the explicit existence assumption of an affine plane of order r−1, or equivalently S(2,r−1,(r−1)^2), and marking the lower bound as con
minor comments (4)
- [§7, proof of Theorem 6] In the displayed computation of (r+1)n/r − |E(H)|, the term |T|/r is written as |T|+2/r in the third line. The previous line has |T|/r correctly. The conclusion is unaffected, but the displayed algebra should be corrected.
- [§8.2, extremal characterization in Theorem 7] The sentence 'Since G is a connected cograph, G must be disconnected. Clearly G is m−17 regular' is confusing as written: it should refer to the complement of G, not to G itself. With 'complement' substituted, the component argument is correct.
- [§8, Theorem 7 statement] The equality statement reads 'equality holds if and only if the hypergraphs is disjoint union of Steiner systems'; this should be 'the hypergraph is a disjoint union'.
- [§3, proof of Theorem 2] The sentence 'From the above claim |V(H_i)| ≥ (r−1)k+1 = t+(r−1)' is misstated. The component has |V(H_i)|=t, while a copy of T_r^k would require (r−1)k+1 > t vertices. The comparison should be made between these two quantities, not written as a lower bound on |V(H_i)|.
Circularity Check
No circularity: the proofs are self-contained and the lower-bound constructions are honestly conditional on external design-existence facts.
full rationale
The derivation chain is self-contained rather than circular. The upper bounds in Proposition 1 and Theorems 3, 4, 6, and 7 are proved from the definitions of linearity and degree via handshaking and double-counting, not by assuming the target extremal value. The lower-bound constructions in Theorems 2 and 5 and Proposition 2 explicitly invoke external existence facts—Steiner systems S(2,r,t), S(2,r,r^2), or an affine plane of order r-1—and then verify the relevant forbidden configuration is absent; no fitted parameter is renamed as a prediction. The equality characterizations in Theorems 3 and 7 are genuine proofs: the 'if' direction computes edge counts from the Steiner-system structure, while the 'only if' direction forces regularity and then pair-count equality, thereby deriving the Steiner system rather than assuming it. The self-citations to [1] and [2] are not load-bearing: the crown upper bound in Section 5 is re-proved through Lemmas 3 and 4, and the new P_4^4 result is argued independently. The one notable weakness is Proposition 2, whose stated hypothesis (r-1)^2 | (n-r) does not guarantee the existence of the affine plane of order r-1 used in its construction; for r=7 (or any r with r-1 not a prime power) the construction is undefined. That is a correctness/conditional-existence gap, not circularity, and it does not affect the central r=4 theorem or the upper-bound results.
Axiom & Free-Parameter Ledger
axioms (4)
- domain assumption Steiner systems S(2,r,t) exist for the parameters used in Theorem 2, and S(2,r,r^2) exist for Theorems 3, 5 and the equality cases of Theorems 3 and 7.
- ad hoc to paper An affine plane of order q = r-1 exists in Proposition 2.
- domain assumption Keevash's design existence theorem: for every fixed r, all sufficiently large admissible n admit Steiner systems S(2,r,n).
- standard math Standard cograph facts: a connected P_4-free graph has disconnected complement; clique-decomposition arguments in line graphs.
Cite this review
Pith. "Pith review of Linear Tur\'an Numbers of Uniform Hypertrees." pith.science (2026). https://pith.science/paper/IYCXKDPK
@misc{pith2026260716854,
author = {Pith},
title = {Pith review of: Linear Tur\'an Numbers of Uniform Hypertrees},
year = {2026},
howpublished = {\url{https://pith.science/paper/IYCXKDPK}},
note = {Machine review of arXiv:2607.16854}
}
abstract
A hypergraph is \emph{linear} if every pair of vertices is contained in at most one hyperedge. For a family $\mathcal{F}$ of $r$-uniform hypergraphs, the linear Tur'an number $ex^{\mathrm{lin}}_r(n,\mathcal{F})$ is the maximum number of hyperedges in an $n$-vertex $\mathcal{F}$-free linear $r$-uniform hypergraph. Extending the work of Gy'arf'as, Ruszink'o, and S'ark"ozy on $3$-uniform linear hypertrees, we study linear Tur'an numbers for higher uniformity. We determine the linear Tur'an number of the $r$-uniform linear star $S_k^r$, proving [ex^{\mathrm{lin}}_r(n,S_k^r)\le \frac{n(k-1)}{r},] with equality exactly for $(k-1)$-regular linear $r$-uniform hypergraphs, whenever they exist. We also construct dense $T_k^r$-free hypergraphs showing that, under suitable divisibility and design-existence assumptions, [ex^{\mathrm{lin}}_r(n,T_k^r)\ge \frac{n(k-1)}{r}] for every linear $r$-uniform hypertree $T_k^r$ with $k$ hyperedges. We then study all linear hypertrees with four hyperedges. For the broom $B_4^r$, we prove [ex^{\mathrm{lin}}_r(n,B_4^r)\le \frac{(r+1)n}{r},] and characterize the extremal hypergraphs as disjoint unions of Steiner systems $S(2,r,r^2)$, whenever such systems exist. For the crown $E_4^r$, we establish [ex^{\mathrm{lin}}_r(n,E_4^r)\le \frac{(2r-1)n}{r},] together with a lower-bound construction leaving only a constant-factor gap. For the linear path $P_4^r$, we construct $P_4^r$-free hypergraphs with $(r+1)n/r$ hyperedges and conjecture this is the optimal general bound. We verify the conjecture for connected hypergraphs under suitable degree conditions. Finally, for $r=4$, we identify counterexamples to a key structural claim in a previous proof of Zhang and Wang, give a new proof that [ex^{\mathrm{lin}}_4(n,P_4^4)\le \frac{5n}{4},] and show that equality holds precisely for disjoint unions of Steiner systems $S(2,4,16)$.
Figures
Reference graph
Works this paper leans on
-
[1]
An Upper Bound on the Linear Turán Number ofk-Crowns.arXiv preprint arXiv:2604.10467, 2026
Rajat Adak. An Upper Bound on the Linear Turán Number ofk-Crowns.arXiv preprint arXiv:2604.10467, 2026
Pith/arXiv arXiv 2026
-
[2]
Bounds on Linear Turán Number for Trees
Rajat Adak and Pragya Verma. Bounds on Linear Turán Number for Trees. In Combinatorial Algorithms, pages 16–31, Cham, 2026. Springer Nature Switzerland
2026
-
[3]
The nonexistence of certain finite projective planes.Canadian Journal of Mathematics, 1(1):88–93, 1949
Richard H Bruck and Herbert J Ryser. The nonexistence of certain finite projective planes.Canadian Journal of Mathematics, 1(1):88–93, 1949
1949
-
[4]
Crowns in linear3-graphs.arXiv preprint arXiv:2107.14713, 2021
Alvaro Carbonero, Willem Fletcher, Jing Guo, András Gyárfás, Rona Wang, and Shiyu Yan. Crowns in linear3-graphs.arXiv preprint arXiv:2107.14713, 2021
Pith/arXiv arXiv 2021
-
[5]
Crowns in linear3-graphs of minimum degree4.The Electronic Journal of Combinatorics, pages P4–17, 2022
Alvaro Carbonero, Willem Fletcher, Jing Guo, András Gyárfás, Rona Wang, and Shiyu Yan. Crowns in linear3-graphs of minimum degree4.The Electronic Journal of Combinatorics, pages P4–17, 2022
2022
-
[6]
Combinatorial problems.Canadian Journal of Mathematics, 2:93–99, 1950
Sarvadaman Chowla and Herbert John Ryser. Combinatorial problems.Canadian Journal of Mathematics, 2:93–99, 1950
1950
-
[7]
Linear Turán Numbers ofLinearCyclesandCycle-CompleteRamseyNumbers.Combinatorics, Probability and Computing, 27(3):358–386, 2018
Clayton Collier-Cartaino, Nathan Graber, and Tao Jiang. Linear Turán Numbers ofLinearCyclesandCycle-CompleteRamseyNumbers.Combinatorics, Probability and Computing, 27(3):358–386, 2018
2018
-
[8]
An Erdős– Gallai type theorem for uniform hypergraphs.European Journal of Combinatorics, 69:159–162, 2018
Akbar Davoodi, Ervin Győri, Abhishek Methuku, and Casey Tompkins. An Erdős– Gallai type theorem for uniform hypergraphs.European Journal of Combinatorics, 69:159–162, 2018
2018
-
[9]
On maximal paths and circuits of graphs.Acta Math
Paul Erdős and Tibor Gallai. On maximal paths and circuits of graphs.Acta Math. Acad. Sci. Hungar. v10, pages 337–356, 1959
1959
-
[10]
Extremal problems in graph theory
Paul Erdős. Extremal problems in graph theory. InTheory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pages 29–36, 1964
1963
-
[11]
Improved Upper Bound on the Linear Turán Number of the Crown.arXiv preprint arXiv:2109.02729, 2021
Willem Fletcher. Improved Upper Bound on the Linear Turán Number of the Crown.arXiv preprint arXiv:2109.02729, 2021
Pith/arXiv arXiv 2021
-
[12]
Turán type problems.Surveys in combinatorics, 166:253–300, 1991
Zoltán Füredi. Turán type problems.Surveys in combinatorics, 166:253–300, 1991
1991
-
[13]
Exact solution of the hypergraph Turán problem fork-uniform linear paths.Combinatorica, 34(3):299–322, 2014
Zoltán Füredi, Tao Jiang, and Robert Seiver. Exact solution of the hypergraph Turán problem fork-uniform linear paths.Combinatorica, 34(3):299–322, 2014
2014
-
[14]
The history of degenerate (bipartite) ex- tremal graph problems
Zoltán Füredi and Miklós Simonovits. The history of degenerate (bipartite) ex- tremal graph problems. InErdős centennial, pages 169–264. Springer, 2013
2013
-
[15]
Chapman and Hall/CRC, 2018
Dániel Gerbner and Balázs Patkós.Extremal finite set theory. Chapman and Hall/CRC, 2018
2018
-
[16]
Linear Turán numbers of acyclic triple systems.European Journal of Combinatorics, 99:103435, 2022
András Gyárfás, Miklós Ruszinkó, and Gábor N Sárközy. Linear Turán numbers of acyclic triple systems.European Journal of Combinatorics, 99:103435, 2022
2022
-
[17]
Turán and Ramsey numbers in linear triple systems.Discrete Mathematics, 344(3):112258, 2021
András Gyárfás and Gábor N Sárközy. Turán and Ramsey numbers in linear triple systems.Discrete Mathematics, 344(3):112258, 2021
2021
-
[18]
The linear Turán number of small triple systems or why is the wicket interesting?Discrete Mathematics, 345(11):113025, 2022
András Gyárfás and Gábor N Sárközy. The linear Turán number of small triple systems or why is the wicket interesting?Discrete Mathematics, 345(11):113025, 2022. Linear Turán Numbers of Uniform Hypertrees 27
2022
-
[19]
Hypergraph extensions of the Erdős-Gallai theorem.European Journal of Combinatorics, 58:238–246, 2016
Ervin Győri, Gyula Y Katona, and Nathan Lemons. Hypergraph extensions of the Erdős-Gallai theorem.European Journal of Combinatorics, 58:238–246, 2016
2016
-
[20]
Hypergraph Turán Problems.Surveys in combinatorics, 392:83– 140, 2011
Peter Keevash. Hypergraph Turán Problems.Surveys in combinatorics, 392:83– 140, 2011
2011
-
[21]
The existence of designs.arXiv preprint arXiv:1401.3665, 2014
Peter Keevash. The existence of designs.arXiv preprint arXiv:1401.3665, 2014
Pith/arXiv arXiv 2014
-
[22]
Turán numbers for hypergraph star forests
Omid Khormali and Cory Palmer. Turán numbers for hypergraph star forests. European Journal of Combinatorics, 102:103506, 2022
2022
-
[23]
Minimal paths and cycles in set systems
Dhruv Mubayi and Jacques Verstraëte. Minimal paths and cycles in set systems. European Journal of Combinatorics, 28(6):1681–1693, 2007
2007
-
[24]
Triple systems with no six points carry- ing three triangles.Combinatorics (Keszthely, 1976), Coll
Imre Z Ruzsa and Endre Szemerédi. Triple systems with no six points carry- ing three triangles.Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai, 18(939-945):2, 1978
1976
-
[25]
Turán and Ramsey numbers in linear triple systems II.Discrete Mathematics, 346(1):113182, 2023
Gábor N Sárközy. Turán and Ramsey numbers in linear triple systems II.Discrete Mathematics, 346(1):113182, 2023
2023
-
[26]
On the Turán Number of the Linear3-GraphC 13.The Electronic Journal of Combinatorics, pages P3–46, 2022
Chaoliang Tang, Hehui Wu, Shengtong Zhang, and Zeyu Zheng. On the Turán Number of the Linear3-GraphC 13.The Electronic Journal of Combinatorics, pages P3–46, 2022
2022
-
[27]
Egy gráfelméleti szélsoértékfeladatról.Mat
Paul Turán. Egy gráfelméleti szélsoértékfeladatról.Mat. Fiz. Lapok, 48(3):436, 1941
1941
-
[28]
Generalized crowns in linear r-graphs.The Electronic Journal of Combinatorics, pages P1–29, 2025
Lin-Peng Zhang, Hajo Broersma, and Ligong Wang. Generalized crowns in linear r-graphs.The Electronic Journal of Combinatorics, pages P1–29, 2025
2025
-
[29]
Turán numbers of general star forests in hypergraphs.Discrete Mathematics, 348(1):114219, 2025
Lin-Peng Zhang, Hajo Broersma, and Ligong Wang. Turán numbers of general star forests in hypergraphs.Discrete Mathematics, 348(1):114219, 2025
2025
-
[30]
The Linear Turán Numbers of Acyclic Linear 4-graphs.Acta Mathematicae Applicatae Sinica, English Series, pages 1–13, 2025
Lin-peng Zhang and Li-gong Wang. The Linear Turán Numbers of Acyclic Linear 4-graphs.Acta Mathematicae Applicatae Sinica, English Series, pages 1–13, 2025
2025
-
[31]
Turán problems for star-path forests in hyper- graphs.Discrete Mathematics, 348(11):114592, 2025
Junpeng Zhou and Xiying Yuan. Turán problems for star-path forests in hyper- graphs.Discrete Mathematics, 348(11):114592, 2025
2025
This paper was first reviewed by deepseek-v4-flash on August 1, 2026.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.