Abstract
Let F be a family of 3-uniform linear hypergraphs. The linear Turán number of F is the maximum possible number of edges in a 3-uniform linear hypergraph on n vertices which contains no member of F as a subhypergraph. In this paper we show that the linear Turán number of the five cycle C5 (in the Berge sense) is [Formula presented]n3/2 asymptotically. We also show that the linear Turán number of the four cycle C4 and {C3,C4} are equal asymptotically, which is a strengthening of a theorem of Lazebnik and Verstraëte [16]. We establish a connection between the linear Turán number of the linear cycle of length 2k+1 and the extremal number of edges in a graph of girth more than 2k−2. Combining our result and a theorem of Collier-Cartaino, Graber and Jiang [8], we obtain that the linear Turán number of the linear cycle of length 2k+1 is Θ(n1+[Formula presented]) for k=2,3,4,6.
Original language | English (US) |
---|---|
Pages (from-to) | 163-181 |
Number of pages | 19 |
Journal | Journal of Combinatorial Theory. Series A |
Volume | 163 |
DOIs | |
State | Published - Apr 2019 |
Externally published | Yes |
Keywords
- Berge cycle
- Five cycle
- Hypergraph Turán problem
- Linear cycle
- Linear Turán number
- Loose cycle
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics