The linear Turán number of the 3-graph P 5 P_{5}
Chaoliang Tang, Hehui Wu, Junchi Zhang · 2026
Read The linear Turán number of the 3-graph P 5 P_{5} by Chaoliang Tang, Hehui Wu, Junchi Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-19068.txt.
Introduction
Chaoliang Tang, Hehui Wu, and Junchi Zhang pin down a Turán type bound for sparse hypergraphs. A linear 3-graph links triples of points so that any two links share at most one point. The question: how many links can such a graph hold with no path of length five hiding inside?
The team proves the count stays under a fixed share of the point count, and they name the only graph that hits the bound exactly. It is built from copies of one small graph with eleven points. Sharp bounds with a named extremal case close a problem fully, a prized outcome in combinatorics.
Catalog record
| CREATOR | Chaoliang Tang, Hehui Wu, Junchi Zhang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-19068
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The linear Turán number of the 3-graph P 5 P_{5} Chaoliang Tang, Hehui Wu, Junchi Zhang Abstract We prove that for any linear 3-graph on n n vertices without a path of length 5, the number of edges is at most 15 11 n \frac{15}{11}n , and the equality holds if and only if the graph is the disjoint union of G 0 G_{0} , a graph with 11 vertices and 15 edges. Thus, e x L ( n , P 5 ) ≤ 15 11 n ex_{L}(n,P_{5})\leq\frac{15}{11}n , and the equality holds if and only if 11 | n 11|n . Keyword: 3-uniform linear hypergraph; linear Turán number; linear path; P_{5} 1 Introduction A k -uniform hypergraph , or a k -graph , is a pair (V,E) such that V is the set of vertices, and E is a family of k -vertex subsets of V . A linear 3-graph G=(V,E) is a 3-uniform hypergraph such that any two vertices are contained in at most one edge. Given a linear 3-graph F , the linear Turán number ex_{L}(n,F) is the maximum number of edges in an F -free linear 3-graph on n vertices. Determining the Turán number is a fundamental problem in extremal graph theory. A celebrated result is the famous (6,3)-theorem proved by Ruzsa and Szemerédi [ 10 ] that ex_{L}(n,C_{3})=o(n^{2}) , where the cycle C_{3} is the unique linear 3-graph with 3 edges and 6 vertices. Determining the linear Turán number of graphs seems surprisingly hard, even for acyclic cases. Recently Gyárfás et al. initiated the study of linear Turán number of some trees in [ 7 ] , where Gyárfás et al. proved that ex_{L}(n,P_{k})\leq 1.5kn and determined the linear Turán number of P_{3},P_{4},B_{4} and matchings. In [ 11 ] , Tang et al. proved that the linear Turán number of the Crown graph E_{4} is 1.5n and completed the determination of linear Turán number for acyclic 3-graphs with at most 4 edges. The graphs mentioned are demonstrated as below. C_{3} P_{3} P_{4} B_{4} E_{4} C_{5} A Berge path of length k in a hypergraph consists of k hyperedges h_{1},h_{2},...,h_{k} such that \{v_{i},v_{i+1}\}\subseteq h_{i} for all i\in[k] , where v_{1},v_{2},...,v_{k+1} are k+1 distinct vertices. In [ 9 ] , Győri et al. showed that an n -vertex linear 3-graph without a Berge path of length k\geq 4 as a subgraph has at most \frac{k-1}{6}n edges. Note that there are more than one 3-uniform Berge Path with length n and some of them is not acyclic. A linear path of length k , denoted by P_{k} , is the only acyclic Berge path, which has 2k+1 vertices. In the same paper, Győri et al. asked the linear Turán number of linear paths with length larger than 4 (see 1.1 , or Conjecture 3.4 in [ 9 ] ). Conjecture 1.1 . Let G be an n vertex linear 3-graph, containing no linear path of length k\geq 5 . Then the number of edges in G is at most \frac{k}{3}n+cn , for some universal constant c. Note that the bound in 1.1 is asymptotic sharp for infinitely many pairs of (n,k) . A maximal partial triple system , MPTS(m) , is a linear triple system on m points whose triples cover the maximum number of pairs of points. Note that the disjoint union of MPTS(2k) does not contain a path of length k (which has 2k+1 vertices), and it has roughly \frac{(k-1)}{3}n . Particularly, if m\equiv 1,3\mod{6} , it is known as Steiner Triple System, STS(m) , which has \frac{(m-1)m}{6} . It is also known that an MPTS(m) has exactly \frac{(m-1)m-8}{6} edges for m\equiv 5\mod{6} , \frac{(m-2)m}{6} edges for m\equiv 0,2\mod{6} , and \frac{(m-2)m-2}{6} edges for m\equiv 4\mod{6} . The main result of this paper is to give the linear Turan number of linear path with length 5, for which the extremal graph is not disjoint union of maximal partial triple system MPTS(10) . The later graph has \frac{13}{10}n edges. Theorem 1.2 . Let G be an n vertex linear 3-graph, containing no P_{5} . Then the number of edges in G is at most \frac{15}{11}n , and the equality holds if and only if the graph is the disjoint union of G_{0} , a graph with 11 vertices and 15 edges as shown below. v_{1} v_{2} v_{3} v_{4} v_{5} u_{1} u_{2} u_{3} u_{4} u_{5} u_{6} Figure 1 : extremal graph G_{0} Vertices v_{1},v_{2},\ldots,v_{5},u_{1},u_{2},\ldots,u_{6} \{v_{1},u_{1},u_{2}\},\{v_{1},u_{3},u_{5}\},\{v_{1},u_{4},u_{6}\}, \{v_{2},u_{1},u_{5}\},\{v_{2},u_{2},u_{6}\},\{v_{2},u_{3},u_{4}\}, Edges \{v_{3},u_{1},u_{3}\},\{v_{3},u_{2},u_{4}\},\{v_{3},u_{5},u_{6}\}, \{v_{4},u_{1},u_{4}\},\{v_{4},u_{2},u_{5}\},\{v_{4},u_{3},u_{6}\}, \{v_{5},u_{1},u_{6}\},\{v_{5},u_{2},u_{3}\},\{v_{5},u_{4},u_{5}\}. 2 Notations and Sketch of Proof Given a graph G , the neighborhood of v in G is denoted by N_{G}(v) , the degree of v in G is denoted by d_{G}(v) , the minimum degree of G is denoted by \delta(G) , the subgraph induced by S\subseteq V(G) is denoted by G[S] . For two set A and B , we write A-B for the set difference A\setminus B . For any integer n , we denote by [n] the set of integers \{1,2,\ldots,n\} . For simplicity, if no ambiguity, we identify a graph G with its vertex set, a single vertex set \{v\} with the element v and we omit a vertex pair \{u,v\} as uv ; a 3-hyperedge \{u,v,w\} as uvw . A linear path of length k , denoted by P_{k} , is the graph with 2k+1 distinct vertices \{u_{i}\mid 1\leq i\leq 2k+1\} and edge set E=\{e_{i}=u_{2j-1}u_{2j}u_{2j+1}\mid 1\leq j\leq k\}. We also denote it by the sequence of vertices P_{k}=u_{1}u_{2}\ldots u_{2k+1} or by the sequence of edges P_{k}=e_{1},e_{2},\ldots,e_{k} . Similarly, a linear cycle of length k , denoted by C_{k} , is the graph with 2k vertices \{u_{i}\mid 1\leq i\leq 2k+1\} and edge set E=\{u_{2j-1}u_{2j}u_{2j+1}\mid 1\leq j\leq k\} , where u_{2k+1}=u_{1} . A linear star with k edges , denoted by S_{k} , is the graph with 2k+1 vertices \{u\}\cup\{v_{i}\}_{1\leq i\leq 2k} and edge set E=\{uv_{2j-1}v_{2j}\mid 1\leq j\leq k\}. A non-trivial star is a star of at least two edges. In this paper, when we talk about paths, cycles and stars, we refer to linear paths, cycles and stars. Given a subset S\subseteq V(G) , let E_{i}(S)=\{e\in E(G)||e\cap S|=i\}, for 1\leq i\leq 3 , and E(S)=E_{1}(S)\cup E_{2}(S)\cup E_{3}(S) , the set of all the edges incident to vertices in S . Note that E(v)=E_{1}(v)=d_{G}(v) for a single vertex v , and one should be careful with the difference between E_{3}(S) and E(S) . In the proof, we will encounter some small graphs with at most 4 edges. To describe them, we use the same notations of linear 3-graph introduced by Colbourn and Dinitz [ 3 ] as listed in Figure 2 , and change the name of some graphs to avoid confusion. L_{8} L_{11} L_{12} L_{13} L_{14} L_{15} L_{16} Figure 2 : Notations for small linear 3-graphs Now we give a sketch of the proof of 1.2 . Note that we just need to consider the case that G is connected. Among the connected linear 3-graphs that do not contain P_{5} as a subgraph, if there exist a graph G with more than 15n(G)/11 edges, let G be the one with the minimum number of vertices. Otherwise, let G be one with exactly 15n(G)/11 edges. We are going to prove