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

1 Introduction

The Turán problem of graphs has always been a hot topic in graph theory. Given graphs F and G, if G does not contain F as a subgraph, we say that G is F-free. We write ex(n, F) for the Turán number of F, which is the maximum number of edges in an F-free graph on n vertices. In general, let F be a family of graphs, the maximum number of edges in an F-free graph on n vertices is called the Turán number of F, denoted by ex(n, F). In this paper, C_k, K_k, K_s,_{t ,} and M_k refer to the cycle with K vertices, the complete graph on K vertices, the complete bipartite graph on s and t vertices, and the matching with K edges, respectively. Let H and F be two graphs. The generalized Turán number of F, denoted by ex(n, H, F), is the maximum number of subgraph isomorphic to H in an F-free graph on n vertices. In particular, when H = K₂, ex(n, K₂, F) is the Turán number of F.

Since the structure of hypergraph is more complex than that of graphs, the study of the Turán problem in hypergraph faces more challenges. In 2017, Gerbner and Palmer [5] defined the notion of Berge hypergraph as a generalization of Berge path and Berge cycle. 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 on n vertices that is Berge-F-free, denoted by ex_r(n, Berge-F).

In recent years, much attention has been paid on the Turán problem of Berge hypergraph in the extremal graph theory. In 2003, Lazebnik and Verstraëte [12] established the bound on the maximum number of edges in an r-uniform hypergraph (r ⩾ 2) without both Berge-C₃ and Berge-C₄. In 2006, Györi [7] determined the exact value for the maximum number of edges in a 3-uniform hypergraph without Berge-C₃. In 2012, Györi and Lemons [9] simultaneously established the upper bound on the maximum number of edges in an r-uniform hypergraph (r ⩾ 2) without Berge-C_2k and the upper bound for the maximum number of edges in an r-uniform hypergraph (r ⩾ 3) without Berge-C_2k+1. In 2016, Györi et al. [8] generalized the Erdös-Gallai theorem on graphs to an r-uniform hypergraph and gave the upper bound on the Turán number of Berge path. In 2017, Gerbner and Palmer [5] gave the bound on the Turán number of a general Berge hypergraph. In 2019, Füredi et al. [2] gave the upper bound on the maximum number of edges in an r-uniform hypergraph which does not contain the Berge cycle with a length at least K. In 2019, Gerbner et al. [4] determined the asymptotic value for the Turán number of Berge-K_{2, t} (t ⩾ 7) in a 3-uniform hypergraph and the upper and lower bounds for the Turán number of Berge-K_{2, t} (r ⩾ 3) in an r-uniform hypergraph. Then, Gerbner et al. [3] further improved the bound on the Turán number of Berge-K_{2, t} in an r-uniform hypergraph, and gave the bound on the Turán number of Berge tree as well as the exact value to the Turán number of Berge-K_k when k > r + 2. For the 3-uniform hypergraph, the Turán number of Berge-K₄ has been determined [6, 15]. Recently, Khormali and Palmer [11] established bounds on the Turán number of Berge star forest in an r-uniform hypergraph. Kang Liying et al. [10] gave the exact value to the Turán number of Berge-M_k in an r-uniform hypergraph. In this paper, the Tur Turán number of Berge linear forest in an r-uniform hypergraph is studied. The exact values of ex_r(n, Berge-L_n,k) under r ⩾ k +1 and 3 ⩽ r ⩽ \lfloor \frac{k-1}{2}\rfloor -1 are determined respectively, and the upper bound on ex_r(n, Berge-L_n,k) is given when \lfloor \frac{k-1}{2}\rfloor ⩽ r ⩽ k.

2 Basic concepts and notations

This section mainly introduces some basic concepts and notations about graphs and hypergraphs. The graphs mentioned in this paper all refer to simple graphs.

Let G be a graph, V(G), and E(G) be the vertex set and the edge set of G, respectively. e(G) refers to the edge number of G. Given a vertex v and an edge e of G, if v\in e, we say that v and e are incident, and v is one endpoint of edge e. If two vertices u and v in G are incident simultaneously with certain edge, we say that u and v are incident in G. If two endpoints of one edge are u and v, the edge will be denoted by uv. Given u\in V\left(G\right), the number of edges incident with vertex u in G is called the degree of u in G, denoted by d_G(u). In particular, the vertex with degree 0 in a graph is defined as isolated vertex. Moreover, a linear forest refers to a graph whose connected components are all paths or isolated vertices. L_n,k indicates the family of graphs composed of the linear forests with n vertices and K edges.

Given two graphs G and F, if V\left(F\right)\subseteq V\left(G\right) and E\left(F\right)\subseteq E\left(G\right), we say F is a subgraph of G. N(F, G) indicates the number of subgraphs isomorphic to F in G. Let V^{\prime } be a nonempty subset of V(G). The subgraph of G induced by V^{\prime } is a subgraph consisting vertex set V^{\prime } and edge sets in which the endpoints in G are all in V^{\prime }, denoted by G[V^{\prime }]. We also say G[V^{\prime }] is the induced subgraph of G. G\V^{\prime } refers to the subgraph obtained by deleting all the vertices in V^{\prime } and all the edges incident to these vertices from G. Let E^{\prime } be a nonempty subset of E(G). The subgraph of G induced by E^{\prime } is a subgraph whose edge set is E^{\prime } and vertex set is all the endpoints of the edges in E^{\prime }, denoted by G[E^{\prime }]. G[E^{\prime }] is also called the edge-induced subgraph of G. The union of G and F refers to a graph with the vertex set V\left(G\right)\cup V\left(F\right) and the edge set E\left(G\right)\cup E\left(F\right), denoted by G∪F. Let u and v be two non-adjacent vertices in G. G + uv indicates the graph obtained by adding the edge uv to G. Given two vertex-disjoint graphs G and F, H and the join graph of H is G∨F, whose vertex set is V(G∨F)=V(G)∪V(F) and edge set is E(G∨F)=E(G)∪E(F)∪{xy:x\inV(G), y\inV(F)}.

The hypergraph H is a set system composed of a binary set (V(H), E(H)). V(H) is a finite set, which is called the vertex set of the hypergraph H. Each element in V(H) is called a vertex of the hypergraph H. E(H) indicates a family of sets consisting of subsets of V(H), which is called the hyperedge set of the hypergraph H. Each element in E(H) is called a hyperedge of hypergraph H, or an edge for short. If every edge of hypergraph H contains r vertices, we say that H is an r-uniform hypergraph.

3 Preliminaries

This chapter mainly introduces some methods and lemmas related to the Turán problem in Berge hypergraph.

In the r-uniform hypergraph, the Turán number of Berge-F is closely related to the generalized Turán number ex(n, K_r, F).

Gerbner and Palmer [5] showed the relationship between the Turán number of Berge-F and the generalized Turán number ex(n, K_r, F).

Lemma 3.1 [5]　Suppose that r ⩾ 2 and F is a simple graph. Then

\mathrm{e}\mathrm{x}\left(n,K_r,F\right)\le {\mathrm{e}\mathrm{x}}_{\mathrm{r}}\left(n,\mathrm{B}\mathrm{e}\mathrm{r}\mathrm{g}\mathrm{e}\text{-}F\right)\le \mathrm{e}\mathrm{x}\left(n,K_r,F\right)+\mathrm{e}\mathrm{x}\left(n,F\right).

Give a graph G, all edges in G are colored with red and blue, and this edge-colored graph is called red-blue-colored graph. Assume that G is a red-blue-colored graph, G_red is the subgraph generated by all red edges in G, G_blue is the subgraph generated by all blue edges in G, and define

g_r\left(G\right)=e\left(G_{red}\right)+N\left(K_r,G_{blue}\right).

In the following lemmas, Gerbner et al. [3] showed the relationship between the Turán number of Berge-F in an r-uniform hypergraph and the F-free red-blue-colored graph.

Lemma 3.2 [3]　 Let r ⩾ 2 and F be a graph.

ex_r(n, Berge-F) ⩽ max{g_r(G) | G is a red-blue-colored graph on n vertices without F as a subgraph}.

Kang et al. [10] gave the following three lemmas.

Lemma 3.3 [10]　 Given three integers k, r, and l, if r ⩽ k − 1 and 0 < l < k, then

l+\left(\genfrac{}{}{0pt}{}{k-l}{r-1}\right)\le \left(\genfrac{}{}{0pt}{}{k}{r-1}\right).

Equality holds if and only if l = 0.

Lemma 3.4 [10]　 Given three integers k, r, and l, if l ⩽ k, then

l+\left(\genfrac{}{}{0pt}{}{k-l}{r-1}\right)\le \mathrm{m}\mathrm{a}\mathrm{x}\left\{\left(\genfrac{}{}{0pt}{}{k}{r-1}\right),k\right\}.

Lemma 3.5 [10]　 Given two integers k and r, then

max{g_r(G)|G is a red-blue-colored complete graph K_k on k vertices} = \mathrm{m}\mathrm{a}\mathrm{x}\{\left(\genfrac{}{}{0pt}{}{k}{r}\right),\left(\genfrac{}{}{0pt}{}{k}{2}\right)\}.

When r ⩾ k − 1, the equality holds if and only if all edges in K_k are red. When r ⩽ k − 3, the equality holds if and only if all edges in K_k are blue. When r = k − 2, the equality holds if and only if all edges in K_k are blue or red.

Recently, Zhang et al. [14] gave the generalized Turán number ex(n, K_r, L_n,k) of spanning linear forest L_n,k .

Lemma 3.6 [14]　 Given any integer r ⩾ 2 and n ⩾ k + 1, then

\mathrm{e}\mathrm{x}(n,K_r,L_{n,k})=\left\{\left(\genfrac{}{}{0pt}{}{k}{r}\right),\left(\genfrac{}{}{0pt}{}{\lceil {\displaystyle \frac{k+1}{2}}\rceil }{r}\right)+\left(n-\lceil {\displaystyle \frac{k+1}{2}}\rceil \right)\left(\genfrac{}{}{0pt}{}{\lceil {\displaystyle \frac{k-1}{2}}\rceil }{r-1}\right)\right\}.

It is verified that the graph K_k or the graph K\lceil \frac{k+1}{2}\rceil∨(n −\lceil \frac{k+1}{2}\rceil ) K₁ is the extremal graph with the extremal number in Lemma 3.6. According to Lemma 3.1 and Lemma 3.6, we obtain the following results.

Lemma 3.7

{\mathrm{e}\mathrm{x}}_r(n,\mathrm{B}\mathrm{e}\mathrm{r}\mathrm{g}\mathrm{e}\text{-}{L}_{n,k})\ge max\left\{\left(\genfrac{}{}{0pt}{}{k}{r}\right),\left(\genfrac{}{}{0pt}{}{\lceil {\displaystyle \frac{k+1}{2}}\rceil }{r}\right)+\left(n-\lceil {\displaystyle \frac{k\mp 1}{2}}\rceil \right)\left(\genfrac{}{}{0pt}{}{\lceil {\displaystyle \frac{k-1}{2}}\rceil }{r-1}\right)\right\}.

In 1976, Bondy and Chvátal [1] introduced the closure technique for graphs. Given the graph G with n vertices, the property P defined on G, and the positive integer K, if G + uv has property P and d_G(u) + d_G(v) ⩾ k, then G itself has property P. We say property P is k-stable. The k closure of G which is a graph is obtained by repeatedly connecting pairs of nonadjacent vertices whose sum of degrees is not less than K in G until no such pair exists. The k closure of G is denoted by cl_k(G). In particular, we say G is k-closure-stable when cl_k(G) = G. If the property “forbidden graph family F (or graph-family-F-free)” is k-stable for certain graph family F, the study of the extremal number ex(n, F) is equivalent to the study of the maximum number of edges in a k-closure-stable graph that the graph family F is free.

In the following lemmas, Ning and Wang [13] proved that the property “L_n,k-free” is k-stable.

Lemma 3.8 [13]　 Let G be a graph, u and v be two distinct vertices in G such that d_G(u) + d_G(v) ⩾ k. G is L_n,k-free if and only if G + uv is L_n,k-free.

4 Main results

This chapter mainly discusses the Turán number of Berge-L in an r-uniform hypergraphs. It is verified that when n ⩽ k, an r-uniform hypergraph on n vertices must be Berge-L_n,k-free. Therefore, ex_r (n, Berge-L_n,k)=\left(\genfrac{}{}{0pt}{}{n}{r}\right) when n ⩽ k. Assume that n ⩾ k + 1 in the following lemmas.

Theorem 4.1　 Let R and K be two positive integers. If r ⩾ k + 1, then

{\mathrm{e}\mathrm{x}}_r\left(n,\mathrm{B}\mathrm{e}\mathrm{r}\mathrm{g}\mathrm{e}\text{-}{L}_{n,k}\right)=k-1.

Proof　As any r-uniform hypergraph consisting of n vertices and k − 1 edges must be Berge-L_n,k-free,

{\mathrm{e}\mathrm{x}}_r\left(n,\mathrm{B}\mathrm{e}\mathrm{r}\mathrm{g}\mathrm{e}\text{-}{L}_{n,k}\right)\ge k-1.

The following is to prove that any r-uniform hypergraph consisting of n vertices and k edges must contain Berge-L_n,k .

By reduction to absurdity, we assume that there exists an r-uniform hypergraph H with n vertices and k edges such that H is Berge-L_n,k-free. To keep uniformity, we may assume that G is a Berge linear forest with the largest number of edges contained in H. Let t be the number of edges, and L_t indicates the corresponding linear forest. There is t ⩽ k − 1. Then we can obtain that at least one edge in H is not contained in G, and this edge is denoted by e. In the proof, we assume that L_t does not contain isolated vertices. If there are isolated vertices, we only need to consider the paths in L_t.

If there are at least two vertices in e that do not belong to V(L_t) , and the two vertices are denoted by u and v, given L_t+1 = L_t∪{uv}, L_t+1 will be a linear forest with t + 1 edges, and G∪e is Berge-L_t+1, which is a contradiction to the maximality of G.

If there is only one vertex in e that does not belong to V(L_t), and the vertex is denoted by u, we claim that at least one vertex in e\{u} is an endpoint of certain path in L_t. Otherwise, every point in e\{u} will be an interior vertex of certain path in L_t. When r ⩾ k + 1, t ⩾ k + 1, which is a contradiction. Therefore, it can be assumed that v\ine\{u} is an endpoint of certain path in L_t. Given L_t+1 = L_t∪{uv}, L_t+1 will be a linear forest with t + 1 edges, and G∪e is Berge-L_t+1, which is a contradiction to the maximality of G.

If all vertices in e belong to V(L_t), we claim that at least three vertices in e are endpoints of certain path in L_t. Otherwise, at least r − 2 vertices in e are interior vertices of certain path in L_t. When r ⩾ k +1, t ⩾ k, which is a contradiction. Therefore, e contains two distinct vertices u and v such that u and v are the endpoints of two distinct paths in L_t. Given L_t+1 = L_t∪{uv}, L_t+1 will be a linear forest with t + 1 edges, and G∪e is Berge-L_t+1, which is a contradiction to the maximality of G.

Therefore, it is conclude that when r ⩾ k + 1, ex_r(n, Berge-L_n,k) = k − 1.

When 2 ⩽ r ⩽ \lfloor \frac{k-1}{2}\rfloor -1, to gain the exact value of the Turán number of Berge-L_n,k in an r-uniform hypergraph, we give following lemma.

Lemma 4.1　 Let G be a red-blue-colored graph on n vertices that L_n,k is free. When 3 ⩽ r ⩽ \lfloor \frac{k-1}{2}\rfloor -1,

g_r(G)\le max\left\{\left(\genfrac{}{}{0pt}{}{k}{r}\right),\left(\genfrac{}{}{0pt}{}{\lceil {\displaystyle \frac{k+1}{2}}\rceil }{r}\right)+\left(n-\lceil {\displaystyle \frac{k+1}{2}}\rceil \right)\left(\genfrac{}{}{0pt}{}{\lceil {\displaystyle \frac{k-1}{2}}\rceil }{r-1}\right)\right\}.

Proof　Let G be a red-blue-colored graph on n vertices that L_n,k is free and the value of g_r(G) has been maximized. We claim that G is k-closure-stable. Otherwise, given cl_k(G) be the k closure of G, G\subset \mathrm{c}{\mathrm{l}}_k(G). According to Lemma 3.8, cl_k(G) is also L_n,k-free. We give cl_k(G) the following red-blue coloring: keep the edges belonging to G in cl_k(G) the color in G, and color the edges that do not belong to G in cl_k(G) red, then g_r(cl_k(G)) > g_r(G), which is a contradiction to the maximality of g_r(G). Therefore, G is k-closure-stable.

Let V₁ be the set of vertices with degree at least\lceil \frac{k}{2}\rceil in G. Assume that |V₁| t, V₂ = V(G) \ V₁ = \left\{v_1,v_2,\dots ,v_{n-t}\right\}. Since G is k-closure-stable, G[V₁] is a t-clique. In addition, as G is L_n,k-free, t ⩽ k. Based on the value range of t, two different cases are considered below.

Case 1　 t ⩽ \lfloor \frac{k}{2}\rfloor.

Considering |V₂|= n − t⩾n −\lceil \frac{k+1}{2}\rceil, we assume that v_1,v_2,\dots ,v_{n-\lceil \frac{k+1}{2}\rceil } are the first n-\lceil \frac{k+1}{2}\rceil vertices in V₂, and G^{\prime } = G\\{v_1,v_2,\dots ,v_{n-\lceil \frac{k+1}{2}\rceil }\}. As v_i∉ V₁, d_G(v_i) ⩽ \lfloor \frac{k-1}{2}\rfloor, in which i=1,2,\dots ,n-\lceil \frac{k+1}{2}\rceil. If there are l_i red edges incident to v_i in the red-blue-colored graph G, the maximum number of blue r-cliques containing v_i is \left(\genfrac{}{}{0pt}{}{\lfloor \frac{k-1}{2}\rfloor -l_i}{r-1}\right), where i=1,2,\dots ,n\lceil \frac{k+1}{2}\rceil, n −\lceil \frac{k+1}{2}\rceil. According to Lemma 3.3 and Lemma 3.5, we obtain

\begin{array}{rl}{g}_r\left(G\right)& \le \sum _{i=1}^{n-\lceil \frac{k+1}{2}\rceil }\left(\left(\genfrac{}{}{0pt}{}{\lfloor {\displaystyle \frac{k-1}{2}}\rfloor -{\ell }_i}{r-1}\right)+{\ell }_i\right)+g_r\left(G^{\prime }\right)\\ & \le \sum _{i=1}^{n-\lceil \frac{k+1}{2}\rceil }\left(\genfrac{}{}{0pt}{}{\lceil {\displaystyle \frac{k-1}{2}}\rceil }{r-1}\right)+g_r\left(K_{\lceil \frac{k+1}{2}\rceil }\right)\\ & \le \left(n-\lceil \frac{k+1}{2}\rceil \right)\left(\genfrac{}{}{0pt}{}{\lceil {\displaystyle \frac{k-1}{2}}\rceil }{r-1}\right)+\left(\genfrac{}{}{0pt}{}{\lceil {\displaystyle \frac{k+1}{2}}\rceil }{r}\right).\end{array}

Case 2　 \lceil \frac{k+1}{2}\rceil ⩽ t ⩽ k.

Considering that G is k-closure-stable, for any vertices v ∈V₂, d_G(v) ⩽ k − t. If s = k − t, 0 ⩽ s ⩽ \lfloor \frac{k-1}{2}\rfloor. we assume that there are l_i red edges incident to v_i in the red-blue-colored graph G, the maximum number of blue r-cliques containing v_i is \left(\genfrac{}{}{0pt}{}{s-l_i}{r-1}\right), where i=1,2,\dots ,n-t. According to Lemma 3.4 and Lemma 3.5, we obtain

\begin{array}{rl}{g}_r\left(G\right)& \le \sum _{i=1}^{n-t}(\left(\genfrac{}{}{0pt}{}{s-{\ell }_i}{r-1}\right)+{\ell }_i)+g_r\left(K_t\right)\\ & \le \sum _{i=1}^{n-t}\mathrm{m}\mathrm{a}\mathrm{x}\left\{\left(\genfrac{}{}{0pt}{}{s}{r-1}\right),s\right\}+\left(\genfrac{}{}{0pt}{}{t}{r}\right)\\ & \le \left(n-t\right)\cdot \mathrm{m}\mathrm{a}\mathrm{x}\{\left(\genfrac{}{}{0pt}{}{s}{r-1}\right),s\}+\left(\genfrac{}{}{0pt}{}{t}{r}\right)\\ & =\left(n-k+s\right)\cdot \mathrm{m}\mathrm{a}\mathrm{x}\{\left(\genfrac{}{}{0pt}{}{s}{r-1}\right),s\}+\left(\genfrac{}{}{0pt}{}{k-s}{r}\right).\end{array}

Let f(s) = (n – k + s)\left(\genfrac{}{}{0pt}{}{s}{r-1}\right)+\left(\genfrac{}{}{0pt}{}{k-s}{r}\right) and g(s) = (n – k + s)s +\left(\genfrac{}{}{0pt}{}{k-s}{r}\right). It is verified that as f^{″}(s) > 0 and g^{″}(s) > 0, f(s) and g(s) are convex function. According to 0 ⩽ s ⩽ \lfloor \frac{k-1}{2}\rfloor and the convexity of f(s) and g(s), we obtain that

\begin{array}{rl}{g}_r\left(G\right)& \le \mathrm{m}\mathrm{a}\mathrm{x}\{f\left(s\right),g\left(s\right)\}\\ & \le \mathrm{m}\mathrm{a}\mathrm{x}\left\{f\left(0\right),f\left(\lfloor {\displaystyle \frac{k-1}{2}}\rfloor \right),g\left(0\right),g\left(\lfloor {\displaystyle \frac{k-1}{2}}\rfloor \right)\right\}\\ & =\mathrm{m}\mathrm{a}\mathrm{x}\left\{\left(\genfrac{}{}{0pt}{}{k}{r}\right),\left(\genfrac{}{}{0pt}{}{\lceil {\displaystyle \frac{k+1}{2}}\rceil }{r}\right)+\left(n-\lceil {\displaystyle \frac{k+1}{2}}\rceil \right)\left(\genfrac{}{}{0pt}{}{\lceil {\displaystyle \frac{k-1}{2}}\rceil }{r-1}\right)\right\}.\end{array}

In summary, the lemma mentioned above is proved.

According to Lemma 3.2, Lemma 3.7, and Lemma 4.1, we obtain the following results.

Theorem 4.2　 Given two positive integers r and k, when 3 ⩽ r ⩽ \lfloor \frac{k-1}{2}\rfloor -1,

{\mathrm{e}\mathrm{x}}_r(n,\mathrm{B}\mathrm{e}\mathrm{r}\mathrm{g}\mathrm{e}\text{-}{L}_{n,k})=max\left\{\left(\genfrac{}{}{0pt}{}{k}{r}\right),\left(\genfrac{}{}{0pt}{}{\lceil {\displaystyle \frac{k+1}{2}}\rceil }{r}\right)+\left(n-\lceil \frac{k+1}{2}\rceil \right)\left(\genfrac{}{}{0pt}{}{\lceil {\displaystyle \frac{k-1}{2}}\rceil }{r-1}\right)\right\}.

When \lfloor \frac{k-1}{2}\rfloor ⩽ r ⩽ k, in order to obtain the upper bound of the Turán number of Berge-L_n,k in an r-uniform hypergraph, we give the following lemma.

Lemma 4.2　 Let G be a red-blue-colored graph on n vertices that L_n,k is free. When \lfloor \frac{k-1}{2}\rfloor ⩽ r ⩽ k,

g_r(G)\le max\left\{\left(\genfrac{}{}{0pt}{}{k}{r}\right),\left(\genfrac{}{}{0pt}{}{k}{2}\right),\left(n-\lceil \frac{k+1}{2}\rceil \right)\lfloor \frac{k-1}{2}\rfloor +\left(\genfrac{}{}{0pt}{}{\lceil {\displaystyle \frac{k+1}{2}}\rceil }{2}\right)\right\}.

Proof　Let G be a red-blue-colored graph on n vertices that L_n,k is free and the value of g_r(G) has been maximized. We claim that G is k-closure-stable.

Let V₁ be the set of vertices with degree at least \lceil \frac{k}{2}\rceil in G. Assume that |V₁| = t, V₂ = V(G)\V₁ = \left\{v_1,v_2,\dots ,V_{n-t}\right\}. Since G is k-closure-stable, G[V₁] is a t-clique. In addition, as G is L_n,k-free, t ⩽ k. Based on the value range of t, two different cases are considered below.

Case 1　 t ⩽ \lfloor \frac{k}{2}\rfloor.

Considering |V₂| = n − t ⩾ n − \lceil \frac{k+1}{2}\rceil, we assume that v_1,v_2,\dots ,v_{n-\lceil \frac{k+1}{2}\rceil }are the first n −\lceil \frac{k+1}{2}\rceil vertices in V₂. Let G^{\prime } =G\\{v_1,v_2,\dots ,v_{n-\lceil \frac{k+1}{2}\rceil }\}. As v_i∉ V₁, d_G(v_i) ⩽ \lfloor \frac{k-1}{2}\rfloor, in which i=1,2,\dots ,n-\lceil \frac{k+1}{2}\rceil. If there are l_i red edges incident to v_i in the red-blue-colored graph G, the maximum number of blue r-cliques containing v_i is \left(\genfrac{}{}{0pt}{}{\lfloor \frac{k-1}{2}\rfloor -l_i}{r-1}\right), where i=1,2,\dots ,n-\lceil \frac{k+1}{2}\rceil. According to Lemma 3.4 and Lemma 3.5, we obtain

\begin{array}{rl}{g}_r\left(G\right)& \le \sum _{i=1}^{n-\lceil \frac{k+1}{2}\rceil }(\left(\begin{array}{c}\lfloor {\displaystyle \frac{k-1}{2}}\rfloor -{\ell }_i\\ r-1\end{array}\right)+{\ell }_i)+g_r\left(G^{\prime }\right)\\ & \le \sum _{i=1}^{n-\lceil \frac{k+1}{2}\rceil }(\left(\begin{array}{c}\lfloor {\displaystyle \frac{k-1}{2}}\rfloor -{\ell }_i\\ r-1\end{array}\right)+{\ell }_i)+g_r\left(K_{\lceil \frac{k+1}{2}\rceil }\right)\\ & \le \sum _{i=1}^{n-\lceil \frac{k+1}{2}\rceil }\mathrm{m}\mathrm{a}\mathrm{x}\{\left(\begin{array}{c}\lceil {\displaystyle \frac{k-1}{2}}\rceil \\ r-1\end{array}\right),\lfloor \frac{k-1}{2}\rfloor \}+\\ & \mathrm{m}\mathrm{a}\mathrm{x}\left\{\left(\begin{array}{c}\lceil {\displaystyle \frac{k+1}{2}}\rceil \\ 2\end{array}\right),\left(\begin{array}{c}\lceil {\displaystyle \frac{k+1}{2}}\rceil \\ r\end{array}\right)\right\}\\ & =\left(n-\lceil \frac{k+1}{2}\rceil \right)\lfloor \frac{k-1}{2}\rfloor +\left(\genfrac{}{}{0pt}{}{\lceil {\displaystyle \frac{k+1}{2}}\rceil }{2}\right).\end{array}

Case 2　 \lceil \frac{k+1}{2}\rceil ⩽ r ⩽ k.

Considering that G is k-closure-stable, for any vertices v\in V_2, d_G(v) ⩽ k − t. If s = k − t, 0 ⩽ s ⩽ \lfloor \frac{k-1}{2}\rfloor. We assume that there are l_i red edges incident to v_i in the red-blue-colored graph G, the maximum number of blue r-cliques containing v_i is \left(\genfrac{}{}{0pt}{}{\lceil s-li\rceil }{r-1}\right), where i=1,2,\dots ,n-t. According to Lemma 3.4 and Lemma 3.5, we obtain

\begin{array}{rl}{g}_r\left(G\right)& \le \sum _{i=1}^{n-t}\left(\left(\genfrac{}{}{0pt}{}{s-{\ell }_i}{r-1}\right)+{\ell }_i\right)+g_r\left(K_t\right)\\ & \le \sum _{i=1}^{n-t}\mathrm{m}\mathrm{a}\mathrm{x}\left\{\left(\genfrac{}{}{0pt}{}{s}{r-1}\right),s\right\}+\mathrm{m}\mathrm{a}\mathrm{x}\left\{\left(\genfrac{}{}{0pt}{}{t}{r}\right),\left(\genfrac{}{}{0pt}{}{t}{2}\right)\right\}\\ & =\left(n-t\right)s+\mathrm{m}\mathrm{a}\mathrm{x}\left\{\left(\genfrac{}{}{0pt}{}{t}{r}\right),\left(\genfrac{}{}{0pt}{}{t}{2}\right)\right\}\\ & =\left(n-k+s\right)s+\mathrm{m}\mathrm{a}\mathrm{x}\left\{\left(\genfrac{}{}{0pt}{}{k-s}{r}\right),\left(\genfrac{}{}{0pt}{}{k-s}{2}\right)\right\}.\end{array}

It is verified that as f^{″}(s) > 0 and g^{″}(s) > 0, f(s) and g(s) are convex function. According to 0 ⩽ s ⩽ \lfloor \frac{k-1}{2}\rfloor and the convexity of f(s) and g(s), we obtain that

\begin{array}{rl}{g}_r\left(G\right)& \le \mathrm{m}\mathrm{a}\mathrm{x}\{f\left(s\right),g\left(s\right)\}\\ & \le \mathrm{m}\mathrm{a}\mathrm{x}\left\{f\left(0\right),f\left(\lfloor \frac{k-1}{2}\rfloor \right),g\left(0\right),g\left(\lfloor \frac{k-1}{2}\rfloor \right)\right\}\\ & =\mathrm{m}\mathrm{a}\mathrm{x}\left\{\left(\genfrac{}{}{0pt}{}{k}{r}\right),\left(\genfrac{}{}{0pt}{}{k}{2}\right),\left(n-\lceil \frac{k+1}{2}\rceil \right)\lfloor \frac{k-1}{2}\rfloor \left(\genfrac{}{}{0pt}{}{\lceil {\displaystyle \frac{k+1}{2}}\rceil }{2}\right)\right\}.\end{array}

In summary, the lemma mentioned above is proved.

According to Lemma 3.2 and Lemma 4.2, we obtain the following result.

Theorem 4.3　 Given two positive integers r and k, when \lfloor \frac{k-1}{2}\rfloor ⩽ r ⩽ k

{\mathrm{e}\mathrm{x}}_r(n,\mathrm{B}\mathrm{e}\mathrm{r}\mathrm{g}\mathrm{e}\text{-}{L}_{n,k})\le max\left\{\left(\genfrac{}{}{0pt}{}{k}{r}\right),\left(\genfrac{}{}{0pt}{}{k}{2}\right),\left(n-\lceil \frac{k+1}{2}\rceil \right)\lfloor \frac{k-1}{2}\rfloor +\left(\genfrac{}{}{0pt}{}{\lceil {\displaystyle \frac{k+1}{2}}\rceil }{2}\right)\right\}.

5 Conclusion

The Turán problem of hypergraphs is more complex than that of graphs. At present, there are few results on the exact value of Turán number of general hypergraphs. Compared to general hypergraphs, Berge hypergraphs are more closely related to graphs. Therefore, the Turán problem of Berge hypergraphs can be studied with the help of relevant techniques and methods applied in the research of graphs. In this paper, we determine the exact value of ex_r(n, Berge-L_n,k) when r ⩾ k + 1 and 3 ⩽ r ⩽ \lfloor \frac{k-1}{2}\rfloor -1 by means of two lemmas on the Turán number of Berge hypergraphs and the closure technique on graphs. And we also give the upper bound of ex_r(n, Berge-L_n,k) when \lfloor \frac{k-1}{2}\rfloor ⩽ r ⩽ k.

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