pith. sign in

arxiv: 2601.17325 · v2 · submitted 2026-01-24 · 🧮 math.CO · cs.DM

Bounds on Linear Tur\'{a}n Number for Trees

Rajat Adak , Pragya Verma This is my paper

Pith reviewed 2026-05-16 11:34 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords linear Turán numberr-uniform hypergraphshypertreesacyclic hypergraphsextremal combinatoricsforbidden subhypergraphs
0
0 comments X

The pith

Any linear r-uniform hypergraph on n vertices without the hypertree B_4^r has at most (r+1)n/r edges, with extremal examples fully characterized.

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

The paper extends linear Turán problems to r-uniform acyclic hypergraphs by giving a general construction that produces linear hypergraphs with n(k-1)/r edges avoiding any given k-edge tree. For the specific 4-edge tree B_4^r, formed by adding an edge to a degree-one vertex in S_3^r, the authors prove that no linear hypergraph can have more than (r+1)n/r edges without containing it and describe all the maximal examples. They provide a separate upper bound for the crown tree E_4^r and a construction achieving (r+1)n/r edges for the path tree P_4^r along with a conjecture for its exact number.

Core claim

We prove the exact bound ex_r^lin(n,B_4^r)≤(r+1)n/r and characterize the extremal hypergraph class, where B_4^r is formed from S_3^r by appending a hyperedge incident to a degree-one vertex.

What carries the argument

The forbidden hypertree B_4^r, obtained by appending one hyperedge to a degree-one vertex of S_3^r, which is used to bound the size of linear r-uniform hypergraphs avoiding it.

Load-bearing premise

Mild divisibility and existence assumptions are required for the general lower-bound construction that achieves n(k-1)/r edges while avoiding any k-edge tree.

What would settle it

A linear r-uniform hypergraph on n vertices with more than (r+1)n/r hyperedges that contains no copy of B_4^r would disprove the upper bound.

Figures

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

Figure 1
Figure 1. Figure 1: Configurations of B r 4 and E r 4 (in the figure r = 5). Alongside these expansions, there is a notable non-expansion configuration known as the crown Er 4 , consisting of three pairwise disjoint hyperedges together with a fourth hyperedge, called the base, that intersects each of the other three. Crowns have been studied in a variety of settings in [1],[2],[17], and [19]. In a related direction, Fletcher … view at source ↗
read the original abstract

A hypergraph $H$ is said to be \emph{linear} if every pair of vertices lies in at most one hyperedge. Given a family $\mathcal{F}$ of $r$-uniform hypergraphs, an $r$-uniform hypergraph $H$ is \emph{$\mathcal{F}$-free} if it contains no member of $\mathcal{F}$ as a subhypergraph. The \emph{linear Tur\'{a}n number} $ex_r^{\mathrm{lin}}(n,\mathcal{F})$ denotes the maximum number of hyperedges in an $\mathcal{F}$-free linear $r$-uniform hypergraph on $n$ vertices. Gy\'arf\'as, Ruszink\'o, and S\'ark\"ozy~[\emph{Linear Tur\'an numbers of acyclic triple systems}, European J.\ Combin.\ (2022)] initiated the study of bounds on the linear Tur\'an number for acyclic $3$-uniform linear hypergraphs. In this paper, we extend the study of linear Tur\'{a}n numbers for acyclic systems to higher uniformity. We first give a construction for any linear $r$-uniform tree with $k$ edges that yields the lower bound $ ex_r^{\mathrm{lin}}(n,T_k^r)\ge {n(k-1)}/{r}, $ under mild divisibility and existence assumptions. Next, we study hypertrees with four edges. We prove the exact bound $ ex_r^{\mathrm{lin}}(n,B_4^r)\le {(r+1)n}/{r} $ and characterize the extremal hypergraph class, where $B_4^r$ is formed from $S_3^r$ by appending a hyperedge incident to a degree-one vertex. We also prove the bound $ ex_r^{\mathrm{lin}}(n,E_4^r)\le {(2r-1)n}/{r} $ for the crown $E_4^r$. Finally, we give a construction showing $ ex_r^{\mathrm{lin}}(n,P_4^r)\ge {(r+1)n}/{r} $ under suitable assumptions and conclude with a conjecture on sharp upper bound for $P_4^r$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper extends linear Turán numbers ex_r^lin(n,F) from the 3-uniform acyclic case to general r-uniformity. It gives a general construction yielding the lower bound ex_r^lin(n,T_k^r) ≥ n(k-1)/r for any linear r-uniform tree T_k^r (under mild divisibility and existence assumptions). For the specific 4-edge hypertree B_4^r (formed by attaching one extra edge to a leaf of S_3^r), it proves the exact upper bound ex_r^lin(n,B_4^r) ≤ (r+1)n/r together with a characterization of the extremal linear hypergraphs. It also establishes the upper bound ex_r^lin(n,E_4^r) ≤ (2r-1)n/r for the crown and a matching-order construction ex_r^lin(n,P_4^r) ≥ (r+1)n/r, ending with a conjecture that the latter is sharp.

Significance. If the proofs hold, the work provides the first exact determination of a linear Turán number for a 4-edge r-uniform tree beyond the 3-uniform setting, together with an explicit extremal characterization. The general tree construction and the clean charging argument for B_4^r are reusable techniques that strengthen the foundation for studying larger acyclic families. The results are parameter-free and rest on direct counting and structural arguments that reference only the cited 2022 predecessor.

minor comments (3)
  1. [§2] §2 (general construction): the divisibility and existence assumptions for the lower bound are stated but not quantified; adding a sentence on the range of n for which they hold would improve readability.
  2. [Introduction] Definition of B_4^r: while the abstract describes it as S_3^r plus one pendant edge, a formal vertex/edge listing or small diagram in the introduction would help readers track the charging argument in the upper-bound proof.
  3. [Final section] The conjecture for P_4^r is stated without any supporting partial upper-bound evidence; a brief remark explaining why the B_4^r method does not immediately apply would clarify the open status.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of our manuscript. The summary accurately describes our extension of linear Turán numbers to r-uniform acyclic hypergraphs, the general lower-bound construction, the exact result with characterization for B_4^r, the bound for E_4^r, and the construction plus conjecture for P_4^r. We are pleased with the recommendation for minor revision.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's central results—an exact upper bound ex_r^lin(n,B_4^r) ≤ (r+1)n/r with extremal characterization, plus matching lower bounds for trees and other hypertrees—are obtained via direct constructions under divisibility assumptions and structural analysis of maximal linear hypergraphs avoiding the defined forbidden subhypergraphs (B_4^r formed from S_3^r by leaf attachment, etc.). The only external reference is to the independent 2022 Gyárfás–Ruszinkó–Sárközy paper on the 3-uniform case (different authors), which is used only to motivate the extension and is not load-bearing for the new proofs. No self-definitional steps, fitted parameters renamed as predictions, ansatz smuggling, or uniqueness theorems imported from the authors' own prior work appear. The derivation chain is self-contained and externally falsifiable via the explicit constructions and counting arguments.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard definitions of linear hypergraphs and subhypergraph containment plus mild divisibility conditions for constructions; no free parameters are fitted to data and no new entities are postulated.

axioms (2)
  • standard math Standard definitions of linear r-uniform hypergraphs and subhypergraph containment
    Invoked in the opening definitions of ex_r^lin and F-free.
  • domain assumption Existence of certain regular linear hypergraphs under divisibility conditions
    Required for the general lower-bound construction.

pith-pipeline@v0.9.0 · 5706 in / 1434 out tokens · 52975 ms · 2026-05-16T11:34:06.552867+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. An Upper Bound on the Linear Tur\'{a}n Number of $k$-Crowns

    math.CO 2026-04 unverdicted novelty 6.0

    An upper bound is established for the linear Turán number ex_r^lin(n, C_{1,k}^r) of k-crowns in linear r-graphs.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages · cited by 1 Pith paper

  1. [1]

    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

    work page arXiv 2021

  2. [2]

    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

    work page 2022

  3. [3]

    Linear turán numbers of linear cycles and cycle-complete ramsey numbers.Combinatorics, Probability and Computing, 27(3):358–386, 2018

    Clayton Collier-Cartaino, Nathan Graber, and Tao Jiang. Linear turán numbers of linear cycles and cycle-complete ramsey numbers.Combinatorics, Probability and Computing, 27(3):358–386, 2018

    work page 2018

  4. [4]

    Extremal problems in graph theory

    P Erdős. Extremal problems in graph theory. in in theory of graphs and its appli- cations. InProc. Sympos. Smolenice, pages 29–36, 1965

    work page 1965

  5. [5]

    On maximal paths and circuits of graphs.Acta Math

    Pál Erdős and Tibor Gallai. On maximal paths and circuits of graphs.Acta Math. Acad. Sci. Hungar. v10, pages 337–356, 1959

    work page 1959

  6. [6]

    Improved upperbound onthe linear tur\’annumber ofthe crown

    WillemFletcher. Improved upperbound onthe linear tur\’annumber ofthe crown. arXiv preprint arXiv:2109.02729, 2021

    work page arXiv 2021

  7. [7]

    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

    work page 1991

  8. [8]

    Exact solution of the hypergraph turán problem for k-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 for k-uniform linear paths.Combinatorica, 34(3):299–322, 2014

    work page 2014

  9. [9]

    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

    work page 2013

  10. [10]

    Chapman and Hall/CRC, 2018

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

    work page 2018

  11. [11]

    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

    work page 2022

  12. [12]

    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

    work page 2016

  13. [13]

    Hypergraph turan problems.Surveys in combinatorics, 392:83–140, 2011

    Peter Keevash. Hypergraph turan problems.Surveys in combinatorics, 392:83–140, 2011

    work page 2011

  14. [14]

    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

    work page 2022

  15. [15]

    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

    work page 2007

  16. [16]

    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

    work page 1976

  17. [17]

    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

    work page 2022

  18. [18]

    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

    work page 1941

  19. [19]

    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

    work page 2025

  20. [20]

    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

    work page 2025

  21. [21]

    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

    work page 2025

  22. [22]

    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

    work page 2025