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

Keywords

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

RIGHTS & PERMISSIONS

Higher Education Press 2024