Turán number of Berge linear forests in uniform hypergraphs

doi:10.3868/s140-DDD-024-0005-x

Front. Math. China

2024, Vol. 19

Issue (1) : 25-35 https://doi.org/10.3868/s140-DDD-024-0005-x

Turán number of Berge linear forests in uniform hypergraphs

Liying KANG(

), Jiawei HUANG(

), Yisai XUE(

), Zhiwei WU(

)

Department of Mathematics, Shanghai University, Shanghai 200444, China

Download: PDF(495 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

Let F be a graph and H be a hypergraph. We say that H contains a Berge-F If there exists a bijection $φ$ : E(F)→E(H) such that for $∀ e ∈ E (F)$ , $e ⊂ φ (e)$ , 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 $⩽$ $⌊ k − 1 2 ⌋ − 1$ , we determine the exact value of ex_r(n, Berge-L_n,k) respectively. When $⌊ k − 1 2 ⌋$ $⩽$ 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

Corresponding Author(s): Liying KANG,Jiawei HUANG,Yisai XUE,Zhiwei WU

Online First Date: 31 May 2024 Issue Date: 03 June 2024

Cite this article:

Liying KANG,Jiawei HUANG,Yisai XUE, et al. Turán number of Berge linear forests in uniform hypergraphs[J]. Front. Math. China, 2024, 19(1): 25-35.

URL:

https://academic.hep.com.cn/fmc/EN/10.3868/s140-DDD-024-0005-x
https://academic.hep.com.cn/fmc/EN/Y2024/V19/I1/25

1	J A Bondy, V Chvátal. A method in graph theory. Discrete Math 1976; 15(2): 111–135
2	Z Füredi, A Kostochka, R Luo. Avoiding long Berge cycles. J Combin Theory Ser B 2019; 137: 55–64
3	D Gerbner, C Methuku. General lemmas for Berge-Turan hypergraph problems. European J Combin 2020; 86: 103082
4	D Gerbner, A Methuku, M Vizer. Asymptotics for the Turán number of Berge-K2, t. Combin Theory Ser B 2019; 137: 264–290
5	D Gerbner, C Palmer. Extremal results for Berge hypergraphs. SIAM J Discrete Math 2017; 31(4): 2314–2327
6	A Gyárfás. The Turán number of Berge-K4 in triple systems. SIAM J Discrete Math 2019; 33(1): 383–392
7	E Györi. Triangle-free hypergraphs. Combin Probab Comput 2006; 15(1/2): 185–191
8	E Györi, G Y Katona, N Lemons. Hypergraph extensions of the Erdös-Gallai theorem. European J Combin 2016; 58: 238–246
9	E Györi, N Lemons. Hypergraphs with no cycle of a given length. Combin Probab Comput 2012; 21(1/2): 193–201
10	L Y Kang, Z Y Ni, E F Shan. Turán number of Berge matchings in uniform hypergraphs. Discrete Math 2022; 345(8): 112901
11	O Khormali, C Palmer. Turán numbers for hypergraph star forests. European J Combin 2022; 102: 103506
12	F Lazebnik, J Verstraëte. On hypergraphs of girth five. Electron J Combin 2003; 10: R25
13	B Ning, J Wang. The formula for Turan number of spanning linear forests. Discrete Math 2020; 343(8): 111924
14	L P Zhang, L G Wang, J L Zhou. The generalized Turán number of spanning linear forests. Graphs Combin 2022; 38(2): 40
15	H Zhu, L Y Kang, Z Y Ni, E F Shan. The Turán number of Berge-K4 in 3-uniform hypergraphs. SIAM J Discrete Math 2020; 34(3): 1485–1492

[1]	Xiying YUAN, Xuelian SI, Li ZHANG. Ordering uniform supertrees by their spectral radii[J]. Front. Math. China, 2017, 12(6): 1393-1408.
[2]	Dongmei CHEN, Zhibing CHEN, Xiao-Dong ZHANG. Spectral radius of uniform hypergraphs and degree sequences[J]. Front. Math. China, 2017, 12(6): 1279-1288.
[3]	Xie-Bin CHEN. Fault-free Hamiltonian cycles passing through a prescribed linear forest in 3-ary n-cube with faulty edges[J]. Front Math Chin, 2014, 9(1): 17-30.

Viewed

Full text

Abstract

Cited

Shared

Discussed