# Turán numbers of general hypergraph star forests ††thanks: Supported by the
National Natural Science Foundation of China (No.12271439) and China
Scholarship Council (No. 202206290003).

Lin-Peng Zhanga,b, Hajo Broersmab111Corresponding author., Ligong Wanga
a School of Mathematics and Statistics,
Northwestern Polytechnical University, Xi’an, Shaanxi 710129, P.R. China.
b Faculty of Electrical Engineering, Mathematics and Computer Science,
University of Twente, P.O. Box 217, 7500 AE Enschede, the Netherlands
E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
Abstract

Let $\mathcal{F}$ be a family of $r$-uniform hypergraphs, and let $H$ be an
$r$-uniform hypergraph. Then $H$ is called $\mathcal{F}$-free if it does not
contain any member of $\mathcal{F}$ as a subhypergraph. The Turán number of
$\mathcal{F}$, denoted by $ex_{r}(n,\mathcal{F})$, is the maximum number of
hyperedges in an $\mathcal{F}$-free $n$-vertex $r$-uniform hypergraph. Our
current results are motivated by earlier results on Turán numbers of star
forests and hypergraph star forests. In particular, Lidický, Liu and Palmer
[Electron. J. Combin. 20 (2013)] determined the Turán number $ex(n,F)$ of a
star forest $F$ for sufficiently large $n$. Recently, Khormali and Palmer
[European. J. Combin. 102 (2022) 103506] generalized the above result to three
different well-studied hypergraph settings, but restricted to the case that
all stars in the hypergraph star forests are identical. We further generalize
these results to general hypergraph star forests. Key Words: Turán number;
Berge hypergraph; star forest AMS Subject Classification (2020): 05C35, 05C65

##  1 Introduction

The results in this paper deal with Turán numbers of hypergraph star forests.
Our work is motivated by recent results by different groups of researchers,
and aims at generalizing their results. Before we can give more details, we
need to introduce and recall some essential terminology and notation.

Let $\mathcal{F}$ be a family of $r$-uniform hypergraphs. An $r$-uniform
hypergraph $H$ is called $\mathcal{F}$-free if it does not contain any member
of $\mathcal{F}$ as its subhypergraph. Note that here we mean subhypergraph,
and not necessarily induced subhypergraph. The Turán number of $\mathcal{F}$,
denoted by $ex_{r}(n,\mathcal{F})$, is the maximum number of hyperedges in an
$r$-uniform $n$-vertex $\mathcal{F}$-free hypergraph. When $r=2$, instead of
writing $ex_{2}(n,\mathcal{G})$ we use $ex(n,\mathcal{G})$ for a family of
graphs $\mathcal{G}$. Determining the Turán numbers for specific graphs and
graph classes is a classic and well-studied area within graph theory. This
started already back in 1907, when Mantel [28] determined the Turán number of
a triangle $K_{3}$. The term Turán number reflects the fact that in 1941,
Turán [35] generalized Mantel’s result by his seminal theorem that settles the
problem of determining the Turán number of a complete graph $K_{k}$ for
general $k$. Since then, there have appeared many papers and monographs on
this type of problems. One of the most fundamental results within this area of
research is the Erdős-Stone-Simonovits theorem, which gives the following
asymptotic result for all $k$-chromatic graphs $F$:

$ex(n,F)=\bigg{(}1-\frac{1}{k-1}\bigg{)}\frac{n^{2}}{2}+o(n^{2}).$

Here $k$ denotes the chromatic number of $F$, i.e., the smallest number of
colors needed to assign one color to each vertex of $F$ in such a way that
adjacent vertices receive different colors. Note that the above formula only
gives $ex(n,F)=o(n^{2})$ for a bipartite (2-chromatic) graph $F$. Determining
Turán numbers for bipartite graphs remains an active area of research. We
refer to the survey of Füredi and Simonovits [12] for an extensive history.

In this paper, we focus on sparse bipartite graphs, namely star forests, and
their hypergraph counterparts. Fix a positive integer $\ell$. Let $S_{\ell}$
denote the star with $\ell$ edges, i.e., the complete bipartite graph
$K_{1,\ell}$. A star forest is a graph consisting of a number of vertex-
disjoint stars. Let $G$ and $H$ be two vertex-disjoint graphs. The union of
$G$ and $H$, denoted by $G\cup H$, is the graph with vertex set $V(G)\cup
V(H)$ and edge set $E(G)\cup E(H)$. Denote by $k\cdot G$ the graph composed of
$k$ pairwise vertex-disjoint copies of the graph $G$.

In 2013, Lidický, Liu and Palmer [26] determined the Turán number of a star
forest for sufficiently large $n$.

######  Theorem 1.1 (Lidický, Liu and Palmer, [26]).

Let $d_{1}\geq d_{2}\geq\cdots\geq d_{k}$ be $k$ positive integers. For $n$
sufficiently large,

$ex\bigg{(}n,\bigcup\limits_{i=1}^{k}S_{d_{i}}\bigg{)}=\mathop{max}\limits_{1\leq
i\leq
k}\Bigg{\\{}(i-1)(n-i+1)+\binom{i-1}{2}+\left\lfloor\frac{d_{i}-1}{2}(n-i+1)\right\rfloor\Bigg{\\}}.$

We come back to this later, but first continue with a discussion on hypergraph
analogues of Turán type extremal problems. Determining Turán numbers for
hypergraphs is another direction which has attracted a lot of attention. One
of the issues that we meet is to give a suitable and reasonable generalization
of graph structures to hypergraph structures. It is natural to generalize the
notion of a complete graph to a complete hypergraph in the following way.
Since the edge set of a complete graph $K_{k}$ on $k$ vertices is the set of
all possible 2-element subsets of these $k$ vertices, the set of hyperedges of
a complete $r$-uniform $k$-vertex hypergraph is the set of all possible
$r$-element subsets of these $k$ vertices. The difficulty of determining the
Turán numbers for hypergraphs is reflected by the fact that we still do not
know the Turán number of $K^{3}_{4}$, the complete 3-uniform 4-vertex
hypergraph.

In this paper, we aim to determine Turán numbers for analogues of star forests
in the hypergraph setting. For this, we will in fact consider three different
hypergraph settings that are known from literature. The first hypergraph
setting we consider is based on the notion of expansion.

Fix a graph $F$ and an integer $r\geq 2$. The expansion of $F$ is the
$r$-uniform hypergraph $F^{+}$ constructed by adding $r-2$ new distinct
vertices to each edge of $F$, where all added new vertices are distinct. When
$r=2$, the expansion $F^{+}$ is exactly the original graph $F$. There already
exist several papers involving Turán numbers for various expansions (See,
e.g., [2, 8, 10, 11, 22, 23, 24, 29, 31]). The case with $F^{+}=S^{+}_{\ell}$
has a considerable history. See the survey [30] for an overview.

In 1977, Duke and Erdős [4] proved the following theorem.

######  Theorem 1.2 (Duke and Erdős, [4]).

Fix integers $\ell\geq 2$ and $r\geq 3$. Then there exists a constant $c(r)$
such that for sufficiently large $n$,

$ex_{r}(n,S^{+}_{\ell})\leq c(r)\ell(\ell-1)n^{r-2}.$

We can construct an extremal hypergraph with size $ex_{r}(n,S^{+}_{\ell})$ of
order $n^{r-2}$ as follows. Take an $r$-uniform hypergraph all hyperedges of
which contain a fixed pair of vertices.

For presenting the next result due to Erdős [5], let $M_{k}$ be a matching of
size $k$, i.e., a set of $k$ disjoint edges. We can view $M_{k}$ as a star
forest each star of which is $S_{1}$, an edge. The following well-known
theorem gives the Turán number of the expansion of $M_{k}$, when the number of
vertices is sufficiently large.

######  Theorem 1.3 (Erdős, [5]).

Fix integers $k\geq 1$ and $r\geq 2$. Then for sufficiently large $n$,

$ex_{r}(n,M^{+}_{k})=\binom{n}{r}-\binom{n-k+1}{r}.$

In a recently published paper, Khormali and Palmer [21] generalized the above
result to the expansion $k\cdot S^{+}_{\ell}$ of a star forest $k\cdot
S_{\ell}$ composed of $k$ copies of the star $S_{\ell}$.

######  Theorem 1.4 (Khormali and Palmer, [21]).

Fix integers $\ell,k\geq 1$ and $r\geq 2$. Then for sufficiently large $n$,

$ex_{r}(n,k\cdot
S^{+}_{\ell})=\binom{n}{r}-\binom{n-k+1}{r}+ex_{r}(n-k+1,S^{+}_{\ell}).$

In our first new main result, we generalize the above result by obtaining the
Turán number of the expansion of a general star forest. We postpone our proof
of the next result to Section 2.

######  Theorem 1.5.

Fix integers $d_{1}\geq d_{2}\geq\cdots\geq d_{k}$, $k\geq 1$ and $r\geq 2$.
Then for sufficiently large $n$,

$ex_{r}\bigg{(}n,\bigcup\limits_{i=1}^{k}S^{+}_{d_{i}}\bigg{)}=\mathop{max}\limits_{1\leq
i\leq
k}\Bigg{\\{}\binom{n}{r}-\binom{n-i+1}{r}+ex_{r}\Big{(}n-i+1,S^{+}_{d_{i}}\Big{)}\Bigg{\\}}.$

For our next main result, we turn to another hypergraph setting, which is
based on the notion of a linear hypergraph. An $r$-uniform hypergraph is
called linear if every pair of hyperedges of it shares at most one vertex. It
is easy to see that each expansion is a linear hypergraph. Hence, we can
consider corresponding problems among linear hypergraphs. Let $F$ be a linear
$r$-uniform hypergraph. Then the linear Turán number of $F$, denoted by
$ex^{lin}_{r}(n,F)$, is the maximum number of hyperedges in an $r$-uniform
$n$-vertex $F$-free linear hypergraph. A seminal result in this context
settles the problem of determining the linear Turán number
$ex^{lin}_{3}(n,C^{+}_{3})$ of the expansion of $C_{3}$, which is equivalent
to the famous (6,3)-problem. Motivated by this result, more and more papers on
this topic are starting to emerge (See, e.g., [3, 6, 7, 9, 13, 15, 18, 19, 25,
32, 33, 34]).

In 2022, Khormali and Palmer [21] determined the linear Turán number of
$k\cdot S^{+}_{l}$ asymptotically for sufficiently large $n$.

######  Theorem 1.6 (Khormali and Palmer, [21]).

Fix integers $\ell,k\geq 1$ and $r\geq 2$. Then for sufficiently large $n$,

$ex^{lin}_{r}(n,k\cdot
S^{+}_{\ell})\leq\bigg{(}\frac{\ell-1}{r}+\frac{k-1}{r-1}\bigg{)}(n-k+1)+\frac{\binom{k-1}{2}}{\binom{r}{2}}.$

Moreover, this bound is sharp asymptotically.

In our second main result, we determine the linear Turán number of a general
hypergraph star forest asymptotically for sufficiently large $n$.

######  Theorem 1.7.

Fix integers $d_{1}\geq d_{2}\geq\cdots\geq d_{k}$, $k\geq 1$ and $r\geq 2$.
Then for sufficiently large $n$,

$ex^{lin}_{r}\bigg{(}n,\bigcup\limits_{i=1}^{k}S^{+}_{d_{i}}\bigg{)}\leq\mathop{max}\limits_{1\leq
i\leq
k}\bigg{\\{}\bigg{(}\frac{d_{i}-1}{r}+\frac{i-1}{r-1}\bigg{)}(n-i+1)+\frac{\binom{i-1}{2}}{\binom{r}{2}}\bigg{\\}}.$

Moreover, this bound is sharp asymptotically.

We postpone our proof of the above result to Section 3. In the following, we
turn to a third hypergraph setting, as defined by Gerbner and Palmer [16]. Let
$F$ be a graph. An $r$-uniform hypergraph $\mathcal{H}$ is called a Berge-$F$
if there is an injection $f:V(F)\rightarrow V(\mathcal{H})$ and a bijection
$f^{\prime}:E(F)\rightarrow E(\mathcal{H})$ such that for every edge $uv\in
E(F)$ we have $\\{f(u),f(v)\\}\subseteq f^{\prime}(uv)$. For a fixed graph
$F$, we can observe that there are many different hypergraphs that are a
Berge-$F$, and that a fixed hypergraph $\mathcal{H}$ can be a Berge-$F$ for
more than one graph $F$. For a short survey of extremal results for
Berge-$F$-free hypergraphs see Subsection 5.2.2 in [17].

In 2022, by considering distinct values of $r,k,\ell$ in the following two
results, Khormali and Palmer [21] determined the Turán number of a
Berge-$k\cdot S_{\ell}$ asymptotically for sufficiently large $n$.

######  Theorem 1.8 (Khormali and Palmer, [21]).

Fix integers $\ell,k\geq 2$ and $r\geq\ell+k-1$. Then for sufficiently large
$n$,

$ex_{r}(n,\mbox{Berge-}k\cdot S_{\ell})\leq\frac{\ell-1}{r-k+1}(n-k+1).$

Moreover, this bound is sharp whenever $r-k+1$ divides $n-k+1$.

######  Theorem 1.9 (Khormali and Palmer, [21]).

Fix integers $\ell,k\geq 2$ and $r\leq\ell+k-2$. Then for sufficiently large
$n$,

$ex_{r}(n,\mbox{Berge-}k\cdot
S_{\ell})\leq\bigg{(}\binom{\ell+k-1}{r}-\binom{k-1}{r}\bigg{)}\left\lceil\frac{n-k+1}{\ell}\right\rceil+\binom{k-1}{r}.$

Moreover, this bound is sharp whenever $\ell$ divides $n-k+1$.

With our final two main results, we generalize the above results to more
general Berge-star forests. We postpone our proofs to Section 4 and 5,
respectively.

######  Theorem 1.10.

Fix integers $d_{1}\geq d_{2}\geq\cdots\geq d_{k}\geq 2$, $k\geq 2$ and $r\geq
d_{1}+k-1$. Then for sufficiently large $n$,

$ex_{r}\bigg{(}n,\mbox{Berge-}\bigcup\limits_{i=1}^{k}S_{d_{i}}\bigg{)}\leq\mathop{max}\limits_{1\leq
s\leq k-1}\bigg{\\{}\frac{d_{s+1}-1}{r-s}(n-s)\bigg{\\}}.$

Moreover, this bound is sharp whenever $r-s$ divides $n-s$ for $1\leq s\leq
k-1$.

######  Theorem 1.11.

Fix integers $d_{1}\geq d_{2}\geq\cdots\geq d_{k}\geq 2$, $k\geq 2$ and $r\leq
d_{1}+k-2$. Then for sufficiently large $n$,

$\displaystyle
ex_{r}\bigg{(}n,\mbox{Berge-}\bigcup\limits_{i=1}^{k}S_{d_{i}}\bigg{)}$
$\displaystyle\leq\mathop{max}\bigg{\\{}\mathop{max}\limits_{1\leq i\leq
k}\bigg{\\{}\bigg{(}\binom{d_{i}+i-1}{r}-\binom{i-1}{r}\bigg{)}\left\lceil\frac{n-i+1}{d_{i}}\right\rceil+\binom{i-1}{r},$
$\displaystyle\frac{d_{i}-1}{r-i+1}(n-i+1)\bigg{\\}},\mathop{max}\limits_{1\leq
c<k-1}\bigg{\\{}\frac{\mathop{max}\Big{\\{}\binom{d_{c}+c}{r-1},d_{c}+c\Big{\\}}}{r-c}(n-c)\bigg{\\}}\bigg{\\}}.$

Moreover, this bound is sharp whenever $d_{i}$ and $r-i+1$ divide $n-i+1$ for
$1\leq i\leq k$.

The remainder of this paper is devoted to the proofs of our new contributions.
We complete the paper by a short concluding section.

##  2 Proof of Theorem 1.5

By Theorems 1.1 and 1.3, the theorem holds for $r=2$ or $d_{1}=1$. Thus, it
suffices to show that the theorem holds when $r\geq 3$ and $d_{1}\geq 2$.

For the lower bound, we can construct an extremal hypergraph $H$ as follows.
Fix $i$ such that $1\leq i\leq k$, and let $A$ and $B$ be vertex sets of $i-1$
and $n-i+1$ vertices, respectively. Firstly, we embed an $S^{+}_{d_{i}}$-free
$r$-uniform hypergraph with $ex_{r}(n-i+1,S^{+}_{d_{i}})$ hyperedges into $B$.
Next, we add every $r$-set that is incident to $A$ to our hypergraph. Since
$B$ contains no copy of $S^{+}_{d_{i}}$, each $S^{+}_{d_{j}}$ with $1\leq
j\leq i$ must contain at least one vertex of $A$. Therefore, $H$ is
$\bigcup\limits_{i=1}^{k}S^{+}_{d_{i}}$-free. Thus, we can choose $i$ such
that the number of hyperedges in $H$ attains the value in the statement of the
theorem.

In the following, we consider the upper bound. Let $\mathcal{H}$ be an
$r$-uniform $n$-vertex hypergraph with

$|E(\mathcal{H})|>\mathop{max}\limits_{1\leq i\leq
k}\Bigg{\\{}\binom{n}{r}-\binom{n-i+1}{r}+ex_{r}\Big{(}n-i+1,S^{+}_{d_{i}}\Big{)}\Bigg{\\}}.$

We need to show that $\mathcal{H}$ is not
$\bigcup\limits_{i=1}^{k}S^{+}_{d_{i}}$-free. We proceed by induction on $k$.
For $k=1$, since $|E(\mathcal{H})|>ex_{r}(n,S^{+}_{d_{1}})$ we have
$\mathcal{H}$ is not $S^{+}_{d_{1}}$-free. Let $k>1$ and assume the statement
holds for $k-1$. In the following, we discuss two cases based on the maximum
degree $\Delta(\mathcal{H})$ of $\mathcal{H}$.

Case 1:

$\Delta(\mathcal{H})<\frac{1}{\bigcup\limits_{i=1}^{k-1}((r-1)d_{i}+1)}\bigg{(}\binom{n}{r}-\binom{n-k+1}{r}\bigg{)}.$

Assume that $\mathcal{H}$ contains a copy of $\cup_{i=1}^{t}S^{+}_{d_{i}}$
such that $t$ is maximal. We claim that $t\geq k$. Otherwise, there are at
most $\cup_{i=1}^{k-1}((r-1)d_{i}+1)$ vertices spanned by
$\cup_{i=1}^{t}S^{+}_{d_{i}}$. After removing these vertices and the incident
hyperedges we have at least

$\displaystyle|E(\mathcal{H})|$
$\displaystyle-\bigcup\limits_{i=1}^{k-1}((r-1)d_{i}+1)\cdot\Delta(\mathcal{H})>|E(\mathcal{H})|-\bigg{(}\binom{n}{r}-\binom{n-k+1}{r}\bigg{)}$
$\displaystyle>\binom{n}{r}-\binom{n-k+1}{r}+ex_{r}\Big{(}n-k+1,S^{+}_{d_{k}}\Big{)}-\bigg{(}\binom{n}{r}-\binom{n-k+1}{r}\bigg{)}$
$\displaystyle=ex_{r}\Big{(}n-k+1,S^{+}_{d_{k}}\Big{)}$

hyperedges. Therefore, there is a copy of $S^{+}_{d_{k}}$ that is vertex-
disjoint from $\bigcup\limits_{i=1}^{t}S^{+}_{d_{i}}$. This violates the
maximality of $t$, a contradiction.

Case 2.

$\Delta(\mathcal{H})\geq\frac{1}{\bigcup\limits_{i=1}^{k-1}((r-1)d_{i}+1)}\bigg{(}\binom{n}{r}-\binom{n-k+1}{r}\bigg{)}.$

Let $u$ be a vertex of maximum degree. Since $d(u)\leq\binom{n-1}{r-1}$,

$\displaystyle|E(\mathcal{H})|-d(u)$ $\displaystyle>\mathop{max}\limits_{1\leq
i\leq
k}\bigg{\\{}\binom{n}{r}-\binom{n-i+1}{r}+ex_{r}\Big{(}n-i+1,S^{+}_{d_{i}}\Big{)}\bigg{\\}}-\binom{n-1}{r-1}$
$\displaystyle=\mathop{max}\limits_{1\leq i\leq
k}\bigg{\\{}\binom{n-1}{r}-\binom{n-(i-1)}{r}+ex_{r}\Big{(}n-(i-1),S^{+}_{d_{i}}\Big{)}\bigg{\\}}$
$\displaystyle\overset{d^{\prime}_{j}=d_{j+1}}{\geq}\mathop{max}\limits_{1\leq
j\leq
k-1}\bigg{\\{}\binom{n-1}{r}-\binom{n-j}{r}+ex_{r}\Big{(}n-j,S^{+}_{d^{\prime}_{j}}\Big{)}\bigg{\\}}$
$\displaystyle=ex_{r}\bigg{(}n-1,\bigcup\limits_{i=2}^{k}S^{+}_{d_{i}}\bigg{)}.$

Therefore, we can consider a copy of $\bigcup\limits_{i=2}^{k}S^{+}_{d_{i}}$
(that we indicate as $\bigcup\limits_{i=2}^{k}S^{+}_{d_{i}}$ in the sequel)
after removing $u$ from $\mathcal{H}$, and apply induction on the resulting
hypergraph.

Next we will show that there is a copy of $S^{+}_{d_{1}}$ with center $u$ that
is vertex-disjoint from $\bigcup\limits_{i=2}^{k}S^{+}_{d_{i}}$. Observe that
$u$ and any vertex $v\in V(\bigcup\limits_{i=2}^{k}S^{+}_{d_{i}})$ are
contained in at most $\binom{n-2}{r-2}$ common hyperedges. Therefore the
number of hyperedges containing $u$ and a vertex of
$\bigcup\limits_{i=2}^{k}S^{+}_{d_{i}}$ is at most

$\bigcup\limits_{i=2}^{k}((r-1)d_{i}+1)\binom{n-2}{r-2}=O(n^{r-2}).$

Note that $d(u)=\Omega(n^{r-1})$. Therefore if we remove the hyperedges
incident to $\bigcup\limits_{i=2}^{k}S^{+}_{d_{i}}$, there still are
$\Omega(n^{r-1})$ hyperedges incident to $u$. As $r\geq 3$ and $d_{1}\geq 2$,
we may apply Theorem 1.2 to these hyperedges to get a copy of $S^{+}_{d_{1}}$
that is vertex-disjoint from $\bigcup\limits_{i=2}^{k}S^{+}_{d_{i}}$, i.e.,
$\mathcal{H}$ contains a copy of $\bigcup\limits_{i=1}^{k}S^{+}_{d_{i}}$, a
contradiction.

Thus, the theorem holds. ∎

##  3 Proof of Theorem 1.7

Before proving Theorem 1.7, we would like to introduce an average degree lemma
obtained by Khormali and Palmer [21] that will be used in our proof.

######  Lemma 3.1 (Average Degree Lemma, [21]).

Fix integers $d$ and $\Delta$ and a constant $0\leq\varepsilon<1$. If
$\mathcal{H}$ is a hypergraph with average degree at least $d-\varepsilon$ and
maximum degree at most $\Delta$, then the number of vertices in $\mathcal{H}$
of degree less than $d$ is at most

$\frac{\Delta-d+\varepsilon}{\Delta-d+1}n.$

In particular, the number of vertices in $\mathcal{H}$ of degree at least $d$
is $\Omega(n)$.

Now we are ready to prove Theorem 1.7. Let $\mathcal{H}$ be an $r$-uniform
$n$-vertex linear hypergraph that is
$\bigcup\limits_{i=1}^{k}S^{+}_{d_{i}}$-free. Let $A$ be the vertex set each
vertex of which has degree at least some fixed large enough constant
$D=D(d_{1},k,r)$. If $|A|\geq k$, then we can greedily embed a copy of
$\bigcup\limits_{i=1}^{k}S^{+}_{d_{i}}$ into $\mathcal{H}$. Thus we have
$|A|\leq k-1$.

After removing the vertices of $A$ and the hyperedges incident to them from
$\mathcal{H}$, we obtain an $r$-uniform hypergraph $\mathcal{H}^{\prime}$. The
maximum degree in $\mathcal{H}^{\prime}$ is less than $D$. Let $|A|=i-1$.
Therefore $1\leq i\leq k$. If the average degree in $\mathcal{H^{\prime}}$ is
at least $d_{i}-\varepsilon$ for any $0<\varepsilon<1$, then by Lemma 3.1 we
have $\Omega(n)$ vertices of degree at least $d_{i}$ in
$\mathcal{H^{\prime}}$. In this case we can greedily embed a copy of
$\bigcup\limits_{t=i}^{k}S^{+}_{d_{t}}$ into $\mathcal{H^{\prime}}$. Then,
together with $\bigcup\limits_{t=1}^{i-1}S^{+}_{d_{t}}$ consisting of
hyperedges incident to $A$, we obtain a copy of
$\bigcup\limits_{t=1}^{k}S^{+}_{d_{t}}$ in $\mathcal{H}$, a contradiction.

Therefore, the average degree in $\mathcal{H^{\prime}}$ is at most $d_{i}-1$.
Thus we have

$|E(\mathcal{H^{\prime}})|\leq\frac{d_{i}-1}{r}(n-|A|).$

Let $B$ be the vertex set of $\mathcal{H^{\prime}}$, i.e.,
$B=V(\mathcal{H})\setminus A$. Denote by $E(A,B)$ the hyperedge set of
$\mathcal{H}$ that contain at least one vertex of $A$ and one vertex of $B$.
To count the size of $E(A,B)$, we first count the number of pairs
$(h,\\{u,v\\})$ where $h$ is a hyperedge of $\mathcal{H}$, $u\in A\cap h$ and
$v\in B\cap h$. Let $h\in E(A,B)$. Then we have $|A\cap h|$ choices for $u$
and $|B\cap h|$ choices for $v$. Thus the number of pairs $(h,\\{u,v\\})$ is

$\sum\limits_{h\in E(A,B)}|A\cap h||B\cap h|\geq\sum\limits_{h\in
E(A,B)}(r-1)=|E(A,B)|(r-1).$

On the other hand, for a fixed $u$ and $v$ there is at most one hyperedge
containing them, as $\mathcal{H}$ is linear. Thus, the number of pairs
$(h,\\{u,v\\})$ is at most $|A|(n-|A|)$.

Combining these two estimates for the number of pairs $(h,\\{u,v\\})$, and
solving for $|E(A,B)|$ gives

$|E(A,B)|\leq\frac{|A|}{r-1}(n-|A|).$

Furthermore, the maximum number of hyperedges contained completely in $A$ is
at most $\binom{|A|}{2}/\binom{r}{2}$, as each pair of vertices in $A$ is
contained in at most one hyperedge.

Therefore, the hyperedge number of $\mathcal{H}$ is

$|E(\mathcal{H})|\leq\frac{d_{i}-1}{r}(n-i+1)+\frac{i-1}{r-1}(n-i+1)+\frac{\binom{i-1}{2}}{\binom{r}{2}}.$

As $1\leq i\leq k$, we have that for $n$ large enough,

$|E(\mathcal{H})|\leq\mathop{max}\limits_{1\leq i\leq
k}\bigg{\\{}\frac{d_{i}-1}{r}(n-i+1)+\frac{i-1}{r-1}(n-i+1)+\frac{\binom{i-1}{2}}{\binom{r}{2}}\bigg{\\}}.$

Just like the construction of the extremal linear hypergraph that Khormali and
Palmer presented for the sharpness statement in Theorem 1.6, we can present a
construction that satisfies the sharpness assertion. Denote by $[r]^{d}$ the
integer lattice formed by $d$-tuples from the set $[r]$. Indeed, we can view
$[r]^{d}$ as a hypergraph $\mathcal{H}$, as follows. The vertex set of
$\mathcal{H}$ consists of all $d$-tuples from the set $[r]$. And the
collection of $d$-tuples that are fixed in all but one coordinate form a
hyperedge. Thus, $[r]^{d}$ is an $r^{d}$-vertex $r$-uniform hypergraph with
$d\cdot r^{d-1}$ hyperedges. It is easy to check that $[r]^{d}$ is linear, as
any two hyperedges of it are either disjoint or intersect in exactly one
vertex. Furthermore, $[r]^{d}$ is $d$-regular, as every vertex of it is
included in exactly $d$ hyperedges. Note that the hyperedges of $[r]^{d}$ can
be partitioned into $d$ classes, each of which forms a matching. This gives a
natural proper hyperedge-coloring of $\mathcal{H}$. We call such a proper
hyperedge-coloring a canonical coloring.

The Cartesian product of two sets $A$ and $B$, denoted $A\times B$, is the set
of all ordered pairs $(a,b)$ where $a\in A$ and $b\in B$. Let $\mathcal{H}$
and $\mathcal{G}$ be two hypergraphs. Then the Cartesian product
$\mathcal{H}\times\mathcal{G}$ of $\mathcal{H}$ and $\mathcal{G}$ is defined
as the hypergraph on vertex set $V(\mathcal{H})\times V(\mathcal{G})$ with
hyperedge set

$E(\mathcal{H}\times\mathcal{G})=\\{\\{u\\}\times e|u\in V(\mathcal{H}),e\in
E(\mathcal{G})\\}\cup\\{f\times\\{v\\}|v\in V(\mathcal{G}),f\in
E(\mathcal{H})\\}.$

Note that if $\mathcal{H}$ is $r$-uniform and $\mathcal{G}$ is $s$-uniform,
then the hyperedges in $\\{f\times\\{v\\}|v\in V(\mathcal{G}),f\in
E(\mathcal{H})\\}$ are of size $r$. We claim that if two hypergraphs
$\mathcal{H}$ and $\mathcal{G}$ are both linear, then
$\mathcal{H}\times\mathcal{G}$ is linear. Indeed, for any two vertices
$u_{1}\times v_{1},u_{2}\times v_{2}\in V(\mathcal{H})\times V(\mathcal{G})$,
they can be contained in one hyperedge if either $u_{1}=u_{2}$ or
$v_{1}=v_{2}$. Assume that $u_{1}=u_{2}=u$. Then we note that $u\times v_{1}$
and $u\times v_{2}$ are contained in a hyperedge if and only if $v_{1}$ and
$v_{2}$ are contained in a hyperedge in $\mathcal{G}$.

Now suppose that $n-i+1$ is divisible by $(r-1)^{i-1}$ and $r^{d_{i}-1}$ for
any $1\leq i\leq k$. We can construct a hypergraph $\mathcal{H}^{*}_{i}$ as
follows. The vertex set of $\mathcal{H}^{*}_{i}$ embodies two disjoint vertex
subsets $A^{*}$ and $B^{*}$, where $A^{*}=\\{a_{1},a_{2},\ldots,a_{i-1}\\}$
and $B^{*}$ has $n-i+1$ vertices whose vertices are partitioned into distinct
copies of $[r-1]^{i-1}\times[r]^{d_{i}-1}$. Assume that all hyperedges of size
$r-1$ in the copies of $[r-1]^{i-1}\times[r]^{d_{i}-1}$ inherit their
canonical hyperedge-coloring from the original hypergraph $[r-1]^{i-1}$. The
hyperedge set of $\mathcal{H}^{*}_{i}$ is partitioned into two hyperedge
subsets $C^{*}$ and $D^{*}$, where $C^{*}$ consists of all hyperedges of size
$r$ in the copies of $[r]^{d_{i}-1}$ in $B^{*}$, and $D^{*}$ consists of every
$h\cup\\{a_{j}\\}$ where $a_{j}\in A^{*}$ and $h$ is a hyperedge of color $j$
in a copy of $[r-1]^{i-1}$ with a canonical hyperedge-coloring. Except for the
above two hyperedge sets $C^{*}$ and $D^{*}$, we can embed
$\binom{i-1}{2}/\binom{r}{2}$ hyperedges into $A^{*}$ without violating the
linear property of $\mathcal{H}$.

We claim that $\mathcal{H}^{*}_{i}$ is linear. For any two hyperedges of
$C^{*}$, they are hyperedges from copies of the linear hypergraph
$[r]^{d_{i}-1}$, and therefore intersect in at most one vertex. As for any two
hyperedges of $D^{*}$, they either have the same color and therefore intersect
in a vertex in $A^{*}$ but not in $B^{*}$, or have different colors and may
intersect in $B^{*}$ in one vertex, but do not intersect in $A^{*}$. And a
hyperedge of $C^{*}$ and a hyperedge of $D^{*}$ intersect in at most one
vertex by the construction of $[r-1]^{i-1}\times[r]^{d_{i}-1}$.

Next step is to show that $\mathcal{H}^{*}_{i}$ is
$\bigcup\limits_{i=1}^{k}S^{+}_{d_{i}}$-free. Every vertex in $B^{*}$ is
incident to exactly $d_{i}-1$ hyperedges that are contained completely in
$B^{*}$. Therefore, if there exists a copy of
$\bigcup\limits_{j=1}^{k}S^{+}_{d_{j}}$ in $\mathcal{H}^{*}_{i}$, then it must
use $i$ distinct vertices in $A^{*}$. Since $A^{*}$ has only $i-1$ vertices,
we have that $\mathcal{H}^{*}_{i}$ is
$\bigcup\limits_{i=1}^{k}S^{+}_{d_{i}}$-free.

Fix $1\leq i\leq k$. The number of hyperedge in $\mathcal{H}^{*}_{i}$ is

$\displaystyle|E(\mathcal{H}^{*}_{i})|$
$\displaystyle=|E(A^{*},B^{*})|+|E(A^{*})|+|E(B^{*})|$
$\displaystyle\geq(i-1)(r-1)^{i-2}\cdot\frac{n-i+1}{(r-1)^{i-1}}+\frac{\binom{i-1}{2}}{\binom{r}{2}}+(d_{i}-1)r^{d_{i}-2}\cdot\frac{n-i+1}{r^{d_{i}-1}}$
$\displaystyle=\bigg{(}\frac{d_{i}-1}{r}+\frac{i-1}{r-1}\bigg{)}(n-i+1)+\frac{\binom{i-1}{2}}{\binom{r}{2}}.$

Thus among all $1\leq i\leq k$, we can get an extremal hypergraph
$\mathcal{H}^{*}$ such that

$\displaystyle|E(\mathcal{H}^{*})|$ $\displaystyle=\mathop{max}\limits_{1\leq
i\leq k}\\{|E(\mathcal{H}^{*}_{i})|\\}$
$\displaystyle\geq\mathop{max}\limits_{1\leq i\leq
k}\bigg{\\{}\bigg{(}\frac{d_{i}-1}{r}+\frac{i-1}{r-1}\bigg{)}(n-i+1)+\frac{\binom{i-1}{2}}{\binom{r}{2}}\bigg{\\}}.$

∎

##  4 Proof of Theorem 1.10

Let $G$ be a graph, $\mathcal{G}$ a Berge-$G$ and $f$ an arbitrary bijection
from $\mathcal{G}$ to $G$ such that $f(h)\subset h$ for any $h\in
E(\mathcal{G})$, i.e., $f$ is a bijection that establishes that $\mathcal{G}$
is a Berge-$G$. We call the graph formed by the image of $f$ a skeleton of
$\mathcal{G}$. Thus, a skeleton of $\mathcal{G}$ is a copy of $G$ embedded
into the vertex set of $\mathcal{G}$.

Before we prove Theorem 1.10, we first introduce the following two useful
lemmas.

######  Lemma 4.1 ([21]).

Fix integers $r\geq 2,\ell\leq r$ and let $\mathcal{G}$ be an $r$-uniform
hypergraph. If $v$ is a vertex of degree $d(v)\geq\ell$ in $\mathcal{G}$, then
$\mathcal{G}$ contains a Berge-$S_{\ell}$ with center $v$.

######  Lemma 4.2 ([21]).

Fix integers $\ell>r\geq 2$ and let $\mathcal{G}$ be an $r$-uniform
hypergraph. If $v$ is a vertex of degree $d(v)>\binom{\ell-1}{r-1}$ in
$\mathcal{G}$, then $\mathcal{G}$ contains a Berge-$S_{\ell}$ with center $v$.

Now we are ready to prove Theorem 1.10. For the lower bound, we need to
construct an extremal hypergraph. Fix $1\leq s\leq k-1$. We construct a
hypergraph $\mathcal{H}^{*}_{s}$ as follows. We consider a
$(d_{s+1}-1)$-regular $(r-s)$-uniform hypergraph on a vertex set $B^{*}$ of
size $n-s$. Such a hypergraph exists as $r-s$ divides $n-s$ and $r-s\geq
d_{s+1}$. Then we add a fixed vertex set $A^{*}$ of size $s$ to each hyperedge
to form an $r$-uniform hypergraph on $n$ vertices. Each vertex in $B^{*}$ has
degree $d_{s+1}-1$, so the skeleton of any Berge-$S_{d_{j}}$ for $1\leq j\leq
s+1$ must use at least one vertex from $A^{*}$. Therefore,
$\mathcal{H}^{*}_{s}$ is Berge-$\bigcup\limits_{j=1}^{k}S_{d_{j}}$-free and
has

$|E(\mathcal{H}^{*}_{s})|=\frac{d_{s+1}-1}{r-s}(n-s).$

Thus, among all $\\{\mathcal{H}^{*}_{s}\\}$ for $1\leq s\leq k-1$, we can get
an extremal hypergraph $\mathcal{H}^{*}$ such that

$|E(\mathcal{H}^{*})|=\mathop{max}\limits_{1\leq s\leq
k-1}\bigg{\\{}\frac{d_{s+1}-1}{r-s}(n-s)\bigg{\\}}.$

Next we prove the upper bound. Let $\mathcal{H}$ be an $n$-vertex
Berge-$\bigcup\limits_{i=1}^{k}S_{d_{i}}$-free $r$-uniform hypergraph. Let $A$
be the vertex set of $\mathcal{H}$ each vertex of which has degree greater
than some fixed large enough constant $D=D(d_{1},k,r)$, and let
$B=V(\mathcal{H})\setminus A$. Assume that $|A|=s$. Then we have the following
claim.

######  Claim 4.1.

$s\leq k-1$.

###### Proof.

Suppose to the contrary that $s\geq k$. Let $A^{\prime}\subseteq A$ be a set
of $k$ vertices of degree at least $D$. As $D$ is large enough, it is easy to
see that there is a Berge-$S_{d_{k-1}}$ with center in $A^{\prime}$ but whose
skeleton is otherwise disjoint from $A^{\prime}$.

Now we suppose that there exists a Berge-$\bigcup\limits_{j=1}^{k-1}S_{d_{j}}$
whose skeleton intersects $A^{\prime}$ in $k-1$ vertices. This
Berge-$\bigcup\limits_{j=1}^{k-1}S_{d_{j}}$ has
$\bigcup\limits_{j=1}^{k-1}d_{j}$ hyperedges and its skeleton spans
$\bigcup\limits_{j=1}^{k-1}(d_{j}+1)$ vertices. Let $u$ be the vertex in
$A^{\prime}$ not in the skeleton of this
Berge-$\bigcup\limits_{j=1}^{k-1}d_{j}$. Then we remove the hyperedges of the
Berge-$\bigcup\limits_{j=1}^{k-1}d_{j}$ from $\mathcal{H}$. As $D$ is large
enough, by Lemma 4.1 or Lemma 4.2 we have that among the remaining hyperedges
there is a Berge-$S_{\cup_{1\leq j\leq k-1}(d_{j}+1)+d_{k}}$, denoted
$\mathcal{S}$, with center $u$. Thus $\mathcal{S}$ is hyperedge-disjoint from
the Berge-$\bigcup\limits_{j=1}^{k-1}S_{d_{j}}$. However, the skeleton of both
of these subhypergraphs may intersect. At most
$\bigcup\limits_{j=1}^{k-1}(d_{j}+1)$ vertices of the skeleton of
$\mathcal{S}$ are shared with the skeleton of the
Berge-$\bigcup\limits_{j=1}^{k-1}S_{d_{j}}$. Therefore, there is a
Berge-$S_{d_{k}}$ whose skeleton is disjoint from the skeleton of the
Berge-$\bigcup\limits_{j=1}^{k-1}S_{d_{j}}$. In particular, we have a
Berge-$\bigcup\limits_{j=1}^{k}S_{d_{j}}$, a contradiction. This confirms the
claim. ∎

We also need the following claim before we can complete our proof.

######  Claim 4.2.

If $s=k-1$, then every vertex in $B$ has degree at most $d_{k}-1$. If $s<k-1$,
then the average degree of the vertices in $B$ is at most $d_{s+1}-1$.

###### Proof.

We first consider the case that $s=k-1$, and suppose that there is a vertex
$v$ in $B$ of degree at least $d_{k}$. Let us remove vertices from the
hyperedges incident to $v$ so that the resulting hyperedges are disjoint from
$A$ and of size exactly $d_{k}$. This is possible as $r\geq d_{1}+k-1$. By
Lemma 4.1, there is a Berge-$S_{d_{k}}$ with center $v$ among these
$d_{k}$-uniform hyperedges. The skeleton of this Berge-$S_{d_{k}}$ is
necessarily contained in $B$. It is easy to see that this Berge-$S_{d_{k}}$
corresponds to a Berge-$S_{d_{k}}$, denoted by $\mathcal{S}$, in $\mathcal{H}$
whose skeleton is contained in $B$. Since the degrees of the vertices in $A$
are large enough, we can construct a
Berge-$\bigcup\limits_{j=1}^{k-1}S_{d_{j}}$ whose hyperedges and skeleton are
disjoint from those of $\mathcal{S}$. Therefore $\mathcal{H}$ contains a
Berge-$\bigcup\limits_{j=1}^{k}S_{d_{j}}$, a contradiction.

Next we consider the case that $s<k-1$. Suppose that the average degree of the
vertices in $B$ is at least $d_{s+1}-1+\varepsilon$ for some constant
$0<\varepsilon\leq 1$. Thus the sum of degrees of the vertices in $B$ is at
least $(d_{s+1}-1+\varepsilon)(n-s)$. Denote by $t$ the number of vertices of
degree at most $d_{s+1}-1$ in $B$. Recall that the vertices of $B$ have degree
at most $D$. Thus the sum of degrees of the vertices in $B$ is at most
$(d_{s+1}-1)t+D(n-s-t)$.

Combining these estimates and solving for $t$ gives

$t\leq\frac{D-d_{s+1}+1-\varepsilon}{D-d_{s+1}+1}(n-s)=(1-\varepsilon^{\prime})(n-s)$

for some $\varepsilon^{\prime}>0$ depending only on $\varepsilon,d_{s+1},k$
and $r$. Therefore, the number of vertices of degree at least $d_{s+1}$ is
$\varepsilon^{\prime}n=\Omega(n)$.

Let us call a pair of vertices $u,v\in B$ _far_ if they do not share a common
neighbor in $B$ (they may still have a common neighbor in $A$). Since the
vertices of $B$ have constant maximum degree, we can find a subset
$B^{\prime}\subset B$ of size $\Omega(n)$ such that all vertices have degree
at least $d_{s+1}$ and all pairs of vertices are far.

For each vertex $u\in B^{\prime}$, there is a Berge-$S_{d_{s+1}}$ with center
$u$. The hyperedges of this Berge-$S_{d_{s+1}}$ may intersect $A$. However, as
$r\geq d_{1}+k-1>d_{1}+s$ we can find a skeleton of this Berge-$S_{d_{s+1}}$
that does not include a vertex of $A$. Since any two vertices in $B^{\prime}$
do not share a common neighbor in $B$, we have a collection of pairwise
hyperedge-disjoint copies of a Berge-$S_{d_{s+1}}$ whose skeletons are also
pairwise vertex-disjoint. Since $n$ is large enough, we can find a copy of a
Berge-$\bigcup\limits_{j=s+1}^{k}S_{d_{j}}$, denoted by $\mathcal{S}$. Since
the degrees of the vertices in $A$ are large enough, we can construct a
Berge-$\bigcup\limits_{j=1}^{s}S_{d_{j}}$ whose hyperedges and skeleton are
disjoint from those of $\mathcal{S}$. Therefore we have a
Berge-$\bigcup\limits_{j=1}^{k}S_{d_{j}}$, a contradiction. This confirms our
second claim. ∎

Now, let us estimate the number of hyperedges in $\mathcal{H}$. As each
hyperedge incident to $A$ is counted at most $s=|A|$ times,

$\sum\limits_{u\in A}d(u)\leq s|E(\mathcal{H})|.$

Let $d(B)$ be the average degree of the vertices in $B$ and observe that

$\displaystyle r|E(\mathcal{H})|$ $\displaystyle=\sum\limits_{u\in
A}d(u)+\sum\limits_{v\in B}d(v)$ $\displaystyle\leq
s|E(\mathcal{H})|+d(B)(n-s).$

Solving for $|E(\mathcal{H})|$ gives

$|E(\mathcal{H})|\leq\frac{d(B)}{r-s}(n-s).$

By Claim 4.2 we have

$|E(\mathcal{H})|\leq\mathop{max}\limits_{1\leq s\leq
k-1}\bigg{\\{}\frac{d_{s+1}-1}{r-s}(n-s)\bigg{\\}}.$

∎

##  5 Proof of Theorem 1.11

In our proof, we make use of the following known result.

######  Lemma 5.1 ([14]).

Fix integers $\ell\geq 1$ and $r\geq 3$.

  * (1)

If $\ell>r$, then

$ex_{r}(n,\mbox{Berge-}S_{\ell})\leq\binom{\ell}{r}\frac{n}{\ell}.$

Furthermore, this bound is sharp whenever $\ell$ divides $n$.

  * (2)

If $\ell\leq r$, then

$ex_{r}(n,\mbox{Berge-}S_{\ell})\leq\frac{\ell-1}{r}n.$

Furthermore, this bound is sharp whenever $r$ divides $n$.

Now we are ready to prove Theorem 1.11. We start again with the lower bounds.
If $r\leq d_{k}+k-2$, then we can present an extremal construction for an
$r$-uniform $n$-vertex Berge-$\bigcup\limits_{1\leq i\leq k}S_{d_{i}}$-free
hypergraph $\mathcal{H}_{i}$, as follows. Fix $1\leq i\leq k$. We put
$n-i+1=q_{i}\cdot d_{i}+t_{i}$ with $0\leq t_{i}<d_{i}$. Let
$V(\mathcal{H}_{i})=A^{*}_{i}\cup B^{*}_{i}$ with $|A^{*}_{i}|=i-1$ and
$|B^{*}_{i}|=n-i+1$. For the case that $i=k$, we partition the vertices of
$B^{*}_{k}$ into $q_{k}$ classes of size $d_{k}$ and a single class of size
$t_{k}$ if $t_{k}>0$. For each partition class $S^{*}_{k}$ of $B^{*}_{k}$ we
form a complete $r$-uniform hypergraph $K^{r}_{d_{k}+k-1}$
($K^{r}_{t_{k}+k-1}$) on the vertices of $A^{*}_{k}\cup S^{*}_{k}$. Thus we
have

$|E(\mathcal{H}_{k})|=\bigg{(}\binom{d_{k}+k-1}{r}-\binom{k-1}{r}\bigg{)}\frac{n-k+1-t_{k}}{d_{k}}+\binom{t_{k}+k-1}{r}.$

The skeleton of any Berge-$S_{d_{j}}$ for $1\leq j\leq k$ in $\mathcal{H}_{k}$
must use at least one vertex of $A^{*}_{k}$. But there are only $k-1$ vertices
in $A^{*}_{k}$. Therefore we have $\mathcal{H}_{k}$ is
Berge-$\bigcup\limits_{1\leq j\leq k}S_{d_{j}}$-free for any $1\leq i\leq k$.
Thus we can choose $i$ such that $E(\mathcal{H}_{i})$ (denoted by
$\mathcal{H}^{*}$) attains its maximum value, i.e.,

$|E(\mathcal{H}^{*})|=\mathop{max}\limits_{1\leq i\leq
k}\bigg{\\{}\bigg{(}\binom{d_{i}+i-1}{r}-\binom{i-1}{r}\bigg{)}\frac{n-i+1-t_{i}}{d_{i}}+\binom{t_{i}+i-1}{r}\bigg{\\}}.$

If $r\geq d_{k}+k-1$, then we can present an extremal construction for an
$r$-uniform $n$-vertex Berge-$\bigcup\limits_{1\leq i\leq k}S_{d_{i}}$-free
hypergraph $\mathcal{H}^{\prime}_{k}$, as follows. Since $r-k+1$ divides
$n-k+1$ and $r-k+1\geq d_{k}$, we can construct a $(d_{k}-1)$-regular
$(r-k+1)$-uniform hypergraph on a vertex set $B^{*}$ of size $n-k+1$. Then we
add a fixed vertex set $A^{*}$ of size $k-1$ to each hyperedge to form an
$r$-uniform hypergraph on $n$ vertices. Each vertex in $B^{*}$ has degree
$d_{k}-1$, so the skeleton of any Berge-$S_{d_{j}}$ for $1\leq j\leq k$ must
use at least one vertex from $A^{*}$. Therefore, $\mathcal{H}^{\prime}_{k}$ is
Berge-$\bigcup\limits_{j=1}^{k}S_{d_{j}}$-free and

$|E(\mathcal{H}^{\prime}_{k})|=\frac{d_{k}-1}{r-k+1}(n-k+1).$

Thus we can get an extremal hypergraph $\mathcal{H}^{\prime}$ such that

$|E(\mathcal{H}^{\prime})|=\mathop{max}\limits_{1\leq i\leq
k}\bigg{\\{}\frac{d_{i}-1}{r-i+1}(n-i+1)\bigg{\\}}.$

Next we prove the upper bound. We proceed by induction on $r$. If $r=2$
($r\leq d_{i}+i-1$ for any $1\leq i\leq k$), then a Berge-$S_{d_{i}}$ is
simply a copy of the graph $S_{d_{i}}$ for any $1\leq i\leq k$. By Theorem
1.1, we have

$\displaystyle ex_{2}\bigg{(}n,\mbox{Berge}-\bigcup\limits_{1\leq i\leq
k}S_{d_{i}}\bigg{)}$ $\displaystyle=ex\bigg{(}n,\bigcup\limits_{1\leq i\leq
k}S_{d_{i}}\bigg{)}$ $\displaystyle\leq\mathop{max}\limits_{1\leq i\leq
k}\Bigg{\\{}(i-1)(n-i+1)+\binom{i-1}{2}+\frac{d_{i}-1}{2}(n-i+1)\Bigg{\\}}$
$\displaystyle=\mathop{max}\limits_{1\leq i\leq
k}\bigg{\\{}\frac{n-i+1}{d_{i}}\bigg{(}\binom{d_{i}+i-1}{2}-\binom{i-1}{2}\bigg{)}+\binom{i-1}{2}\bigg{\\}}.$

Let $r\geq 3$ and assume that the statement of the theorem holds for $r-1$.
Let $\mathcal{H}$ be an $r$-uniform $n$-vertex Berge-$\bigcup\limits_{1\leq
i\leq k}S_{d_{i}}$-free hypergraph of size at least $|E(\mathcal{H}^{*})|$.
Let $A$ be the set of vertices in $\mathcal{H}$ of degree larger than some
fixed large enough constant $D=D(d_{1},k,r)$, and let
$B=V(\mathcal{H})\setminus A$. Put $c=|A|$. We first prove the following
claim.

######  Claim 5.1.

$c\leq k-1$.

###### Proof.

Suppose to the contrary that $c\geq k$ and let $A^{\prime}\subseteq A$ be a
set of $k$ vertices of degree at least $D$. As $D$ is large enough, there must
be a Berge-$S_{d_{1}}$ with center in $A^{\prime}$ but whose skeleton is
otherwise disjoint from $A^{\prime}$. Now we suppose that there exists a
Berge-$\bigcup\limits_{j=1}^{k-1}S_{d_{j}}$ whose skeleton intersects
$A^{\prime}$ in $k-1$ vertices. This
Berge-$\bigcup\limits_{j=1}^{k-1}S_{d_{j}}$ has
$\bigcup\limits_{j=1}^{k-1}d_{j}$ hyperedges and its skeleton spans
$\bigcup\limits_{j=1}^{k-1}(d_{j}+1)$ vertices. Let $u$ be the vertex in
$A^{\prime}$ not in the skeleton of this
Berge-$\bigcup\limits_{j=1}^{k-1}d_{j}$. Then we remove the hyperedges of the
Berge-$\bigcup\limits_{j=1}^{k-1}d_{j}$ from $\mathcal{H}$. As $D$ is large
enough, by Lemma 4.2 we have that among the remaining hyperedges there is a
Berge-$S_{\cup_{1\leq j\leq k-1}(d_{j}+1)+d_{k}}$, denoted by $\mathcal{S}$,
with center $u$. Thus $\mathcal{S}$ is hyperedge-disjoint from the
Berge-$\bigcup\limits_{j=1}^{k-1}S_{d_{j}}$. However, the skeleton of both of
these subhypergraphs may intersect. At most
$\bigcup\limits_{j=1}^{k-1}(d_{j}+1)$ vertices of the skeleton of
$\mathcal{S}$ are shared with the skeleton of the
Berge-$\bigcup\limits_{j=1}^{k-1}S_{d_{j}}$. Therefore, there is a
Berge-$S_{d_{k}}$ whose skeleton is disjoint from the skeleton of the
Berge-$\bigcup\limits_{j=1}^{k-1}S_{d_{j}}$. In particular, we have a
Berge-$\bigcup\limits_{j=1}^{k}S_{d_{j}}$, a contradiction. ∎

Next we distinguish two cases.

Case 1. $c=k-1$.

We will discuss two subcases.

Subcase 1.1. $r\leq d_{k}+k-2$.

We claim that each vertex of $B$ has degree at most $\binom{d_{k}+k-2}{r-1}$.
Otherwise, by Lemma 4.2 we have that there is a Berge-$S_{d_{k}+k-1}$ with
center $x$ which has degree greater than $\binom{d_{k}+k-2}{r-1}$. The
skeleton of this Berge-$S_{d_{k}+k-1}$ uses at most $k-1$ vertices from $A$,
so there remains a Berge-$S_{d_{k}}$, denoted by $\mathcal{S}$, whose skeleton
is contained in $B$. As $D$ is large enough, we may construct $k-1$ more
pairwise hyperedge-disjoint copies of a Berge-$S_{d_{1}}$ (with pairwise
vertex-disjoint skeletons) that are hyperedge-disjoint from $\mathcal{S}$ and
whose skeletons are vertex-disjoint from the skeleton of $\mathcal{S}$. Thus,
we have a copy of a Berge-$\bigcup\limits_{1\leq i\leq k}S_{d_{i}}$ in
$\mathcal{H}$, a contradiction.

Now we compare $\mathcal{H}$ with $\mathcal{H}_{k}$. Firstly, by definition we
have $|E(\mathcal{H})|\geq|E(\mathcal{H}^{*})|\geq|E(\mathcal{H}_{k})|$.
Suppose that there are two vertices $y\in A$ and $y^{*}\in A^{*}_{k}$ such
that $d_{\mathcal{H}}(y)>d_{\mathcal{H}_{k}}(y^{*})$. For each $1\leq j\leq
r-1$, we define

$E^{y}_{j}=\\{e\setminus A|y\in e\in E(\mathcal{H}),|e\setminus A|=j\\}$

and

$E^{y^{*}}_{j}=\\{f\setminus A^{*}|y^{*}\in f\in
E(\mathcal{H}_{k}),|f\setminus A^{*}|=j\\}.$

It is easy to see that the members of $E^{y}_{j}$ have multiplicity at most
$\binom{k-2}{r-1-j}$ and those in $E^{y^{*}}_{j}$ have multiplicity exactly
$\binom{k-2}{r-1-j}$.

If $k-1\geq r-1$, then by the construction of $\mathcal{H}_{k}$ we have that
each vertex of $B^{*}_{k}$ is in a hyperedge with each subset of $A^{*}_{k}$
of size $r-1$. This implies that $|E^{y^{*}}_{1}|\geq|E^{y}_{1}|$. When
$k-1<r-1$, then $E^{y^{*}}_{1}=E^{y}_{1}=\emptyset$. Therefore, since
$d_{\mathcal{H}}(y)\geq d_{\mathcal{H}_{k}}(y^{*})$, we have that
$|E^{y}_{j}|>|E^{y^{*}}_{j}|$ for some $j\geq 2$. Let $\mathcal{G}$ be the
$j$-uniform hypergraph resulting from deleting all repeated hyperedges in this
$E^{y}_{j}$. Thus, the number of hyperedges in the $j$-uniform hypergraph
$\mathcal{G}$ can be calculated as

$\displaystyle|E(\mathcal{G})|$
$\displaystyle\geq\binom{k-2}{r-1-j}^{-1}|E^{y}_{j}|$
$\displaystyle>\binom{k-2}{r-1-j}^{-1}|E^{y^{*}}_{j}|$
$\displaystyle=\binom{k-2}{r-1-j}^{-1}\binom{k-2}{r-1-j}\frac{n-k+1}{d_{k}}\binom{d_{k}}{j}$
$\displaystyle=\frac{n-k+1}{d_{k}}\binom{d_{k}}{j}$ $\displaystyle\geq
ex_{j}(n-k+1,\mbox{Berge-}S_{d_{k}}).$

Therefore, there is a $j$-uniform Berge-$S_{d_{k}}$ in $\mathcal{G}$ on the
vertices of $B$. As each hyperedge of $\mathcal{G}$ is contained in a
hyperedge of $\mathcal{H}$, this corresponds to a Berge-$S_{d_{k}}$ in
$\mathcal{H}$ whose skeleton is contained in $B$. As before, the degree
condition on the vertices in $A$ guarantees the existence of a
Berge-$\bigcup\limits_{1\leq j\leq k-1}S_{d_{j}}$ that together with this
Berge-$S_{d_{k}}$ forms a Berge-$\bigcup\limits_{1\leq j\leq k}S_{d_{j}}$ in
$\mathcal{H}$, a contradiction.

Therefore, every vertex $y\in A$ has degree at most that of the vertices in
$A^{*}_{k}$ in the construction $\mathcal{H}_{k}$. Every vertex in $B$ has
degree at most $\binom{d_{k}+k-2}{r-1}$ while every vertex in $B^{*}_{k}$ has
degree exactly $\binom{d_{k}+k-2}{r-1}$. Thus,
$|E(\mathcal{H})|\leq|E(\mathcal{H}_{k})|\leq|E(\mathcal{H}^{*})|$.

Subcase 1.2. $r\geq d_{k}+k-1$.

We claim that each vertex of $B$ has degree at most $d_{k}-1$. Suppose that
there is a vertex $v$ in $B$ of degree at least $d_{k}$. Let us remove
vertices from the hyperedges incident to $v$ so that the resulting hyperedges
are disjoint from $A$ and of size exactly $d_{k}$. This is possible as $r\geq
d_{k}+k-1$. By Lemma 4.1, there is a Berge-$S_{d_{k}}$ with center $v$ among
these $d_{k}$-uniform hyperedges. The skeleton of this Berge-$S_{d_{k}}$ is
necessarily contained in $B$. It is easy to see that this Berge-$S_{d_{k}}$
corresponds to a Berge-$S_{d_{k}}$, denoted by $\mathcal{S}$, in $\mathcal{H}$
whose skeleton is contained in $B$. Since the degrees of the vertices in $A$
are large enough, we can construct a
Berge-$\bigcup\limits_{j=1}^{k-1}S_{d_{j}}$ whose hyperedges and skeleton are
disjoint from those of $\mathcal{S}$. Therefore $\mathcal{H}$ contains a
Berge-$\bigcup\limits_{j=1}^{k}S_{d_{j}}$, a contradiction. Thus we have

$\displaystyle r|E(\mathcal{H})|$ $\displaystyle=\sum\limits_{u\in
A}d(u)+\sum\limits_{v\in B}d(v)$
$\displaystyle\leq(k-1)|E(\mathcal{H})|+(d_{k}-1)(n-k+1).$

Solving for $|E(\mathcal{H})|$ gives

$|E(\mathcal{H})|\leq\frac{d_{k}-1}{r-k+1}(n-k+1)\leq
E(\mathcal{H}^{\prime}).$

Case 2. $c<k-1$.

If $r\leq d_{c}+c$, then we claim that $d(B)\leq\binom{d_{c}+c}{r-1}$, where
$d(B)$ is the average degree of the vertices in $B$. Otherwise, we have
$d(B)\geq\binom{d_{c}+c}{r-1}+\varepsilon$ for a constant $0<\varepsilon<1$.
Let $s$ be the number of vertices of degree at most $\binom{d_{c}+c}{r-1}$ in
$B$. Recall that the vertices in $B$ have degree at most $D$. Thus, the sum of
degrees in $B$ is at most $\binom{d_{c}+c}{r-1}s+D(n-c-s)$. Combining these
estimates and solving for $s$ gives

$s\leq\frac{D-\binom{d_{c}+c}{r-1}-\varepsilon}{D-\binom{d_{c}+c}{r-1}}(n-c)=(1-\varepsilon^{\prime})(n-c)$

for some $\varepsilon^{\prime}>0$ not depending on $n$. Therefore, the number
of vertices of degree greater than $\binom{d_{c}+c}{r-1}$ is
$\varepsilon^{\prime}n=\Omega(n)$.

Let us call a pair of vertices $u,v\in B$ far if they do not share a common
neighbor in $B$ (they may still have a common neighbor in $A$). Since the
vertices of $B$ have constant maximum degree we can find a subset $B^{\prime}$
of size $\Omega(n)$ such that all vertices have degree greater than
$\binom{d_{c}+c}{r-1}$ and all pairs of vertices are far.

For each vertex $u\in B^{\prime}$, by Lemma 4.2 we have that there is a
Berge-$S_{d_{c}+c+1}$ with center $u$ whose skeleton is disjoint from $A$.
Since any two vertices of $B^{\prime}$ do not share a common neighbor in $B$,
we have a collection of hyperedge-disjoint copies of a Berge-$S_{d_{c}}$. As
$n$ is large enough, we can find a Berge-$\bigcup\limits_{c+1\leq j\leq
k}S_{d_{j}}$ whose skeleton is disjoint from $A$. And since the degrees of the
vertices in $A$ are large enough, we can construct a
Berge-$\bigcup\limits_{1\leq j\leq c}S_{d_{j}}$ whose hyperedges and skeleton
are disjoint from those of Berge-$\bigcup\limits_{c+1\leq j\leq k}S_{d_{j}}$.
Therefore, $\mathcal{H}$ contains a Berge-$\bigcup\limits_{1\leq i\leq
k}S_{d_{i}}$, a contradiction.

Observe that $\sum\limits_{x\in A}d(x)\leq c|E(\mathcal{H})|$ and

$r|E(\mathcal{H})|=\sum\limits_{x\in B}d(x)+\sum\limits_{x\in A}d(x)\leq
d(B)(n-c)+c|E(\mathcal{H})|.$

Solving for $|E(\mathcal{H})|$ gives

$|E(\mathcal{H})|\leq\frac{\binom{d_{c}+c}{r-1}}{r-c}(n-c).$

Since $c<k-1$,

$|E(\mathcal{H})|\leq\mathop{max}\limits_{1\leq
c<k-1}\bigg{\\{}\frac{\binom{d_{c}+c}{r-1}}{r-c}(n-c)\bigg{\\}}.$

Similarly, if $r\geq d_{c}+c+1$ then we have $d(B)\leq d_{c}+c$. In this case,
we have that

$|E(\mathcal{H})|\leq\mathop{max}\limits_{1\leq
c<k-1}\bigg{\\{}\frac{d_{c}+c}{r-c}(n-c)\bigg{\\}}.$

∎

##  6 Concluding Remarks

We complete this paper with two consequences of our results for generalized
Turán numbers. Given two graphs $H$ and $F$, the generalized Turán number of
$F$, denoted by $ex(n,H,F)$, is defined as the maximum number of copies of a
subgraph $H$ in an $n$-vertex $F$-free graph. These generalized Turán numbers
have been studied by different groups of researchers for many types of graphs.
We refer the interested readers to [1, 20, 27, 36, 37, 38] for more details.

Let $G$ be an $n$-vertex $F$-free graph. We define an $r$-uniform hypergraph
$\mathcal{H}$ with the same vertex set as $G$, such that an $r$-set in
$\mathcal{H}$ is a hyperedge if and only if it is the vertex set of a $K_{r}$
in $G$. Note that this implies that $\mathcal{H}$ contains no Berge-$F$ if $G$
is $F$-free. Thus,

$ex(n,K_{r},F)\leq ex_{r}(n,\mbox{Berge-}F).$ (1)

For the case that $r\geq d_{1}+k-1$, by Theorem 1.10 and (1) we obtain the
following corollary.

######  Corollary 6.1.

Fix integers $d_{1}\geq d_{2}\geq\ldots\geq d_{k}\geq 2$ and $k\geq 2$. If
$r\geq d_{1}+k-1$, then for $n$ large enough,

$ex\bigg{(}n,K_{r},\mbox{Berge-}\bigcup\limits_{1\leq i\leq
k}S_{d_{i}}\bigg{)}\leq\mathop{max}\limits_{1\leq i\leq
k}\bigg{\\{}\frac{d_{i}-1}{r-i+1}(n-i+1)\bigg{\\}}.$

Similarly, for the case that $r\leq d_{1}+k-1$, by Theorem 1.11 and (1) we
obtain the following corollary.

######  Corollary 6.2.

Fix integers $d_{1}\geq d_{2}\geq\ldots\geq d_{k}\geq 2$ and $k\geq 2$. If
$r\leq d_{1}+k-2$, then for $n$ large enough,

$\displaystyle ex\bigg{(}n,K_{r},\mbox{Berge-}\bigcup\limits_{1\leq i\leq
k}S_{d_{i}}\bigg{)}$
$\displaystyle\leq\mathop{max}\bigg{\\{}\mathop{max}\limits_{1\leq i\leq
k}\bigg{\\{}\bigg{(}\binom{d_{i}+i-1}{r}-\binom{i-1}{r}\bigg{)}\left\lceil\frac{n-i+1}{d_{i}}\right\rceil+\binom{i-1}{r},$
$\displaystyle\frac{d_{i}-1}{r-i+1}(n-i+1)\bigg{\\}},\mathop{max}\limits_{1\leq
c<k-1}\bigg{\\{}\frac{\mathop{max}\Big{\\{}\binom{d_{c}+c}{r-1},d_{c}+c\Big{\\}}}{r-c}(n-c)\bigg{\\}}\bigg{\\}}.$

## References

  * [1] N. Alon, C. Shikhelman, Many $T$ copies in $H$-free graphs, J. Combin. Theory Ser. B 121 (2016) 146–172.
  * [2] N. Bushaw, N. Kettle, Turán numbers for forests of paths in hypergraphs, SIAM J. Discrete Math. 28 (2014) 711–721.
  * [3] C. Collier-Cartaino, N. Graber, T. Jiang, Linear Turán numbers of $r$-uniform linear cycles and related Ramsey numbers, Combin. Probab. Comput. 27 (2018) 358–386.
  * [4] R.A. Duke, P. Erdős, Systems of finite sets having a common intersection, in: Proc. 8th Southeastern Conf. Combinatorics, Graph Theory and Computing, Congress. Numer., Vol 19, 1977, pp. 247–252.
  * [5] P. Erdős, A problem on independent $r$-tuples, Ann. Univ. Sci. Budapest 8 (1965) 93–95.
  * [6] B. Ergemlidze, E. Győri, A. Methuku, Asymptotics for the Turán number of cycles in 3-uniform linear hypergraphs, J. Combin. Theory Ser. A 163 (2019) 163–181.
  * [7] B. Ergemlidze, E. Győri, A. Methuku, The exact linear Turán number of the sail, Electron. J. Combin. 28 (4) (2021) #4.39.
  * [8] Z. Füredi, Linear trees in uniform hypergraphs, European J. Combin. 35 (2014) 264–272.
  * [9] Z. Füredi, A. Gyárfás, An extension of Mantel’s theorem to k-graphs, Amer. Math. Monthly 127 (3) (2020) 263–268.
  * [10] Z. Füredi, T. Jiang, Hypergraph Turán numbers of linear cycles, J. Combin. Theory Ser. A 123 (2014) 252–270.
  * [11] Z. Füredi, T. Jiang, R. Seiver, Exact solution of the hypergraph Turán problem for $k$-uniform linear paths, Combinatorica 34 (2014) 299–322.
  * [12] Z. Füredi, M. Simonovits, The history of degenerate (bipartite) extremal graph problems, Erdős centennial, 169–264, Bolyai Soc. Math. Stud., 25, János Bolyai Math. Soc., Budapest, 2013.
  * [13] G. Gao, A. Chang, Q. Sun, Asymptotic Turán number for linear 5-cycle in 3-uniform linear hypergraphs, Discrete Math. 346 (1) (2023) 113128.
  * [14] D. Gerbner, A. Methuku, C. Palmer, General lemmas for Berge-Turán hypergraph problems, European J. Combin. 86 (2020) 103082.
  * [15] D. Gerbner, A. Methuku, M. Vizer, Asymptotics for the Turán number of Berge-$K_{2,t}$, J. Combin. Theory Ser. B 137 (2019) 264–290.
  * [16] D. Gerbner, C. Palmer, Extremal results for Berge-hypergraphs, SIAM J. Discrete Math. 31 (2017) 2314–2327.
  * [17] D. Gerbner, B. Patkós, Extremal Finite Set Theory, first ed., CRC Press, 2018.
  * [18] A. Gyárfás, M. Ruszinkó, G.N. Sárközy, Linear Turán numbers of acyclic triple systems, European J. Combin. 99 (2022) 103435.
  * [19] A. Gyárfás, G.N. Sárközy, Turán and Ramsey numbers in linear triple systems, Discrete Math. 344 (3) (2021) 112258.
  * [20] D. Hei, X. Hou, B. Liu, Some exact results of the generalized Turán numbers for paths, European J. Combin. 110 (2023) 103682.
  * [21] O. Khormali, C. Palmer, Turán numbers for hypergraph star forests, European J. Combin. 102 (2022) 103506.
  * [22] A. Kostochka, D. Mubayi, J. Verstraëte, Turán problems and shadows i: paths and cycles, J. Combin. Theory Ser. A 129 (2015) 57–79.
  * [23] A. Kostochka, D. Mubayi, J. Verstraëte, Turán problems and shadows iii: expansions of graphs, SIAM J. Discrete Math. 29 (2015) 868–876.
  * [24] A. Kostochka, D. Mubayi, J. Verstraëte, Turán problems and shadows ii: trees, J. Combin. Theory Ser. B 122 (2017) 457–478.
  * [25] F. Lazebnik, J. Verstraëte, On hypergraphs of girth five, Electron. J. Combin. 10 (2003) #R25.
  * [26] B. Lidický, H. Liu, C. Palmer, On the Turán number of forests, Electron. J. Combin. 20 (2013) #P62.
  * [27] J. Ma, Y. Qiu, Some sharp results on the generalized Turán numbers, European J. Combin. 84 (2020) 103026.
  * [28] W. Mantel, Problem 28, soln. by H. Gouventak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W.A. Wythoff, Wiskundige Opgaven 10 (1907) 60–61.
  * [29] D. Mubayi, A hypergraph extension of Turán’s theorem, J. Combin. Theory Ser. B 96 (2006) 122–134.
  * [30] D. Mubayi, J. Verstraëte, A survey of Turán problems for expansions, in: Recent Trends in Combinatorics, Springer, 2011.
  * [31] O. Pikhurko, Exact computation of the hypergraph Turán function for expanded complete 2-graphs, J. Combin. Theory Ser. B 103 (2013) 220–225.
  * [32] G.N. Sárközy, Turán and Ramsey numbers in linear triple systems II, Discrete Math. 346 (1) (2023) 113182.
  * [33] C. Tang, H. Wu, S. Zhang, Z. Zheng, On the Turán number of the linear 3-graph $C_{13}$, Electron. J. Combin. 29 (3) (2022) #3.46.
  * [34] C. Timmons, On $r$-uniform linear hypergraphs with no Berge-$K_{2,t}$, Electron. J. Combin. 244 (2017) 4–34.
  * [35] P. Turán, Egy gráfelméleti szélsőértékfeladatról, Mat. Fiz. Lapok 48 (1941) 436–452.
  * [36] J. Wang, The shifting method and generalized Turán number of matchings, European J. Combin. 85 (2020) 103057.
  * [37] L.-P. Zhang, L. Wang, J. Zhou, The generalized Turán number of spanning linear forests, Graphs Combin. 38 (2) (2022) Paper No. 40.
  * [38] X. Zhu, Y. Chen, Generalized Turán number for linear forests, Discrete Math. 345 (10) (2022) 112997.