Turán number of Berge linear forests in uniform hypergraphs

Abstract

Let F be a graph and H be a hypergraph. We say that H contains a Berge-F If there exists a bijection \phi: E(F)→E(H) such that for \mathrm{\forall }e\in E\left(F\right), e\subset \phi \left(e\right), and the Turán number of Berge-F is defined to be the maximum number of edges in an r-uniform hypergraph of order n that is Berge-F-free, denoted by ex_r(n, Berge-F). A linear forest is a graph whose connected components are all paths or isolated vertices. Let L_n,k be the family of all linear forests of n vertices with k edges. In this paper, Turán number of Berge-L_n,k in an r-uniform hypergraph is studied. When r⩾k +1 and 3 ⩽r⩽\lfloor \frac{k-1}{2}\rfloor -1, we determine the exact value of ex_r(n, Berge-L_n,k) respectively. When \lfloor \frac{k-1}{2}\rfloor⩽r⩽k, we determine the upper bound of ex_r(n, Berge-L_n,k).

Key words： Uniform hypergraph; Berge hypergraph; linear forest; Turán number

References

1 Bondy J A, Chvátal V. A method in graph theory. Discrete Math 1976; 15(2): 111–135

2 Füredi Z, Kostochka A, Luo R. Avoiding long Berge cycles. J Combin Theory Ser B 2019; 137: 55–64

3 Gerbner D, Methuku C. General lemmas for Berge-Turan hypergraph problems. European J Combin 2020; 86: 103082

4 Gerbner D, Methuku A, Vizer M. Asymptotics for the Turán number of Berge-K_{2, t}. Combin Theory Ser B 2019; 137: 264–290

5 Gerbner D, Palmer C. Extremal results for Berge hypergraphs. SIAM J Discrete Math 2017; 31(4): 2314–2327

6 Gyárfás A. The Turán number of Berge-K₄ in triple systems. SIAM J Discrete Math 2019; 33(1): 383–392

7 Györi E. Triangle-free hypergraphs. Combin Probab Comput 2006; 15(1/2): 185–191

8 Györi E, Katona G Y, Lemons N. Hypergraph extensions of the Erdös-Gallai theorem. European J Combin 2016; 58: 238–246

9 Györi E, Lemons N. Hypergraphs with no cycle of a given length. Combin Probab Comput 2012; 21(1/2): 193–201

10 Kang L Y, Ni Z Y, Shan E F. Turán number of Berge matchings in uniform hypergraphs. Discrete Math 2022; 345(8): 112901

11 Khormali O, Palmer C. Turán numbers for hypergraph star forests. European J Combin 2022; 102: 103506

12 Lazebnik F, Verstraëte J. On hypergraphs of girth five. Electron J Combin 2003; 10: R25

13 Ning B, Wang J. The formula for Turan number of spanning linear forests. Discrete Math 2020; 343(8): 111924

14 Zhang L P, Wang L G, Zhou J L. The generalized Turán number of spanning linear forests. Graphs Combin 2022; 38(2): 40

15 Zhu H, Kang L Y, Ni Z Y, Shan E F. The Turán number of Berge-K₄ in 3-uniform hypergraphs. SIAM J Discrete Math 2020; 34(3): 1485–1492