Pith. sign in

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 →

arxiv 2607.16854 v1 pith:IYCXKDPK submitted 2026-07-18 math.CO cs.DM

Linear Tur\'an Numbers of Uniform Hypertrees

classification math.CO cs.DM MSC 05C6505C3505B05
keywords linear Turán numberuniform linear hypergraphhypertreeSteiner systemextremal hypergraph4-uniform pathcrownbroom
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The reading

This paper is trying to settle the linear Turán number for several uniform hypertrees with four hyperedges: the broom, the crown, and the 4-edge path. Its sharpest result is for the 4-uniform path P_4^4, where it shows that any P_4^4-free linear 4-uniform hypergraph on n vertices has at most 5n/4 hyperedges, with equality exactly for disjoint unions of the Steiner system S(2,4,16). This is the 4-uniform case of a conjecture that would unify bounds for paths of low edge count, and it corrects a previous proof by giving explicit counterexamples to a key structural claim. Why care: exact answers in linear Turán theory are rare, and the extremal objects turn out to be classical designs, connecting extremal hypergraph theory to design theory.

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.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

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

These are editorial extensions of the paper, not claims the author makes directly.

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

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 4 minor

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)
  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)
  1. [§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.
  2. [§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.
  3. [§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'.
  4. [§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

0 steps flagged

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

0 free parameters · 4 axioms · 0 invented entities

The paper introduces no new entities, forces, or fitted parameters. Its assumptions are design-theoretic existence conditions (Steiner systems, affine planes) plus standard math. The only real audited issue is that Proposition 2 uses an affine plane without stating that existence as a hypothesis.

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.
    The lower-bound constructions and equality characterizations are explicitly conditional on these designs. For r=4, S(2,4,16) exists as an affine plane of order 4; for general r the existence is not guaranteed, so the theorems are conditional.
  • ad hoc to paper An affine plane of order q = r-1 exists in Proposition 2.
    The proof of Proposition 2 invokes an affine plane of order q, but the proposition's statement only assumes divisibility. For r=7 (q=6), Bruck–Ryser–Chowla rules out such a plane, so the proof does not cover that case as stated.
  • domain assumption Keevash's design existence theorem: for every fixed r, all sufficiently large admissible n admit Steiner systems S(2,r,n).
    Cited in the introduction to make the conditional statements non-vacuous for large n. It is an external existence theorem, not proved in the paper.
  • standard math Standard cograph facts: a connected P_4-free graph has disconnected complement; clique-decomposition arguments in line graphs.
    Used in the extremal characterization of Theorem 7 (Section 8.2) through the line graph of the hypergraph. These are well-known graph-theoretic facts.

reviewed 2026-08-01 · how reviews work

0 comments
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}
}
Share X Bluesky LinkedIn Reddit HN
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

Figures reproduced from arXiv: 2607.16854 by Pragya Verma, Rajat Adak.

Figure 1
Figure 1. Figure 1: The four linear r-uniform configurations with four hyperedges studied in this paper. The diagrams are schematic: the unlabelled points in each hyperedge represent its remaining vertices. 1.3 Steiner Systems A Steiner system S(t, r, n) consists of an n-element vertex set together with a collection of r-element blocks such that every t-element subset of the vertex set is contained in exactly one block. In pa… view at source ↗
Figure 2
Figure 2. Figure 2: A connected linear 4-uniform P 4 4 -free hypergraph with ∆(H) = 6 and δ(H) ≥ 2 [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: A connected linear 4-uniform P 4 4 -free hypergraph with ∆(H) = 7, δ(H) ≥ 2 H (in [PITH_FULL_IMAGE:figures/full_fig_p019_3.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

31 extracted references · 4 linked inside Pith

  1. [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

  2. [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

  3. [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

  4. [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

  5. [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

  6. [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

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

  8. [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

  9. [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

  10. [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

  11. [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

  12. [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

  13. [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

  14. [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

  15. [15]

    Chapman and Hall/CRC, 2018

    Dániel Gerbner and Balázs Patkós.Extremal finite set theory. Chapman and Hall/CRC, 2018

  16. [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

  17. [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

  18. [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

  19. [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

  20. [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

  21. [21]

    The existence of designs.arXiv preprint arXiv:1401.3665, 2014

    Peter Keevash. The existence of designs.arXiv preprint arXiv:1401.3665, 2014

  22. [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

  23. [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

  24. [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

  25. [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

  26. [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

  27. [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

  28. [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

  29. [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

  30. [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

  31. [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

This paper was first reviewed by deepseek-v4-flash on August 1, 2026.