# Toward a density Corrádi–Hajnal theorem for degenerate hypergraphs

Jianfeng Hou Research was supported by National Natural Science Foundation of
China (Grant No. 12071077). Email<EMAIL_ADDRESS>Center for Discrete
Mathematics, Fuzhou University, Fujian, 350003, China  Caiyun Hu Email:
<EMAIL_ADDRESS>Center for Discrete Mathematics, Fuzhou University,
Fujian, 350003, China  Heng Li Email<EMAIL_ADDRESS>School of
Mathematics, Shandong University, Shandong, 250100, China  Xizhi Liu Research
was supported by ERC Advanced Grant 101020255 and Leverhulme Research Project
Grant RPG-2018-424. Email<EMAIL_ADDRESS>Mathematics Institute and
DIMAP, University of Warwick, Coventry, CV4 7AL, UK  Caihong Yang Email:
<EMAIL_ADDRESS>Center for Discrete Mathematics, Fuzhou University,
Fujian, 350003, China  Yixiao Zhang Email<EMAIL_ADDRESS>Center for
Discrete Mathematics, Fuzhou University, Fujian, 350003, China

###### Abstract

Given an $r$-graph $F$ with $r\geq 2$, let $\mathrm{ex}(n,(t+1)F)$ denote the
maximum number of edges in an $n$-vertex $r$-graph with at most $t$ pairwise
vertex-disjoint copies of $F$. Extending several old results and complementing
prior work [31] on nondegenerate hypergraphs, we initiate a systematic study
on $\mathrm{ex}(n,(t+1)F)$ for degenerate hypergraphs $F$.

For a broad class of degenerate hypergraphs $F$, we present near-optimal upper
bounds for $\mathrm{ex}(n,(t+1)F)$ when $n$ is sufficiently large and $t$ lies
in intervals
$\left[0,\frac{\varepsilon\cdot\mathrm{ex}(n,F)}{n^{r-1}}\right]$,
$\left[\frac{\mathrm{ex}(n,F)}{\varepsilon n^{r-1}},\varepsilon n\right]$, and
$\left[(1-\varepsilon)\frac{n}{v(F)},\frac{n}{v(F)}\right]$, where
$\varepsilon>0$ is a constant depending only on $F$. Our results reveal very
different structures for extremal constructions across the three intervals,
and we provide characterizations of extremal constructions within the first
interval. Additionally, for graphs, we offer a characterization of extremal
constructions within the second interval. Our proof for the first interval
also applies to a special class of nondegenerate hypergraphs, including those
with undetermined Turán densities, partially improving a result in [31].

Keywords: Turán problems, the Corrádi–Hajnal Theorem, the Kővári-Sós-Turán
Theorem, Zarankiewicz problem, $F$-matching, $r$-partite $r$-graphs.

##  1 Introduction

###  1.1 Motivation

Fix an integer $r\geq 2$, an $r$-graph $\mathcal{H}$ is a collection of
$r$-subsets of some finite set $V$. We identify a hypergraph $\mathcal{H}$
with its edge set and use $V(\mathcal{H})$ to denote its vertex set. The size
of $V(\mathcal{H})$ is denoted by $v(\mathcal{H})$. Given a vertex $v\in
V(\mathcal{H})$, the degree $d_{\mathcal{H}}(v)$ of $v$ in $\mathcal{H}$ is
the number of edges in $\mathcal{H}$ containing $v$. We use
$\delta(\mathcal{H})$, $\Delta(\mathcal{H})$, and $d(\mathcal{H})$ to denote
the minimum degree, the maximum degree, and the average degree of
$\mathcal{H}$, respectively. We will omit the subscript $\mathcal{H}$ if it is
clear from the context.

Given two $r$-graphs $F$ and $\mathcal{H}$, the $F$-matching number
$\nu(F,\mathcal{H})$ of $\mathcal{H}$ is the maximum of vertex-disjoint copies
of $F$ in $\mathcal{H}$. This extends the definition the matching number
$\nu(\mathcal{H})$ of $\mathcal{H}$ as
$\nu(\mathcal{H})=\nu(K_{r}^{r},\mathcal{H})$, where $K_{\ell}^{r}$ denotes
the complete $r$-graph with $\ell$ vertices. The study of the following
problem encompasses several central topics in Extremal Combinatorics. Given an
$r$-graph $F$ and integers $n,t\in\mathbb{N}$:

What constraints on an $n$-vertex $r$-graph $\mathcal{H}$ force it to satisfy
$\nu(F,\mathcal{H})\geq t+1$? ($\ast$)

There are several classical result on this topic from the minimum degree
perspective. For example, Corrádi and Hajnal [6] proved the following result
for $K_{3}$.

######  Theorem 1.1 (Corrádi–Hajnal [6]).

Suppose that $n,t\in\mathbb{N}$ are integers with $t\leq n/3$. Then every
$n$-vertex graph $G$ with $\delta(G)\geq
t+\left\lfloor\frac{n-t}{2}\right\rfloor$ contains at least $t$ vertex-
disjoint copies of $K_{3}$, i.e.

$\displaystyle\delta(G)\geq
t+\left\lfloor\frac{n-t}{2}\right\rfloor\quad\Rightarrow\quad\nu(K_{3},G)\geq
t.$

Later, Theorem 1.1 was extended to all complete graphs in the classical
Hajnal–Szemerédi Theorem [27], which implies that for all integers
$n\geq\ell\geq 2$, $t\leq\lfloor n/(\ell+1)\rfloor$, and for every $n$-vertex
graph $G$,

$\displaystyle\delta(G)\geq
t+\left\lfloor\frac{\ell-1}{\ell}(n-t)\right\rfloor\quad\Rightarrow\quad\nu(K_{\ell+1},G)\geq
t.$

There are many further extensions of Theorem 1.1 to general graphs (see e.g.
[3, 38]) and hypergraphs (see e.g. [49]). We refer the reader to a survey [41]
by Kühn and Osthus for further related results.

Problem ($\ast$ ‣ 1.1) becomes much harder when considered from the average
degree perspective. For $r=2$ and $F=K_{2}$, the celebrated Erdős–Gallai
Theorem [10] states that for all integers $n,\ell\in\mathbb{N}$ with $t+1\leq
n/2$ and for every $n$-vertex graph $G$,

$\displaystyle|G|>\max\left\\{\binom{2t+1}{2},\binom{n}{2}-\binom{n-t}{2}\right\\}\quad\Rightarrow\quad\nu(G)\geq
t+1.$

Extending the Erdős–Gallai Theorem to $r$-graphs for $r\geq 3$ is a major open
problem in Extremal Set Theory. Despite substantial effort, the following
conjecture of Erdős is still open in general (see e.g. [15, 16, 17, 32] for
some recent progress on this topic).

######  Conjecture 1.2 (Erdős [9]).

Suppose that $n,t,r\in\mathbb{N}$ satisfy $r\geq 3$ and $t+1\leq n/r$. Then
for every $n$-vertex $r$-graph $\mathcal{H}$,

$\displaystyle|\mathcal{H}|>\max\left\\{\binom{r(t+1)-1}{r},\binom{n}{r}-\binom{n-t}{r}\right\\}\quad\Rightarrow\quad\nu(\mathcal{H})\geq
t+1.$

In the special case where $t=1$, Problem ($\ast$ ‣ 1.1) exhibits a close
relationship with the Turán problem. Fix an $r$-graph $F$, we say an $r$-graph
$\mathcal{H}$ is $F$-free if $\nu(F,\mathcal{H})=0$. In other words,
$\mathcal{H}$ does not contains $F$ as a subgraph. The Turán number
$\mathrm{ex}(n,F)$ of $F$ is the maximum number of edges in an $F$-free
$r$-graph on $n$ vertices. The Turán density of $F$ is defined as
$\pi(F):=\lim_{n\to\infty}\mathrm{ex}(n,F)/\binom{n}{r}$, the existence of the
limit follows from a simple averaging argument of Katona, Nemetz, and
Simonovits [34]. Let $\mathrm{EX}(n,F)$ denote the collection of all
$n$-vertex $F$-free $r$-graphs with exactly $\mathrm{ex}(n,F)$ edges. Members
in $\mathrm{EX}(n,F)$ the extremal constructions of $F$. The study of
$\mathrm{ex}(n,F)$ and $\mathrm{EX}(n,F)$ is a central topic in Extremal
Combinatorics. The celebrated Turán Theorem states that
$\mathrm{EX}(n,K_{\ell+1})=\\{T(n,\ell)\\}$ for all $n\geq\ell\geq 2$, where
$T(n,\ell)$ denote the balanced $\ell$-partite graph with $n$ vertices.

We call an $r$-graph $F$ nondegenerate if $\pi(F)>0$, and degenerate if
$\pi(F)=0$. By a theorem of Erdős [8], an $r$-graph $F$ is degenerate iff it
is $r$-partite, i.e. the vertex set of $F$ can be partitioned into $r$ parts
such that every edge contains exactly one vertex from each part. The
celebrated Erdős–Stone–Simonovits Theorem [13, 14] provides a satisfying bound
for $\mathrm{ex}(n,F)$ when $F$ is a nondegenerate graph. However, determining
$\mathrm{ex}(n,F)$ (even asymptotically) for degenerate graphs and $r$-graphs
with $r\geq 3$ remains a challenging problem in general. We refer the reader
to surveys [24, 35] for more related results.

Our focus in this work lies in exploring average degree (i.e. edge density)
constraints that force an $r$-graph to have large $F$-matching number,
especially when $F$ is a degenerate $r$-graph. Since our results are closely
related to the Turán problem of $F$, we abuse the use of notation by letting
$\mathrm{ex}\left(n,(t+1)F\right)$ denote the maximum number of edges in an
$n$-vertex $r$-graph $\mathcal{H}$ with $\nu(F,\mathcal{H})<t+1$. Let us
introduce some definitions and known results before stating our results.

Given two $r$-graphs $\mathcal{G}$ and $\mathcal{H}$, we use
$\mathcal{G}\sqcup\mathcal{H}$ to denote the vertex-disjoint union of
$\mathcal{G}$ and $\mathcal{H}$. The join
$\mathcal{G}\mathbin{\;{\rotatebox{90.0}{{$\small\Bowtie$}}}}\mathcal{H}$ of
$\mathcal{G}$ and $\mathcal{H}$ is the $r$-graph obtained from
$\mathcal{G}\sqcup\mathcal{H}$ by adding all $r$-sets that have nonempty
intersection with both $V(\mathcal{G})$ and $V(\mathcal{H})$. For simplicity,
we define the join of an $r$-graph $\mathcal{H}$ and a family $\mathcal{F}$ of
$r$-graphs as
$\mathcal{H}\mathbin{\;{\rotatebox{90.0}{{$\small\Bowtie$}}}}\mathcal{F}:=\left\\{\mathcal{H}\mathbin{\;{\rotatebox{90.0}{{$\small\Bowtie$}}}}\mathcal{G}\colon\mathcal{G}\in\mathcal{F}\right\\}$.
Similar, let
$\mathcal{H}\sqcup\mathcal{F}:=\left\\{\mathcal{H}\sqcup\mathcal{G}\colon\mathcal{G}\in\mathcal{F}\right\\}$

In [7], Erdős considered $\mathrm{ex}(n,(t+1)K_{3})$ and proved the following
result.

######  Theorem 1.3 (Erdős [7]).

Suppose that $n,t\in\mathbb{N}$ are integers satisfying $t\leq\sqrt{n/400}$.
Then

$\displaystyle\mathrm{EX}\left(n,(t+1)K_{3}\right)=\\{K_{t}\mathbin{\;{\rotatebox{90.0}{{$\small\Bowtie$}}}}T(n-t,2)\\}.$

Later, Moon [51] extended it to all complete graphs.

######  Theorem 1.4 (Moon [51]).

Suppose that $n,t,\ell\in\mathbb{N}$ are integers satisfying $\ell\geq 2$,
$t\leq\frac{2n-3\ell^{2}+2\ell}{\ell^{3}+2\ell^{2}+\ell+1}$, and
$\ell\mid(n-t)$. Then

$\displaystyle\mathrm{EX}\left(n,(t+1)K_{\ell+1}\right)=\left\\{K_{t}\mathbin{\;{\rotatebox{90.0}{{$\small\Bowtie$}}}}T(n-t,\ell)\right\\}.$
(1)

It is worth mentioning that Simonovits [59] also considered this problem and
proved that if $t\geq 1$ and $\ell\geq 2$ are fixed integers, then (1) holds
for all sufficiently large $n$.

Extending Theorem 1.4 to larger $t$ becomes much more challenging. Indeed, a
full density version of the Corrádi–Hajnal Theorem was obtained only very
recently by Allen, Böttcher, Hladký, and Piguet [2] when $n$ is large. Their
results show that, interestingly, there are four different extremal
constructions for four different regimes of $t$, and the construction
$K_{t}\mathbin{\;{\rotatebox{90.0}{{$\small\Bowtie$}}}}T(n-t,2)$ is extremal
only for $t\leq\frac{2n-6}{9}$. For the other three extremal constructions, we
refer the reader to their paper for details. A full-density version of the
Corrádi–Hajnal Theorem for larger complete graphs still seems out of reach,
and it appears that there are even no conjectures for the extremal
constructions in general (see remarks in the last section of [2]).

In [31], the authors initiated a systematic study of
$\mathrm{ex}\left(n,(t+1)F\right)$ for nondegenerate hypergraphs $F$. It was
showed in [31] that if a nondegenerate hypergraphs $F$ satisfies the
‘Smoothness’ and ‘Boundedness’ constraints (refer to [31] for definitions),
then for sufficiently large $n$ and all $t\leq\epsilon n$, where $\epsilon>0$
is a constant depending only on $F$, we have
$\mathrm{EX}\left(n,(t+1)F\right)=\left\\{K_{t}\mathbin{\;{\rotatebox{90.0}{{$\small\Bowtie$}}}}\mathrm{EX}\left(n,F\right)\right\\}$.

To complement the work of [31], we initiate a systematic study of
$\mathrm{ex}\left(n,(t+1)F\right)$ for degenerate hypergraphs $F$ in the
present paper. Let us introduce some definitions and simple facts first.

$K_{t}$$K_{2,3}$-free$K_{2t+1}$$K_{5t+4}$$K_{2,3}$-free$0$$t$$\sim\sqrt{\frac{n}{2}}$$\sim\frac{4n}{29}$$\frac{n}{5}$
Figure 1: Three conjectured asymptotic extremal constructions for
$\mathrm{ex}(n,(t+1)K_{2,3})$ for $t$ in different intervals. We highlighted
the three small intervals in which the constructions are asymptotically
optimal.

Given an $r$-graph $F$ and an integer $s\in[0,v(F)]$, let

$\displaystyle F[s]:=\left\\{F[S]\colon S\subset V(F)\text{ and
}|S|=s\right\\},$

where $F[S]$ denotes the induced subgraph of $F$ on $S$. The covering number
$\tau(F)$ of $F$ is defined as

$\displaystyle\tau(F):=\min\left\\{|S|\colon\text{$S\subset V(F)$ and $S\cap
e\neq\emptyset$ for all $e\in F$}\right\\}.$

For an $m$-vertex $r$-graph $F$ with covering number $\tau$, let

  1. (i)

$\mathcal{G}_{1}(n,t,F):=K_{t}^{r}\mathbin{\;{\rotatebox{90.0}{{$\small\Bowtie$}}}}\mathrm{EX}(n-t,F)$,

  2. (ii)

$\mathcal{G}_{2}(n,t,F):=K_{\tau(t+1)-1}^{r}\mathbin{\;{\rotatebox{90.0}{{$\small\Bowtie$}}}}\mathrm{EX}\left(n-\tau(t+1)+1,F[m-\tau+1]\right)$,

  3. (iii)

$\mathcal{G}_{3}(n,t,F):=K_{m(t+1)-1}^{r}\sqcup\mathrm{EX}\left(n-m(t+1)+1,F\right)$.

Let $g_{i}(n,t,F)$ denote the size of a member in $\mathcal{G}_{i}(n,t,F)$ for
$i\in\\{1,2,3\\}$. Simple calculations show that

$\displaystyle g_{1}(n,t,F)$
$\displaystyle=\binom{n}{r}-\binom{n-t}{r}+\mathrm{ex}(n-t,F),$ $\displaystyle
g_{2}(n,t,F)$
$\displaystyle=\binom{n}{r}-\binom{n-\tau(t+1)+1}{r}+\mathrm{ex}\left(n-\tau(t+1)+1,F[m-\tau+1]\right),\quad\text{and}$
$\displaystyle g_{3}(n,t,F)$
$\displaystyle=\binom{m(t+1)-1}{r}+\mathrm{ex}\left(n-m(t+1)+1,F\right).$

An easy observation is that the every member in the families defined above has
$n$ vertices and is $(t+1)F$-free. Therefore, we have the following lower
bound for $\mathrm{ex}\left(n,(t+1)F\right)$.

######  Proposition 1.5.

Suppose that $F$ is an $m$-vertex $r$-graph with covering number $\tau$. Then

$\displaystyle\mathrm{ex}\left(n,(t+1)F\right)\geq\max\left\\{g_{i}(n,t,F)\colon
i\in\\{1,2,3\\}\right\\}$

for all $t\geq 1$ and $n\geq mt$.

Our main results, which will be presented shortly, show that for an
$r$-partite $r$-graph $F$ with part sizes $s_{r}\geq\cdots\geq s_{1}=\tau(F)$,
the constructions $\mathcal{G}_{1}(n,t,F)$, $\mathcal{G}_{2}(n,t,F)$, and
$\mathcal{G}_{3}(n,t,F)$ are asymptotically optimal for
$\mathrm{ex}\left(n,(t+1)F\right)$ when $n$ is large, and $t$ lies in
intervals $\left[0,\frac{\varepsilon\cdot\mathrm{ex}(n,F)}{n^{r-1}}\right]$,
$\left[\frac{\mathrm{ex}(n,F)}{\varepsilon n^{r-1}},\varepsilon n\right]$, and
$\left[(1-\varepsilon)\frac{n}{v(F)},\frac{n}{v(F)}\right]$, respectively (see
Figure 1). Here $\varepsilon>0$ is a constant depending only on $F$. We
conjecture that when $F$ is the balanced complete $r$-partite $r$-graph
$K_{s,\ldots,s}^{r}$, the asymptotic behavior of
$\mathrm{ex}\left(n,(t+1)F\right)$ is governed by the three constructions
defined above for all feasible $t$. For general degenerate $r$-graphs, there
are could be more extremal constructions (see Section 6 for more details). We
hope that our results together with results in [31] may provide some insights
towards a comprehensive generalization of the density version of the
Corrádi–Hajnal Theorem for all hypergraphs.

###  1.2 The first interval

In this subsection, we present the result for
$\mathrm{ex}\left(n,(t+1)F\right)$ when $t$ lies in
$\left[0,\frac{\varepsilon\cdot\mathrm{ex}(n,F)}{n^{r-1}}\right]$. This result
shares similarities with the main result in [31], but here we only need the
following weaker property of $F$.

######  Definition 1.6 (Boundedness).

Let $c_{1},c_{2}>0$ be two constants. An $r$-graph $F$ is
$(c_{1},c_{2})$-bounded111One could extend the definition of ‘Boundedness’ by
allowing $c_{1}$ and $c_{2}$ to be functions of $n$, but constant functions
are sufficient for our purpose in the present paper. if the following holds
for all sufficiently large $n$. Every $n$-vertex $r$-graph $\mathcal{H}$ with

$\displaystyle\Delta(\mathcal{H})\geq
c_{1}\binom{n-1}{r-1}\quad\text{and}\quad|\mathcal{H}|\geq(1-c_{2})\cdot\mathrm{ex}(n,F)$

contains a copy of $F$. We say $F$ is bounded if it is $(c_{1},c_{2})$-bounded
for some $c_{1},c_{2}>0$.

We will show in [30] that many well-studied degenerate hypergraphs such as
even cycles $C_{2k}$ for $k\geq 2$, complete bipartite graphs $K_{s,t}$ for
$t>s(s-1)\geq 2$, and the expansion of complete bipartite graphs $K_{s,t}^{+}$
for $t>(s-1)!\geq 2$ are bounded.

######  Theorem 1.7.

Let $m\geq r\geq 2$ be integers and $F$ be an $r$-graph with $m$ vertices.
Suppose that $F$ is $(c_{1},c_{2})$-bounded for some $c_{1}<1/m$ and
$c_{2}>0$. Then for sufficiently large $n$,

$\displaystyle\mathrm{EX}\left(n,(t+1)F\right)=K_{t}^{r}\mathbin{\;{\rotatebox{90.0}{{$\small\Bowtie$}}}}\mathrm{EX}(n-t,F)$

holds for all integers $t$ satisfying

$\displaystyle 0\leq
t\leq\min\left\\{\frac{\delta\cdot\mathrm{ex}(n,F)}{m\binom{n-1}{r-1}},\
\frac{\delta(n-1)}{8m(r-1)}\right\\},\quad\text{where}\quad\delta:=\min\left\\{\frac{1}{4}\left(\frac{1}{m}-c_{1}\right),\
\frac{c_{2}}{4}\right\\}.$

######  Definition 1.8 (Suspensions).

Let $F$ be an $(r-1)$-graph. The suspension $\widehat{F}$ of $F$ is the
$r$-graph defined as $\widehat{F}:=\left\\{v\cup e\colon e\in F\right\\}$,
where $v$ is a new vertex not contained in $V(F)$.

Observe that the suspension $\widehat{F}$ of every hypergraph $F$ is
$(c_{1},1)$-bounded for all $c_{1}>\pi(F)$. Thus we have the following
corollary.

######  Corollary 1.9.

Let $m\geq r\geq 2$ be integers and $F$ be an $(r-1)$-graph on $m-1$ vertices.
Suppose that $\pi(F)<1/m$. Then for sufficiently large $n$, we have

$\displaystyle\mathrm{EX}(n,(t+1)\widehat{F})=K_{t}^{r}\mathbin{\;{\rotatebox{90.0}{{$\small\Bowtie$}}}}\mathrm{EX}(n-t,\widehat{F})$

holds for all integers $t$ satisfying

$\displaystyle 0\leq
t\leq\min\left\\{\frac{1-m\cdot\pi(F)}{5m^{2}}\frac{\mathrm{ex}(n,F)}{\binom{n-1}{r-1}},\
\frac{1-m\cdot\pi(F)}{40m^{2}}\frac{n-1}{r-1}\right\\}.$

Remarks.

  * •

Note that we do not require $F$ to be a degenerate hypergraph in Theorem 1.7.
Thus Theorem 1.7 improves [31, Theorem 1.7] for nondegenerate $r$-graphs $F$
with $\pi(F)<1/v(F)$ since we do not need the ‘Smoothness’ constraint in
Theorem 1.7. Also note that Corollary 1.9 improves [31, Theorem 1.7] for the
suspension of nondegenerate $r$-graphs $F$ with $\pi(F)<\frac{1}{v(F)+1}$, and
an illustrative example is provided in the subsequent Corollary 1.10.

  * •

For integers $r>b\geq 0$ let $Y_{r,b}$ denote the $r$-graph consistsing of two
edges that intersect in exactly $b$ vertices. Gan, Han, Sun and Wang [25] (see
also [28]) proved some asymptotic upper bounds for
$\mathrm{ex}\left(n,(t+1)Y_{r,b}\right)$ for $r>b\geq 1$. Since $Y_{r,b}$ is
the suspension of $Y_{r-1,b-1}$ for $b\geq 1$, Corollary 1.9 improves their
results for $t$ in the interval as stated in Corollary 1.9.

Let $r\geq 2$ be an integer. A notable example in hypergraph Turán problem is
the generalized triangle $T_{r}$, defined as

$\displaystyle
T_{r}:=\left\\{\\{1,\ldots,r-1,r\\},\\{1,\ldots,r-1,r+1\\},\\{r,r+1,\ldots,2r-1\\}\right\\}.$

The study of $\pi(T_{r})$ has a long history (see e.g. [50, 4, 18, 58, 57, 36,
56, 55, 43, 45]), although the precise value of $\pi(T_{r})$ remains
undetermined for all $r\geq 7$. Determining the $\pi(\widehat{T}_{r})$ appears
to be even more challenging in general, and the longstanding problem of
determining $\pi(\widehat{T}_{3})$, i.e. $\pi(K_{4}^{3-})$, remains open (see
[19, 52]).

In [20], Frankl–Füredi showed that $\pi(T_{r})\leq\frac{1}{e\binom{r-1}{2}}$,
which is smaller that $\frac{1}{2r}$ when $r\geq 4$. Therefore, by Corollary
1.9222Together with facts
$\mathrm{ex}(n,\widehat{T}_{r}))\geq\pi(\widehat{T}_{r})\binom{n}{r}$,
$\pi(\widehat{T}_{r})\leq\pi(T_{r})\leq\frac{1}{e\binom{r-1}{2}}$, and some
simple calculations., we obtain the following result, which appears to be the
first of its kind for a hypergraph with an undetermined Turán density.

######  Corollary 1.10.

Suppose that $r\geq 4$ is an integer. Then for sufficiently large $n$,

$\displaystyle\mathrm{EX}(n,(t+1)\widehat{T}_{r})=K_{t}^{r}\mathbin{\;{\rotatebox{90.0}{{$\small\Bowtie$}}}}\mathrm{EX}(n-t,\widehat{T}_{t}),$

holds for all integers $t$ satisfying

$\displaystyle 0\leq
t\leq\frac{\left(1-(2r-1)\cdot\pi(\widehat{T}_{r})\right)\cdot\pi(\widehat{T}_{r})}{5r(2r-1)^{2}}n.$

The proof of Theorem 1.7 is presented in Section 3.

###  1.3 The second interval

In this subsection, we present the result for
$\mathrm{ex}\left(n,(t+1)F\right)$ when $t$ lies in
$\left[\frac{\mathrm{ex}(n,F)}{\varepsilon n^{r-1}},\varepsilon n\right]$.

######  Theorem 1.11.

Let $r\geq 2$ and $s_{r}\geq\cdots\geq s_{1}\geq 2$ be integers. Let
$s:=s_{1}+\cdots+s_{r}$ and $\mathbb{B}:=B_{s_{1},\ldots,s_{r}}^{r}$ be an
$r$-partite $r$-graph with part sizes $s_{1},\ldots,s_{r}$. For sufficiently
large $n$,

$\displaystyle\mathrm{ex}(n,(t+1)\mathbb{B})\leq\binom{n}{r}-\binom{n-s_{1}(t+1)+1}{r}+\mathrm{ex}(n-s_{1}(t+1)+1,\mathbb{B}).$

holds for all integers $t$ satisfying

$\displaystyle
320es_{1}s\left(\frac{\mathrm{ex}(n,\mathbb{B})}{\binom{n-1}{r-1}}+320es_{1}s^{2}r!\right)\leq
t\leq\frac{n}{512es_{1}s^{3}r!}.$

For graphs, we are able to obtain the following tight bound.

######  Theorem 1.12.

Let $s_{2}\geq s_{1}\geq 2$ be integers. Let $s:=s_{1}+s_{2}$ and
$\mathbb{B}:=B_{s_{1},s_{2}}$ be an $s_{1}$ by $s_{2}$ bipartite connected
graph with $\tau(B)=s_{1}$. For sufficiently large $n$,

$\displaystyle\mathrm{ex}\left(n,(t+1)\mathbb{B}\right)=\binom{n}{2}-\binom{n-s_{1}(t+1)+1}{2}+\mathrm{ex}\left(n-s_{1}(t+1)+1,\mathbb{B}[s_{2}+1]\right)$

holds for all integers $t$ satisfying

$\displaystyle\max\left\\{\sqrt{32s_{1}sn},\
\frac{12800es^{5}}{s_{1}}\left(\frac{\mathrm{ex}(n,\mathbb{B})}{n-1}+288es_{1}s^{2}r!\right)\right\\}\leq
t\leq\frac{n}{1024es_{1}s^{3}}.$

Since the complete bipartite graph $K_{s_{1},s_{2}}$ with $s_{2}\geq s_{1}\geq
2$ satisfies
$\mathrm{ex}(n,K_{s_{1},s_{2}})\geq\mathrm{ex}(n,K_{2,2})=(1/2-o(1))n^{3/2}$
(see [5, 12, 21, 22, 23]), we obtain the following corollary of Theorem 1.12.

######  Corollary 1.13.

Let $s_{2}\geq s_{1}\geq 2$ be integers. Let $s:=s_{1}+s_{2}$ and
$\mathbb{K}:=K_{s_{1},s_{2}}$. For sufficiently large $n$,

$\displaystyle\mathrm{ex}\left(n,(t+1)\mathbb{K}\right)=\binom{n}{2}-\binom{n-s_{1}(t+1)+1}{2}+\mathrm{ex}\left(n-s_{1}(t+1)+1,\mathbb{K}[s_{2}+1]\right)$

holds for all integers $t$ satisfying

$\displaystyle\frac{12801es^{5}\cdot\mathrm{ex}(n,\mathbb{K})}{s_{1}(n-1)}\leq
t\leq\frac{n}{1024es_{1}s^{3}}.$

The proof of Theorem 1.11 is presented in Section 5.2. The proof of Theorem
1.12 is presented in Section 5.3.

###  1.4 The third interval

We present the result for $\mathrm{ex}\left(n,(t+1)F\right)$ when $t$ lies in
$\left[(1-\varepsilon)\frac{n}{v(F)},\frac{n}{v(F)}\right]$ in this
subsection.

We say an $n$-vertex $r$-graph $\mathcal{H}$ is an $m$-star for some $m\leq n$
if there exists a set $V_{1}\subset V(\mathcal{H})$ of size $m$ such that
every edge in $\mathcal{H}$ contains at least one vertex in $V_{1}$. Extending
the definition of $\mathrm{ex}\left(n,F\right)$, we let
$\mathrm{ex}_{\mathrm{star}}\left(m,n,F\right)$ denote the maximum number of
edges in an $F$-free $r$-uniform $m$-star with $n$ vertices. Observe that
$\mathrm{ex}_{\mathrm{star}}\left(m,n,F\right)\leq\mathrm{ex}\left(n,F\right)$
for all $m\leq n$, and
$\mathrm{ex}_{\mathrm{star}}\left(n,n,F\right)=\mathrm{ex}\left(n,F\right)$.

Let $K_{s_{1},\ldots,s_{r}}^{r}$ denote the complete $r$-partite $r$-graph
with part sizes $s_{1},\ldots,s_{r}$. Using an argument analogous to Erdős’
proof in [8] (refer also to Proposition 2.11), it is easy to obtain the
following result, which provides an improved upper bound for
$\mathrm{ex}_{\mathrm{star}}\left(m,n,K_{s_{1},\ldots,s_{r}}^{r}\right)$ when
$m$ is small.

######  Proposition 1.14.

Suppose that $r\geq 2$ and $s_{r}\geq\cdots\geq s_{1}\geq 1$ are integers.
Then

$\displaystyle\mathrm{ex}_{\mathrm{star}}\left(m,n,K_{s_{1},\ldots,s_{r}}^{r}\right)\leq\frac{(s_{2}+\cdots+s_{r}-r+1)^{\frac{1}{s_{1}}}}{r}mn^{r-1-\frac{1}{s_{1}\cdots
s_{r-1}}}+\frac{s_{1}-1}{r}\binom{n}{r-1}.$

Our main result in this subsection is as follows.

######  Theorem 1.15.

Let $r\geq 2$ and $s_{r}\geq\cdots\geq s_{1}\geq 1$ be integers. Let
$s:=s_{1}+\cdots+s_{r}$ and $\mathbb{B}:=B_{s_{1},\ldots,s_{r}}^{r}$ be an
$r$-partite $r$-graph with part sizes $s_{1},\ldots,s_{r}$. For sufficiently
large $n$,

$\displaystyle\mathrm{ex}(n,(t+1)\mathbb{B})\leq\binom{s(t+1)-1}{r}+\mathrm{ex}_{\mathrm{star}}\left(n-st,n,s\mathbb{B}\right).$

holds for all integers $t$ satisfying

$\displaystyle\frac{n}{s}-\frac{n}{16e^{2}r^{4}s^{2}\prod_{i\in[r]}s_{i}}\leq
t\leq\frac{n}{s}.$

For graphs, we are able to obtain the following better bound.

######  Theorem 1.16.

Let $s_{2}\geq s_{1}\geq 2$ be integers. Let $s:=s_{1}+s_{2}$ and
$\mathbb{B}:=B_{s_{1},s_{2}}$ be an $s_{1}$ by $s_{2}$ bipartite graph. For
sufficiently large $n$,

$\displaystyle\mathrm{ex}(n,(t+1)\mathbb{B})\leq\binom{s(t+1)-1}{2}+\mathrm{ex}\left(n-s(t+1)+1,\mathbb{B}\right)+s_{1}sn$

holds for all integers $t$ satisfying

$\displaystyle\frac{n}{s}-\frac{n}{65s_{1}s^{2}}\leq t\leq\frac{n}{s}.$

The proof of Theorem 1.16 is presented in Section 4.1. The proof of Theorem
1.15 is presented in Section 4.2. In the next section, we present some
definitions and preliminary results.

##  2 Preliminaries

Let $r\geq 2$ be an integer and $\mathcal{H}$ be an $r$-graph. Given a set
$W\subset V(\mathcal{H})$, we use $\mathcal{H}[W]$ to denote the induced
subgraph of $\mathcal{H}$ on $W$, and use $\mathcal{H}-W$ to denote the
induced subgraph of $\mathcal{H}$ on $V(\mathcal{H})\setminus W$. Given two
disjoint sets $S,T\subset V(\mathcal{H})$, we use $\mathcal{H}[S,T]$ to denote
the collection of edges in $\mathcal{H}$ that have nonempty intersection with
both $S$ and $T$. We use $\overline{\mathcal{H}}$ to denote the complement of
$\mathcal{H}$.

The following simple inequalities will be useful.

######  Fact 2.1.

Suppose that $n\geq r\geq 1$ and $t\in[n]$ are integers. Then

$\displaystyle\binom{n-t}{r}\leq\left(1-\frac{t}{n}\right)^{r}\binom{n}{r}\quad\text{and}\quad\binom{n}{r}\leq\left(\frac{n}{n-t-r}\right)^{r}\binom{n-t}{r}.$

######  Fact 2.2 ([31, Lemma 3.4]).

Suppose that $n,b,r\geq 1$ are integers satisfying
$b\leq\frac{n-r^{2}+1}{r+1}$. Then

$\displaystyle\binom{n}{r}\leq\frac{n^{r}}{r!}\leq e\binom{n-b}{r}.$

######  Fact 2.3.

Suppose that $n,\ell,x\geq 0$ are integers satisfying $\ell+x\leq n$. Then

$\displaystyle\binom{n}{2}-\binom{n-\ell-x}{2}\geq\binom{n}{2}-\binom{n-\ell}{2}+x(n-\ell-x).$

######  Fact 2.4.

Suppose that $r\geq 1$ is an integer and $0\leq x\leq\frac{1}{4r}$ is a real
number. Then

$\displaystyle\left(\frac{1}{1-x}\right)^{r}\leq 1+4rx.$

###### Proof.

This is due to

$\displaystyle\left(\frac{1}{1-x}\right)^{r}\leq(1+2x)^{r}\leq
1+2rx+\sum_{i=2}^{r}(2rx)^{i}\leq
1+2rx+2rx\cdot\sum_{i=1}^{r-1}\left(\frac{1}{2}\right)^{i}\leq 1+4rx.$

######  Fact 2.5.

Suppose that $x\leq 1$ and $r\geq 1$ are real numbers. Then

$\displaystyle(1-x)^{\frac{1}{r}}\leq 1-\frac{x}{r}.$

###  2.1 Graphs

Given integers $m,n,s_{1},s_{2}\geq 1$ and an $s_{1}$ by $s_{2}$ bipartite
graph $B_{s_{1},s_{2}}=B[W_{1},W_{2}]$, the Zarankiewicz number
$Z(m,n,B_{s_{1},s_{2}})$ is the maximum number of edges in an $m$ by $n$
bipartite graph without a copy of $B_{s_{1},s_{2}}$ with the set $W_{1}$
contained in the part of size $m$ and the set $W_{2}$ contained in the part of
size $n$. For convenience, we use $Z(m,n,s_{1},s_{2})$ to denote
$Z(m,n,K_{s_{1},s_{2}})$.

We will use the following classical result of Kővári, Sós and Turán [39].

######  Theorem 2.6 (Kővári–Sós–Turán [39]).

Let $m,n,s_{1},s_{2}\geq 1$ be integers. Then

$\displaystyle\mathrm{ex}(n,K_{s_{1},s_{2}})$
$\displaystyle\leq\frac{(s_{2}-1)^{\frac{1}{s_{1}}}}{2}n^{2-\frac{1}{s_{1}}}+\frac{s_{1}-1}{2}n,\quad\text{and}$
$\displaystyle Z(m,n,s_{1},s_{2})$
$\displaystyle\leq(s_{2}-1)^{\frac{1}{s_{1}}}mn^{1-\frac{1}{s_{1}}}+(s_{1}-1)n.$

The following result of Alon and Yuster [3] will be useful in the proof of
Theorem 1.16.

######  Theorem 2.7 (Alon–Yuster [3]).

Let $F$ be a graph with $m$ vertices. For every $\varepsilon>0$ there exists
$n_{0}=n_{0}(\varepsilon,F)$ such that the following holds for all $n\geq
n_{0}$. Every $n$-vertex graph $G$ with
$\delta(G)\geq\left(1-\frac{1}{\chi(H)}+\varepsilon\right)n$ contains $\lfloor
n/m\rfloor$ pairwise vertex-disjoint copies of $F$.

We also need the following simple result on $\frac{\mathrm{ex}(n,F)}{n}$ in
the proof of Theorem 1.16.

######  Proposition 2.8.

Let $F$ be a connected graph. For all integers $n\geq m\geq 1$ we have

$\displaystyle\frac{\mathrm{ex}(n,F)}{n}\geq\left(1-\frac{m}{n}\right)\frac{\mathrm{ex}(m,F)}{m}.$

###### Proof.

Let $G_{m}$ be an $m$-vertex $F$-free graph with $\mathrm{ex}(m,F)$ edges. Let
$G_{n}$ be the union of $\lfloor n/m\rfloor$ vertex-disjoint copies of $G_{m}$
with a set of $n-m\lfloor n/m\rfloor$ isolated vertices. Since $F$ is
connected, the graph $G_{n}$ is $F$-free. Therefore, we have

$\displaystyle\frac{\mathrm{ex}(n,F)}{n}\geq\frac{|G_{n}|}{n}=\frac{\lfloor
n/m\rfloor\times\mathrm{ex}(m,F)}{n}\geq\left(\frac{n}{m}-1\right)\frac{m}{n}\frac{\mathrm{ex}(m,F)}{m}=\left(1-\frac{m}{n}\right)\frac{\mathrm{ex}(m,F)}{m},$

proving Proposition 2.8.

###  2.2 Hypergraphs

Given a $r$-graph $\mathcal{H}$ and a vertex $v\in V(\mathcal{H})$, the link
$L_{\mathcal{H}}(v)$ of $v$ in $\mathcal{H}$ is defined as

$\displaystyle
L_{\mathcal{H}}(v):=\left\\{A\in\binom{V(\mathcal{H})}{r-1}\colon
A\cup\\{v\\}\in\mathcal{H}\right\\}.$

Recall that the degree $d_{\mathcal{H}}(v)$ of $v$ is
$d_{\mathcal{H}}(v):=|L_{\mathcal{H}}(v)|$. Given a set $S\subset
V(\mathcal{H})$ let

$\displaystyle L_{\mathcal{H}}(S):=\bigcap_{v\in S}L_{\mathcal{H}}(v)$

denote the common link of $S$ in $\mathcal{H}$, and let
$d_{\mathcal{H}}(S):=|L_{\mathcal{H}}(S)|$. Let $T\subset V(\mathcal{H})$ be a
set of size $r-1$, the neighborhood of $T$ is

$\displaystyle N_{\mathcal{H}}(T):=\left\\{v\in V(\mathcal{H})\colon
T\cup\\{v\\}\in\mathcal{H}\right\\}.$

We will omit the subscript $\mathcal{H}$ from the notations defined above if
it is clear from the context.

Extending the Kővári–Sós–Turán Theorem to hypergraphs, Erdős [8] proved the
following theorem.

######  Theorem 2.9 (Erdős [8]).

Let $n\geq r\geq 3$ and $s_{r}\geq\cdots\geq s_{1}\geq 1$ be integers. There
exists a constant $C:=C(r,s_{1},\ldots,s_{r})$ such that

$\displaystyle\mathrm{ex}(n,K_{s_{1},\ldots,s_{r}}^{r})\leq
Cn^{r-\frac{1}{s_{1}\cdots s_{r-1}}}.$

Remark. A detailed analysis (see Appendix A) of the proof of Erdős in [8]
shows that

$\displaystyle\mathrm{ex}(n,K_{s_{1},\ldots,s_{r}}^{r})\leq\frac{(s_{2}+\cdots+s_{r}-r+1)^{\frac{1}{s_{1}}}}{r}n^{r-\frac{1}{s_{1}\cdots
s_{r-1}}}+\frac{s_{1}-1}{r}\binom{n}{r-1}.$

We also need the following lower bound for
$\mathrm{ex}(n,K_{s_{1},\ldots,s_{r}}^{r})$ which comes from a simple
application of the probabilistic deletion method.

######  Fact 2.10.

Let $r\geq 2$ and $s_{r}\geq s_{r-1}\geq\cdots\geq s_{1}\geq 2$ be integers.
Then

$\displaystyle\mathrm{ex}(n,K_{s_{1},\ldots,s_{r}}^{r})\geq{\rm{ex}}(n,K_{2,\ldots,2}^{r})=\Omega\left(n^{r-\frac{r}{2^{r}-1}}\right)=\Omega\left(n^{r-\frac{2}{3}}\right).$
(2)

An $r$-graph $\mathcal{H}$ is bipartite if there exists a bipartition
$V_{1}\cup V_{2}=V(\mathcal{H})$ such that every edge in $\mathcal{H}$ has
nonempty intersection with both $V_{1}$ and $V_{2}$. A bipartite $r$-graph
$\mathcal{H}=\mathcal{H}[V_{1},V_{2}]$ is semibipartite if every edge in
$\mathcal{H}$ contains exactly one vertex from $V_{1}$. Let
$\mathbb{B}:=B[W_{1},\ldots,W_{r}]$ be an $r$-partite $r$-graph with parts
$W_{1},\ldots,W_{r}$. An ordered copy of $\mathbb{B}$ in a semibipartite
$r$-graph $\mathcal{H}[V_{1},V_{2}]$ is a copy of $\mathbb{B}$ with $W_{1}$
contained in $V_{1}$ and $W_{2},\ldots,W_{r}$ contained in $V_{2}$. Extending
the graph Zarankiewicz number to hypergraphs, we use $Z(m,n,\mathbb{B})$ to
denote the maximum number of edges in an $m$ by $n$ semibipartite $r$-graph
without any ordered copy of $\mathbb{B}$. For convenience, let
$Z(m,n,s_{1},\ldots,s_{r}):=Z(m,n,K_{s_{1},\ldots,s_{r}}^{r})$.

Extending results of Kővári–Sós–Turán and Erdős, we prove the following upper
bound for $Z(m,n,s_{1},\ldots,s_{r})$. Since the proof is essentially the same
as that of Erdős in [8], we include in Appendix B.

######  Proposition 2.11.

Suppose that $r\geq 3$, $s_{r}\geq\cdots\geq s_{1}\geq 1$, and $m,n\geq 1$ are
integers. Then

$\displaystyle
Z(m,n,s_{1},\ldots,s_{r})\leq\frac{(s_{2}+\cdots+s_{r}-r+1)^{\frac{1}{s_{1}}}}{r}mn^{r-1-\frac{1}{s_{1}\cdots
s_{r-1}}}+\frac{s_{1}-1}{r}\binom{n}{r-1}.$

The following theorem of Lu and Székely [49] will be useful in the proof of
Theorem 1.15.

######  Theorem 2.12 (Lu–Székely [49]).

Let $F$ be an $r$-graph such that every edge in $F$ has nonempty intersection
with at most $d$ other edges in $F$. Suppose that an $n$-vertex $r$-graph
$\mathcal{H}$ satisfies

$\displaystyle v(F)\mid
v(\mathcal{H})\quad\text{and}\quad\delta(\mathcal{H})\geq\left(1-\frac{1}{e\left(d+1+r^{2}\frac{|F|}{v(F)}\right)}\right)\binom{n-1}{r-1}.$

Then $\mathcal{H}$ contains a perfect $F$-matching. In particular, if an
$n$-vertex $r$-graph $\mathcal{H}$ satisfies

$\displaystyle\sum_{i\in[r]}s_{i}\mid
v(\mathcal{H})\quad\text{and}\quad\delta(\mathcal{H})\geq\left(1-\frac{1}{2er^{2}\prod_{i\in[r]}s_{i}}\right)\binom{n-1}{r-1}.$

Then $\mathcal{H}$ contains a perfect $K_{s_{1},\ldots,s_{r}}^{r}$-matching.

The following simple upper bound for the number of edges in an $(t+1)F$-free
$r$-graph with bounded degree will be useful.

######  Lemma 2.13.

Let $m\geq r\geq 2$ be integers and $F$ be an $r$-graph on $m$ vertices. For
every $t\geq 0$, every $n$-vertex $(t+1)F$-free $r$-graph $\mathcal{H}$
satisfies

$\displaystyle|\mathcal{H}|\leq
mt\cdot\Delta(\mathcal{H})+\mathrm{ex}(n-mt,F).$

###### Proof.

Let $\mathcal{H}$ be an $n$-vertex $(t+1)F$-free $r$-graph. Let
$\mathcal{F}=\\{F_{1},\ldots,F_{\ell}\\}$ be a maximum collection of pairwise
vertex-disjoint copies of $F$ in $\mathcal{H}$. Let
$B:=\bigcup_{i\in[\ell]}V(F_{i})$. Since $\mathcal{H}$ is $(t+1)F$-free, we
have $\ell\leq t$ and hence, $|B|\leq m\ell$. Let $U:=V(\mathcal{H})\setminus
B$. By moving vertices from $U$ to $B$, we may assume that $|B|=mt$. Observe
that $\mathcal{H}[U]$ is $F$-free. So we have

$\displaystyle|\mathcal{H}|\leq\sum_{v\in
B}d_{\mathcal{H}}(v)+|\mathcal{H}[U]|\leq
mt\cdot\Delta(\mathcal{H})+\mathrm{ex}(n-mt,F),$

proving Lemma 2.13.

We will need the following simple fact regarding the monotonicity of
$\binom{n}{r}-\binom{n-x}{r}+\mathrm{ex}(n-x,F)$.

######  Fact 2.14.

Let $F$ be an $r$-graph and let

$\displaystyle f(x):=\binom{n}{r}-\binom{n-x}{r}+\mathrm{ex}(n-x,F)$

for all integers $x\in[n]$. Then $f(\ell)\leq f(\ell+1)$ for all integers
$\ell\in[n-1]$.

##  3 Proofs for theorems in the first interval

We prove Theorem 1.7 in this section. Let us start with some technical lemmas.

######  Lemma 3.1.

Let $n\geq m\geq r\geq 2$ be integers and $\delta\in[0,1/m]$ be a real number.
Let $F$ be an $m$-vertex $r$-graph. Suppose that $t$ is a positive integer
satisfying

$\displaystyle t\leq\min\left\\{\frac{\delta mn}{r-1}-r,\
\frac{n}{m}\right\\}.$

Then every $n$-vertex $(t+1)F$-free $r$-graph $\mathcal{H}$ with
$\Delta(\mathcal{H})\leq\left(1/m-\delta\right)\binom{n-1}{r-1}$ satisfies

$\displaystyle|\mathcal{H}|\leq\binom{n}{r}-\binom{n-t}{r}+\mathrm{ex}(n-t,F).$

###### Proof of Lemma 3.1.

Since $t\leq\frac{\delta mn}{r-1}-r\leq n-\left(1-\delta
m\right)^{\frac{1}{r-1}}n-r$, we have

$\displaystyle\left(1-\delta m\right)\left(\frac{n}{n-t-r}\right)^{r-1}\leq
1.$

Combined with Lemma 2.13 and Fact 2.1, we obtain

$\displaystyle|\mathcal{H}|$ $\displaystyle\leq
mt\left(\frac{1}{m}-\delta\right)\binom{n-1}{r-1}+\mathrm{ex}(n-mt,F)$
$\displaystyle\leq\left(1-\delta
m\right)\left(\frac{n}{n-t-r}\right)^{r-1}t\binom{n-t}{r-1}+\mathrm{ex}(n-t,F)$
$\displaystyle\leq
t\binom{n-t}{r-1}+\mathrm{ex}(n-t,F)\leq\binom{n}{r}-\binom{n-t}{r}+\mathrm{ex}(n-t,F),$

which proves Lemma 3.1.

######  Lemma 3.2.

Let $n\geq m\geq r\geq 2$ be integers and $\delta_{1},\delta_{2}\geq 0$ be
real numbers. Let $F$ be a $(c_{1},c_{2})$-bounded $r$-graph. Suppose that
$\mathcal{H}$ is an $n$-vertex $r$-graph satisfying

  1. (i)

$|\mathcal{H}|\geq\left(1-c_{2}+\delta_{1}\right)\mathrm{ex}(n,F)$, and

  2. (ii)

there exists a vertex $v\in V(\mathcal{H})$ with
$d_{\mathcal{H}}(v)\geq(c_{1}+\delta_{2})\binom{n-1}{r-1}$.

Then for every set $B\subset V(\mathcal{H})\setminus\\{v\\}$ of size at most
$\min\left\\{\frac{\delta_{1}\cdot\mathrm{ex}(n,F)}{\binom{n-1}{r-1}},\
\frac{\delta_{2}(n-1)}{r-1}\right\\}$, there exists a copy of $F$ in
$\mathcal{H}$ that have empty intersection with $B$.

###### Proof.

Fix $B\subset V(\mathcal{H})\setminus\\{v\\}$ of size at most
$\min\left\\{\frac{\delta_{1}\cdot\mathrm{ex}(n,F)}{\binom{n-1}{r-1}},\
\frac{\delta_{2}(n-1)}{r-1}\right\\}$. Let $U:=V(\mathcal{H})\setminus B$,
$n_{1}:=|U|$, and $\mathcal{H}_{1}:=\mathcal{H}[U]$. It follows from the
assumptions that

$\displaystyle|\mathcal{H}_{1}|\geq\left(1-c_{2}+\delta_{1}\right)\mathrm{ex}(n,F)-|B|\binom{n-1}{r-1}\geq(1-c_{2})\cdot\mathrm{ex}(n,F),$

and

$\displaystyle d_{\mathcal{H}_{1}}(v)\geq
d_{\mathcal{H}}(v)-|B|\binom{n-2}{r-2}\geq(c_{1}+\delta_{2})\binom{n-1}{r-1}-|B|\frac{r-1}{n-1}\binom{n-1}{r-1}\geq
c_{1}\binom{n-1}{r-1}.$

So, it follows from the $(c_{1},c_{2})$-boundedness of $F$ that
$F\subset\mathcal{H}_{1}$.

Now we are ready to prove Theorem 1.7.

###### Proof of Theorem 1.7.

Fix integers $m\geq r\geq 2$ and fix an $m$-vertex $(c_{1},c_{2})$-bounded
$r$-graph $F$ with $c_{1}<1/m$ and $c_{2}>0$. Let

$\displaystyle\delta:=\min\left\\{\frac{1}{4}\left(\frac{1}{m}-c_{1}\right),\
\frac{c_{2}}{4}\right\\},\quad\text{and}\quad 0\leq
t\leq\min\left\\{\frac{\delta\cdot\mathrm{ex}(n,F)}{m\binom{n-1}{r-1}},\
\frac{\delta(n-1)}{8m(r-1)}\right\\}.$

Let $n$ be a sufficiently large integer and $\mathcal{H}$ be an $n$-vertex
$(t+1)F$-free $r$-graph with maximum number of edges. It follows from
Proposition 1.5 that

$\displaystyle|\mathcal{H}|\geq
g_{1}(n,t,F)=\binom{n}{r}-\binom{n-t}{r}+\mathrm{ex}(n-t,F).$ (3)

Let

$\displaystyle V:=V(\mathcal{H}),\quad L:=\left\\{v\in V\colon
d_{\mathcal{H}}(v)\geq\left(c_{1}+2\delta\right)\binom{n-1}{r-1}\right\\},\quad
U:=V\setminus L,\quad\text{and}\quad\ell:=L$

For convenience, let us assume that $L=\\{v_{1},\ldots,v_{\ell}\\}$.

######  Claim 3.3.

We have $\ell\leq t$.

###### Proof.

Suppose to the contrary that $\ell\geq t+1$. We may assume that $\ell=t+1$,
since otherwise we can replace $L$ by a $(t+1)$-subset. For $i\in[t+1]$ let
$\mathcal{H}_{i}:=\mathcal{H}[U\cup\\{v_{i}\\}]$. Let $n_{1}:=n-t$. Notice
from (3) that for each $i\in[t+1]$, the $r$-graph $\mathcal{H}_{i}$ satisfies

$\displaystyle|\mathcal{H}_{i}|\geq|\mathcal{H}|-\left(\binom{n}{r}-\binom{n-t}{r}\right)\geq\mathrm{ex}(n,F)\geq(1-c_{2}+\delta)\mathrm{ex}(n,F).$
(4)

For every $i\in[t+1]$ we will find a copy of $F$ in $\mathcal{H}_{i}$, denoted
by $F_{i}$, such that $F_{1},\ldots,F_{t+1}$ are pairwise vertex-disjoint.
Define $B_{0}:=\emptyset$. Suppose that we have defined $B_{i}\subset
V(\mathcal{H})$ with $|B_{i}|\leq im$ for some $i\in[0,t]$. Consider the
$r$-graph $\mathcal{H}_{i+1}$. It follows from the definition of $L$ that

$\displaystyle d_{\mathcal{H}_{i+1}}(v_{i+1})\geq
d_{\mathcal{H}}(v_{i+1})-t\binom{n-2}{r-2}$
$\displaystyle\geq(c_{1}+2\delta)\binom{n-1}{r-1}-t\frac{r-1}{n-1}\binom{n-1}{r-1}$
$\displaystyle\geq(c_{1}+\delta)\binom{n-1}{r-1}.$ (5)

Since

$\displaystyle|B_{i}|\leq im\leq
tm\leq\min\left\\{\frac{\delta\cdot\mathrm{ex}(n,F)}{\binom{n-1}{r-1}},\
\frac{\delta(n-1)}{r-1}\right\\},$

it follows from (4), (3), and Lemma 3.2 that there exists a copy of $F$ in
$\mathcal{H}_{i+1}$ that have empty intersection with $B_{i}$. Denote this
copy of $F$ by $F_{i+1}$ and let $B_{i+1}:=B_{i}\cup V(F_{i+1})$. Then
$|B_{i+1}|=|B_{i}|+m\leq(i+1)m$. Inductively, we can find
$F_{1},\ldots,F_{t+1}$ as desired, contradicting the $(t+1)F$-freeness of
$\mathcal{H}$.

Let $t_{1}:=t-\ell$. It follows from Claim 3.3 that $t_{1}\geq 0$.

######  Claim 3.4.

The induced subgraph $\mathcal{H}[U]$ is $(t_{1}+1)F$-free.

###### Proof.

Suppose to the contrary that there exists $t_{1}+1$ pairwise vertex-disjoint
copies of $F$, denoted by $F_{1}^{\prime},\ldots,F_{t_{1}+1}^{\prime}$, in
$\mathcal{H}[U]$. Let $B_{0}:=\bigcup_{i\in[t_{1}+1]}V(F_{i}^{\prime})$ and
notice that $|B_{0}|=(t_{1}+1)m$. For $i\in[\ell]$ let
$\mathcal{H}_{i}:=\mathcal{H}[U\cup\\{v_{i}\\}]$. Repeating the argument as in
the proof of Claim 3.3, we find a copy of $F$, denoted by $F_{i}$, in
$\mathcal{H}_{i}$ for every $i\in[\ell]$, such that $F_{1},\ldots,F_{\ell}$
are pairwise vertex-disjoint. Moreover, we can also guarantee that each
$F_{i}$ have empty intersection with $B_{0}$. However, this contradicts the
$(t+1)F$-freeness of $\mathcal{H}$, since
$F_{1},\ldots,F_{\ell},F_{1}^{\prime},\ldots,F_{t_{1}}^{\prime}$ are $t+1$
pairwise vertex-disjoint copies of $F$ in $\mathcal{H}$.

It follows from $\ell\leq t\leq\frac{\delta(n-1)}{8m(r-1)}$ (Claim 3.3), the
definition of $L$, Facts 2.1, and 2.4 that

$\displaystyle\Delta(\mathcal{H}[U])\leq(c_{1}+2\delta)\binom{n-1}{r-1}$
$\displaystyle\leq(c_{1}+2\delta)\left(\frac{n}{n-\ell-r}\right)^{r-1}\binom{n-\ell-1}{r-1}$
$\displaystyle\leq(c_{1}+2\delta)\left(1+\frac{4(r-1)(\ell+r)}{n}\right)\binom{n-\ell-1}{r-1}$
$\displaystyle\leq(c_{1}+2\delta)\left(1+\frac{\delta}{m}\right)\binom{n-\ell-1}{r-1}$
$\displaystyle\leq(c_{1}+3\delta)\binom{n-\ell-1}{r-1}\leq\left(\frac{1}{m}-\delta\right)\binom{n-\ell-1}{r-1},$

where the last inequality follows from the assumption that
$\delta\leq\frac{1}{4}\left(\frac{1}{m}-c_{1}\right)$. In addition, since $n$
is large, we have $\frac{\delta
m(n-\ell)}{r-1}-r\geq\frac{\delta(n-1)}{8m(r-1)}\geq t$. So it follows from
Claim 3.3 and Lemma 3.1 that

$\displaystyle|\mathcal{H}[U]|$
$\displaystyle\leq\binom{n-\ell}{r}-\binom{n-\ell-(t-\ell)}{r}+\mathrm{ex}(n-\ell-(t-\ell),F)$
$\displaystyle=\binom{n-\ell}{r}-\binom{n-t}{r}+\mathrm{ex}(n-t,F).$

Consequently, we have

$\displaystyle|\mathcal{H}|\leq\binom{n}{r}-\binom{n-\ell}{r}+|\mathcal{H}[U]|\leq\binom{n}{r}-\binom{n-t}{r}+\mathrm{ex}(n-t,F),$

proving Theorem 1.7.

##  4 Proofs for theorems in the third interval

In this section, we prove Theorems 1.15 and 1.16. Both proofs share a similar
strategy, and we begin with the proof of Theorem 1.16 since it is more
straightforward to comprehend compared to the hypergraph case.

###  4.1 Graphs: proof of Theorem 1.16

Let us provide a concise overview of the proof strategy for Theorem 1.16. We
will start with an extremal $(t+1)\mathbb{B}$-free graph $G$, take a maximum
collection of pairwise vertex-disjoint copies of $\mathbb{B}$ in $G$, and
denote the union of their vertex sets by $V_{1}$. We will show that the set
$L\subset V_{1}$ of large degree vertices contains most vertices in $V_{1}$.
Then, a key step is to use the Alon–Yuster Theorem (Theorem 2.7) to show that
the number of edges crossing $L$ and $V(G)\setminus V_{1}$ is small. Using
this key property and applying some relatively trivial estimates, we will
obtain the desired bound on the size of $|G|$.

###### Proof of Theorem 1.16.

Fix integers $s_{2}\geq s_{1}\geq 2$ and an $s_{1}$ by $s_{2}$ bipartite graph
$B_{s_{1},s_{2}}=:\mathbb{B}$. Let

$\displaystyle
s:=s_{1}+s_{2}\quad\text{and}\quad\varepsilon:=\frac{1}{65s_{1}s^{2}}.$

Let $n$ be a sufficiently large integer, $t\in\left[\frac{n}{s}-\varepsilon
n,\frac{n}{s}\right]$ be an integer, and $G$ be an $n$-vertex
$(t+1)\mathbb{B}$-free graph with maximum number of edges. Let
$\hat{t}:=s(t+1)-1$ for simplicity. Notice from Proposition 1.5 and Fact 2.14
that

$\displaystyle|G|\geq
g_{3}(n,t,\mathbb{B})=\binom{\hat{t}}{2}+\mathrm{ex}\left(n-\hat{t},\mathbb{B}\right)\geq\binom{st}{2}+\mathrm{ex}(n-st,\mathbb{B}).$
(6)

Let $\mathcal{B}=\\{\mathbb{B}_{1},\ldots,\mathbb{B}_{t}\\}$ be a collection
of pairwise vertex-disjoint copies of $\mathbb{B}$ in $G$ (the existence of
$\mathcal{B}$ is guaranteed by the maximality of $G$). Let

$\displaystyle V:=V(G),\quad V_{1}:=\bigcup_{i\in[t]}V(B_{i}),\quad
V_{2}:=V\setminus V_{1},\quad\text{and}\quad G_{i}:=G[V_{i}]\quad\text{for
$i\in\\{1,2\\}$}.$

Note that $|V_{1}|=st$ and $G_{2}$ is $\mathbb{B}$-free, so we have (by
Theorem 2.6)

$\displaystyle|G_{2}|\leq\mathrm{ex}(n-st,\mathbb{B})\leq
C(n-st)^{2-\frac{1}{s_{1}}}.$ (7)

Trivially, we have

$\displaystyle|G[V_{1},V_{2}]|\leq|V_{1}||V_{2}|=st(n-st).$ (8)

Let

$\displaystyle\alpha:=1-\frac{1}{2s_{1}},\quad L:=\left\\{v\in V_{1}\colon
d_{G_{1}}(v)\geq\alpha(st-1)\right\\},\quad S:=V_{1}\setminus
L,\quad\text{and}\quad\ell:=|L|.$

It follows from the definition of $L$ that

$\displaystyle|G_{1}|$ $\displaystyle=\frac{1}{2}\left(\sum_{v\in
L}d_{G_{1}}(v)+\sum_{v\in S}d_{G_{1}}(v)\right)$
$\displaystyle\leq\frac{1}{2}\left(\ell(st-1)+(st-\ell)\alpha(st-1)\right)=\binom{st}{2}-\frac{st-\ell}{2}(1-\alpha)(st-1).$
(9)

######  Claim 4.1.

We have $|S|\leq\frac{4(n-st)}{(1-\alpha)}$.

###### Proof.

It follows from (7), (8), and (4.1) that

$\displaystyle|G|$ $\displaystyle=|G_{1}|+|G[V_{1},V_{2}]|+|G_{2}|$
$\displaystyle\leq\binom{st}{2}-\frac{st-\ell}{2}(1-\alpha)(st-1)+st(n-st)+\mathrm{ex}(n-st,\mathbb{B}).$

Combined with (6), we obtain

$\displaystyle-\frac{st-\ell}{2}(1-\alpha)(st-1)+st(n-st)\geq 0,$

which implies that

$\displaystyle|S|=st-\ell\leq\frac{2st(n-st)}{(st-1)(1-\alpha)}\leq\frac{4(n-st)}{1-\alpha}.$

Let $\mathcal{B}_{S}$ be the collection of members in $\mathcal{B}$ that have
nonempty intersection with $S$. Let

$\displaystyle
S_{1}:=\bigcup_{B_{i}\in\mathcal{B}_{S}}V(B_{i})\quad\text{and}\quad
L_{1}:=V_{1}\setminus S_{1}.$

Note that $S\subset S_{1}$ and $L_{1}\subset L$. Also, notice from Claim 4.1
that

$\displaystyle|S_{1}|\leq s|S|\leq\frac{4s(n-st)}{1-\alpha}.$ (10)

$L_{1}$$S_{1}$$V_{1}$$V_{2}$$Y$ Figure 2: Supplementary diagram for Claim 4.2
when $F=K_{2,3}$.

Let

$\displaystyle Y:=\left\\{v\in V_{2}\colon|N_{G}(v)\cap L_{1}|\geq
s_{1}s\right\\}.$

######  Claim 4.2.

We have $|Y|\leq s-1$.

###### Proof.

Suppose to the contrary that $|Y|\geq s$. Fix $s$ vertices
$u_{1},\ldots,u_{s}\in Y$. We will show that there exists a collection
$\mathcal{B}^{\prime}=\\{B_{1}^{\prime},\ldots,B_{s}^{\prime}\\}$ of pairwise
vertex-disjoint copies of $\mathbb{B}$ in $G[L_{1}\cup V_{2}]$ such that
$u_{i}\in B_{i}^{\prime}$ for $i\in[s]$. Indeed, it follows from the
definition of $Y$ that there exists an $s_{1}$-set $N_{i}\subset
N_{G}(u_{i})\cap L_{1}\subset L$ for every $i\in[s]$ such that sets
$N_{1},\ldots,N_{s}$ are pairwise disjoint. It follows from the definition of
$L$ that

$\displaystyle|\bigcap_{v\in N_{i}}N_{G}(v)\cap L_{1}|$ $\displaystyle\geq st-
s_{1}\left(st-\alpha(st-1)\right)-|S_{1}|$
$\displaystyle\geq\left(1-s_{1}(1-\alpha)\right)st-
s_{1}s-\frac{4s(n-st)}{1-\alpha}\geq s_{2}s.$

Then, a simple greedy argument shows that such a collection
$\mathcal{B}^{\prime}$ exists.

Let $L^{\prime}:=L_{1}\setminus\bigcup_{i\in[s]}V(B_{i}^{\prime})$. Observe
that $|L_{1}|=|L|-|S_{1}|-s(s-1)$ is divisible by $s$. In addition, it follows
from the definition of $L$ that

$\displaystyle\delta(G[L_{1}^{\prime}])$
$\displaystyle\geq\alpha(st-1)-\left(|S_{1}|+s(s-1)\right)$
$\displaystyle\geq\alpha(st-1)-\left(\frac{4s(n-st)}{1-\alpha}+s(s-1)\right)$
$\displaystyle\geq\left(1-\frac{1}{2s_{1}}\right)(st-1)-\frac{2s_{1}\cdot
4s\cdot\varepsilon s}{1-\varepsilon s}st-s(s-1)$
$\displaystyle>\left(1-\frac{1}{2s_{1}}\right)(st-1)-\frac{1}{8}st-s(s-1)>\left(\frac{1}{2}+\frac{1}{16}\right)(st-1).$

Here, we used the assumption that $t\geq\frac{n}{s}-\varepsilon n$, $s_{1}\geq
2$, and $\varepsilon=\frac{1}{65s_{1}s^{2}}$. So it follows from Theorem 2.7
that $G[L_{1}^{\prime}]$ contains a perfect $B_{s_{1},s_{2}}$-matching, i.e.
$\frac{|L_{1}|}{s}\mathbb{B}\subset G[L_{1}^{\prime}]$. These copies of
$\mathbb{B}$ together with $\mathcal{B}_{S}\cup\mathcal{B}^{\prime}$ shows
that $(t+1)\mathbb{B}\subset G$ (see Figure 2), which is a contradiction.

Claim 4.2 implies that the induced bipartite graph $G[L_{1},V_{2}]$ of $G$ on
$L_{1}$ and $V_{2}$ satisfies

$\displaystyle|G[L_{1},V_{2}]|\leq(s-1)|L_{1}|+\left(|V_{2}|-s+1\right)(s_{1}s-1)<(s-1)st+s_{1}s(n-st).$
(11)

It follows from (7), (4.1), (10), and (11) that

$\displaystyle|G|$
$\displaystyle=|G_{1}|+|G_{2}|+|G[L_{1},V_{2}]|+|G[S_{1},V_{2}]|$
$\displaystyle\leq\binom{st}{2}-\frac{st-\ell}{2}(1-\alpha)(st-1)+\mathrm{ex}(n-st,\mathbb{B})$
$\displaystyle\quad+(s-1)st+s_{1}s(n-st)+s(st-\ell)(n-st)$
$\displaystyle\leq\binom{st}{2}+\mathrm{ex}(n-st,\mathbb{B})+s_{1}sn-\left(\frac{1-\alpha}{2}(st-1)-s(n-st)\right).$

Since $t\geq\frac{n}{s}-\varepsilon n$ and
$\varepsilon=\frac{1}{65s_{1}s^{2}}$, we have

$\displaystyle\frac{1-\alpha}{2}(st-1)-s(n-st)\geq\frac{1}{4s_{1}}(1-\varepsilon
s)n-1-s\cdot\varepsilon sn>0.$

Consequently,

$\displaystyle|G|<\binom{st}{2}+\mathrm{ex}\left(n-st,\mathbb{B}\right)+s_{1}sn\leq\binom{\hat{t}}{2}+\mathrm{ex}\left(n-\hat{t},\mathbb{B}\right)+s_{1}sn,$

completing the proof of Theorem 1.16.

###  4.2 Hypergraphs: proof of Theorem 1.15

The proof strategy for Theorem 1.15 is similar to that of Theorem 1.16, except
in the hypergraph case where we substitute Claim 4.2 with a less precise
estimate, as presented in Claim 4.4.

###### Proof of Theorem 1.15.

Fix integers $r\geq 3$, $s_{r}\geq\cdots\geq s_{1}\geq 2$, and an $r$-partite
$r$-graph $\mathbb{B}:=B_{s_{1},\ldots,s_{r}}^{r}$ with part sizes
$s_{1},\ldots,s_{r}$. Let

$\displaystyle s:=\sum_{i\in[r]}s_{i},\quad
A:=2er^{2}\prod_{i\in[r]}s_{i},\quad\text{and}\quad\varepsilon:=\frac{1}{8er^{2}s^{2}A}.$

Let $n$ be a sufficiently large integer and $t\in\left[\frac{n}{s}-\varepsilon
n,\frac{n}{s}\right]$ be an integer. Let $\mathcal{H}$ be a maximum $n$-vertex
$(t+1)\mathbb{B}$-free $r$-graph. Let $\hat{t}:=s(t+1)-1$ for simplicity. It
follows from Proposition 1.5 and Fact 2.14 that

$\displaystyle|\mathcal{H}|\geq
g_{3}(n,t,\mathbb{B})=\binom{\hat{t}}{r}+\mathrm{ex}\left(n-\hat{t},\mathbb{B}\right)\geq\binom{st}{r}+\mathrm{ex}(n-st,\mathbb{B}).$
(12)

Let $\mathcal{B}=\\{\mathbb{B}_{1},\ldots,\mathbb{B}_{t}\\}$ be a collection
of vertex-disjoint copies of $\mathbb{B}$ in $\mathcal{H}$ (the existence of
such a collection follows from the maximality of $\mathcal{H}$). Let

$\displaystyle V:=V(\mathcal{H}),\quad
V_{1}:=\bigcup_{i\in[t]}V(\mathbb{B}_{i}),\quad V_{2}:=V\setminus
V_{1},\quad\text{and}\quad\mathcal{H}_{i}:=\mathcal{H}[V_{i}]\quad\text{for
$i\in\\{1,2\\}$}.$

Observe that $|V_{1}|=st$ and $\mathcal{H}_{2}$ is $\mathbb{B}$-free. Hence,
by Theorem 2.9, we have

$\displaystyle|\mathcal{H}_{2}|\leq\mathrm{ex}\left(n-st,\mathbb{B}\right)\leq
C(n-st)^{r-\frac{1}{s_{1}\cdots s_{r-1}}}.$ (13)

Since $n-st\leq\varepsilon sn\leq\frac{n}{2r}$, it follows from Fact 2.2 that

$\displaystyle|\mathcal{H}[V_{1},V_{2}]|\leq\sum_{v\in
V_{2}}d_{\mathcal{H}}(v)\leq(n-st)\binom{n-1}{r-1}<e(n-st)\binom{st-1}{r-1}.$
(14)

Let

$\displaystyle\alpha:=1-\frac{1}{2A},\quad L:=\left\\{v\in V_{1}\colon
d_{\mathcal{H}_{1}}(v)\geq\alpha\binom{st-1}{r-1}\right\\},\quad
S:=V_{1}\setminus L,\quad\text{and}\quad\ell:=|L|.$

It follows from the definition of $L$ that

$\displaystyle|\mathcal{H}_{1}|$ $\displaystyle=\frac{1}{r}\left(\sum_{v\in
L}d_{\mathcal{H}_{1}}(v)+\sum_{v\in S}d_{\mathcal{H}_{1}}(v)\right)$
$\displaystyle\leq\frac{1}{r}\left(\ell\binom{st-1}{r-1}+(st-\ell)\alpha\binom{st-1}{r-1}\right)=\binom{st}{r}-(1-\alpha)\frac{st-\ell}{r}\binom{st-1}{r-1}.$
(15)

######  Claim 4.3.

We have $|S|<\frac{er(n-st)}{1-\alpha}$.

###### Proof.

It follows from (13), (14), and (4.2) that

$\displaystyle|\mathcal{H}|$
$\displaystyle=|\mathcal{H}_{1}|+|\mathcal{H}[V_{1},V_{2}]|+|\mathcal{H}_{2}|$
$\displaystyle<\binom{st}{r}-(1-\alpha)\frac{st-\ell}{r}\binom{st-1}{r-1}+e(n-st)\binom{st-1}{r-1}+\mathrm{ex}\left(n-st,\mathbb{B}\right).$

Combined with (12), we obtain

$\displaystyle-(1-\alpha)\frac{st-\ell}{r}\binom{st-1}{r-1}+e(n-st)\binom{st-1}{r-1}>0,$

which implies that $|S|=st-\ell<\frac{er(n-st)}{1-\alpha}$.

Let $\mathcal{B}_{S}$ be the collection of elements in $\mathcal{B}$ that have
nonempty intersection with $S$. Let

$\displaystyle
S_{1}:=\bigcup_{\mathbb{B}_{i}\in\mathcal{B}_{S}}V(\mathbb{B}_{i})\quad\text{and}\quad
L_{1}:=V_{1}\setminus S_{1}.$

Observe that $S\subset S_{1}$ and $L_{1}\subset L$. Also observe from Claim
4.3 that

$\displaystyle|S_{1}|\leq s|S|\leq\frac{ers(n-st)}{1-\alpha}.$ (16)

######  Claim 4.4.

The $r$-graph $\mathcal{H}^{\prime}:=\mathcal{H}[L_{1}\cup
V_{2}]\setminus\mathcal{H}[L_{1}]$ is $s\mathbb{B}$-free. In particular, we
have

$\displaystyle|\mathcal{H}^{\prime}|\leq\mathrm{ex}_{\mathrm{star}}(n-st,n,s\mathbb{B}).$

###### Proof.

Suppose to the contrary that there exists a collection
$\mathcal{B}^{\prime}=\\{\mathbb{B}_{1}^{\prime},\ldots,\mathbb{B}_{s}^{\prime}\\}$
of pairwise vertex-disjoint copies of $\mathbb{B}$ in $\mathcal{H}^{\prime}$.
Let $W:=\bigcup_{i\in[s]}V(\mathbb{B}^{\prime}_{i})$, $W_{1}:=W\cap L_{1}$,
and $W_{2}:=W\cap V_{2}$. Observe that every $\mathbb{B}_{i}^{\prime}$
contains at least one vertex from $V_{2}$ (since $L_{1}$ is an independent set
in $\mathcal{H}^{\prime}$). So we have $|W_{1}|\leq(s-1)s$. It follows that

$\displaystyle|V_{1}\setminus W_{1}|\geq st-(s-1)s=s\left(t+1-s\right).$

Fix an arbitrary subset $L_{1}^{\prime}\subset L_{1}\setminus W_{1}$ of size
exactly $s\left(t+1-s\right)-|S_{1}|$. It follows from the definition of $L$
that the induced subgraph $\mathcal{H}[L_{1}^{\prime}]$ satisfies

$\displaystyle\delta(\mathcal{H}[L_{1}^{\prime}])$
$\displaystyle\geq\alpha\binom{st-1}{t-1}-|V_{1}\setminus
L_{1}^{\prime}|\binom{st-2}{r-2}$
$\displaystyle\geq\alpha\binom{st-1}{t-1}-\left(|S_{1}|+(s-1)s\right)\frac{r-1}{st-1}\binom{st-1}{r-1}$
$\displaystyle>\left(\alpha-\left(\frac{ers(n-st)}{1-\alpha}+s^{2}\right)\frac{r-1}{st-1}\right)\binom{st-1}{r-1},$

where the last inequality follows from (16). Since $n$ is sufficiently large
and $t\geq n/s-\varepsilon n$, simple calculations show that
$\left(\frac{ers(n-st)}{1-\alpha}+s^{2}\right)\frac{r-1}{st-1}<\frac{1}{2A}$.
Therefore, we have
$\delta(\mathcal{H}[L_{1}^{\prime}])\geq\left(1-\frac{1}{A}\right)\binom{st-1}{r-1}$.
It follows from Theorem 2.12 that
$\left(t+1-s-|S_{1}|/s\right)\mathbb{B}\subset\mathcal{H}[L_{1}^{\prime}]$.
However, these $t+1-s-|S_{1}|/s$ copies of $\mathbb{B}$ together with
$\mathcal{B}_{S}\cup\mathcal{B}^{\prime}$ show that
$(t+1)\mathbb{B}\subset\mathcal{H}$, a contradiction.

Let $\mathcal{H}^{\prime\prime}:=\left\\{e\in\mathcal{H}\colon e\cap
S_{1}\neq\emptyset\text{ and }e\cap V_{2}\neq\emptyset\right\\}$. Using Fact
2.2 and Claim 4.3, we obtain

$\displaystyle|\mathcal{H}^{\prime\prime}|\leq|S_{1}||V_{2}|\binom{n-2}{r-2}$
$\displaystyle\leq s|S|\times(n-st)\times e\binom{st-2}{r-2}$
$\displaystyle\leq es(n-st)|S|\times\frac{r}{st}\binom{st-1}{r-1}$
$\displaystyle=\frac{\varepsilon
er^{2}sn}{(1/s-\varepsilon)n}\frac{st-\ell}{r}\binom{st-1}{r-1}\leq\frac{1}{4A}\frac{st-\ell}{r}\binom{st-1}{r-1},$

where the last inequality follows from $\varepsilon=\frac{1}{8er^{2}s^{2}A}$.
Combined with (4.2) and Claim 4.4, we obtain

$\displaystyle|\mathcal{H}|$
$\displaystyle=|\mathcal{H}_{1}|+|\mathcal{H}^{\prime\prime}|+|\mathcal{H}^{\prime}|$
$\displaystyle\leq\binom{st}{r}-(1-\alpha)\frac{st-\ell}{r}\binom{st-1}{r-1}+\frac{1}{4A}\frac{st-\ell}{r}\binom{st-1}{r-1}+\mathrm{ex}_{\mathrm{star}}(n-st,n,s\mathbb{B})$
$\displaystyle=\binom{st}{r}-\left(\frac{1}{2A}-\frac{1}{4A}\right)\frac{st-\ell}{r}\binom{st-1}{r-1}++\mathrm{ex}_{\mathrm{star}}(n-st,n,s\mathbb{B})$
$\displaystyle<\binom{s(t+1)-1}{r}++\mathrm{ex}_{\mathrm{star}}(n-st,n,s\mathbb{B}),$

completing the proof of Theorem 1.15.

##  5 Proofs for theorems in the second interval

In this section, we prove Theorems 1.11 and 1.12. Let us start with some
technical lemmas.

###  5.1 Preparations

Using Proposition 2.11, we establish the following lemma, ensuring a near-
perfect $K_{s_{1},\ldots,s_{r}}^{r}$-matching in a semibipartite $r$-graph
with a minimum degree of $\Omega(n^{r-1})$ on one side.

######  Lemma 5.1.

Let $r\geq 2$ and $s_{r}\geq\cdots\geq s_{1}\geq 2$ be integers and let
$\alpha>0$ be a real number. Let $s:=s_{1}+\cdots+s_{r}$ and
$\mathbb{K}:=K_{s_{1},\ldots,s_{r}}^{r}$. The following holds for sufficiently
large $n$. Suppose that $\mathcal{H}$ is an $m$ by $n$ semibipartite $r$-graph
on $V_{1}$ and $V_{2}$ with $m\leq\frac{\alpha n}{s-s_{1}}$ and
$d_{\mathcal{H}}(v)\geq\alpha n^{r-1}$ for every $v\in V_{1}$. Then
$\mathcal{H}$ contains at least
$\left\lfloor\frac{m}{s_{1}}-\frac{4}{\alpha}\right\rfloor$ pairwise vertex-
disjoint copies of ordered $\mathbb{K}$.

###### Proof.

Let $n$ be sufficiently large and $\mathcal{H}$ be an $m$ by $n$ semibipartite
$r$-graph on $V_{1}$ and $V_{2}$ with $n\geq(s-s_{1})m/\alpha$ and
$d_{\mathcal{H}}(v)\geq\alpha n^{r-1}$ for every $v\in V_{1}$. We may assume
that $m\geq\frac{4s_{1}}{\alpha}$, since otherwise
$\left\lfloor\frac{m}{s_{1}}-\frac{4}{\alpha}\right\rfloor\leq 0$, and there
is nothing to prove. Let $\mathcal{K}=\\{K_{1},\ldots,K_{\ell}\\}$ be a
maximum collection of pairwise vertex-disjoint copies of ordered $K$ in
$\mathcal{H}$. Let $B:=\bigcup_{i\in[\ell]}V(K_{i})$, $B_{i}:=B\cap V_{i}$,
and $V_{i}^{\prime}:=V_{i}\setminus B_{i}$ for $i\in\\{1,2\\}$. Let
$\mathcal{H}^{\prime}$ be the induced subgraph of $\mathcal{H}$ on
$V_{1}^{\prime}\cup V_{2}^{\prime}$ and note that $\mathcal{H^{\prime}}$ is
also semibipartite. Suppose to the contrary that
$\ell\leq\frac{m}{s_{1}}-\frac{4}{\alpha}$. Then $|B_{1}|=s_{1}\ell\leq
m-\frac{4s_{1}}{\alpha}$ and
$|B_{2}|=(s-s_{1})\ell\leq(s-s_{1})\frac{m}{s_{1}}\leq\frac{\alpha n}{s_{1}}$.
Therefore, $|V_{1}^{\prime}|=m-|B_{1}|\geq\frac{4s_{1}}{\alpha}$ and

$\displaystyle|\mathcal{H}^{\prime}|=\sum_{v\in
V_{1}^{\prime}}d_{\mathcal{H}^{\prime}}(v)$ $\displaystyle\geq\sum_{v\in
V_{1}^{\prime}}\left(d_{\mathcal{H}}(v)-|B_{2}|\binom{n-1}{r-2}\right)$
$\displaystyle\geq|V_{1}^{\prime}|\left(\alpha n^{r-1}-\frac{\alpha
n}{s_{1}}\binom{n-1}{r-2}\right)$
$\displaystyle\geq|V_{1}^{\prime}|\times\frac{\alpha}{2}n^{r-1}$
$\displaystyle=|V_{1}^{\prime}|\times\frac{\alpha}{4}n^{r-1}+|V_{1}^{\prime}|\times\frac{\alpha}{4}n^{r-1}\geq
C|V_{1}^{\prime}|n^{r-1-\frac{1}{s_{1}\cdots s_{r-1}}}+s_{1}n^{r-1}.$

It follows from Proposition 2.11 that $\mathcal{H}^{\prime}$ contains an
ordered copy of $K$, contradicting the maximality of $\mathcal{K}$.

If we extend the assumptions in Lemma 5.1 by assuming the number of vertices
with near-maximum degree is at least some constant, then we can enhance the
lemma by finding a perfect $K_{s_{1},\ldots,s_{r}}^{r}$-matching. The proof
relies on a simple absorption strategy, pairing a low-degree vertex with
$s_{1}-1$ high-degree vertices.

$V_{1}$$V_{2}$$L$$S$ Figure 3: Supplementary diagram for Claim 5.2 when
$F=K_{3,3}$.

######  Lemma 5.2.

Let $r\geq 2$ and $s_{r}\geq\cdots\geq s_{1}\geq 2$ be integers and $\alpha>0$
be a real number. Let $s:=s_{1}+\cdots+s_{r}$ and
$\mathbb{K}:=K_{s_{1},\ldots,s_{r}}^{r}$. The following statement holds for
sufficiently large $n$. Suppose that $\mathcal{H}$ is an $m$ by $n$
semibipartite $r$-graph on $V_{1}$ and $V_{2}$ that satisfies

  1. (i)

$m\leq\frac{\alpha n}{8(s-s_{1})}$,

  2. (ii)

$d_{\mathcal{H}}(v)\geq\alpha n^{r-1}$ for every $v\in V_{1}$, and

  3. (iii)

$L:=\left\\{v\in V_{1}\colon d(v)\geq\binom{n}{r-1}-\frac{\alpha
n^{r-1}}{2s_{1}}\right\\}$ has size at least
$\min\left\\{\frac{5s_{1}(s_{1}-1)}{\alpha},\
\frac{s_{1}-1}{s_{1}}m\right\\}$.

Then $\mathcal{H}$ contains $\left\lfloor m/s_{1}\right\rfloor$ pairwise
vertex-disjoint copies of ordered $\mathbb{K}$.

###### Proof.

Let $S:=V_{1}\setminus L$, $\mathcal{H}_{S}:=\mathcal{H}[S\cup V_{2}]$, and
$\mathcal{K}_{S}=\\{\mathbb{K}_{1},\ldots,\mathbb{K}_{\ell}\\}$ be a maximum
collection of ordered copies of $\mathbb{K}$ in $\mathcal{H}_{S}$. Let

$\displaystyle B_{S}:=\bigcup_{i\in[\ell]}V(\mathbb{K}_{i}),\quad
V_{2}^{\prime}:=V_{2}\setminus B_{S},\quad S_{1}:=S\setminus
B_{S},\quad\text{and}\quad m_{1}:=|S_{1}|.$

It follows from Lemma 5.1 that
$\ell\geq\max\left\\{\left\lfloor\frac{|S|}{s_{1}}-\frac{4}{\alpha}\right\rfloor,\
0\right\\}$, and hence,

$\displaystyle
m_{1}=|S|-s_{1}\ell\leq|S|-s_{1}\times\max\left\\{\left\lfloor\frac{|S|}{s_{1}}-\frac{4}{\alpha}\right\rfloor,\
0\right\\}\leq\min\left\\{\frac{5s_{1}}{\alpha},\ |S|\right\\}.$ (17)

Let us assume that $S_{1}:=\\{v_{1},\ldots,v_{m_{1}}\\}$. Let
$T_{1},\ldots,T_{m_{1}}$ be pairwise disjoint $(s_{1}-1)$-subsets of $L$ (the
existence of such $T_{i}$’s is guaranteed by (iii) and (17)). Let
$\mathcal{H}_{i}$ denote the induced subgraph of $\mathcal{H}$ on
$\\{v_{i}\\}\cup T_{i}\cup V_{2}^{\prime}$ for $i\in[m_{1}]$.

Let $B_{0}:=\emptyset$. Suppose that we have defined $B_{i}\subset V_{2}$ of
size $i(s-s_{1})$ for some $i\in[0,m_{1}-1]$. We will find an ordered copy of
$\mathbb{K}$ in $\mathcal{H}_{i+1}^{\prime}:=\mathcal{H}_{i+1}-B_{i}$. Indeed,
notice from (i) that

$\displaystyle|B_{i}\cup B_{S}|\leq\frac{m}{s_{1}}(s-s_{1})\leq\frac{\alpha
n}{4}.$

Combined with (ii) and (iii), we see that the common link
$L_{\mathcal{H}_{i+1}^{\prime}}(T_{i+1}\cup\\{v_{i+1}\\})$ satisfies

$\displaystyle L_{\mathcal{H}_{i+1}^{\prime}}(T_{i+1}\cup\\{v_{i+1}\\})$
$\displaystyle\geq d_{\mathcal{H}}(v_{i+1})-\sum_{u\in
T_{i+1}}\left(\binom{n}{r-1}-d_{\mathcal{H}}(u)\right)-|B_{i}\cup
B_{S}|\binom{n-1}{r-2}$ $\displaystyle\geq\alpha n^{r-1}-(s_{1}-1)\frac{\alpha
n^{r-1}}{2s_{1}}-\frac{\alpha n}{4}\binom{n-1}{r-2}\geq\frac{\alpha
n^{r-1}}{4}.$

Since $n$ is sufficiently large, it follows from Theorem 2.9 that
$K_{s_{2},\ldots,s_{r}}^{r-1}\subset
L_{\mathcal{H}_{i+1}^{\prime}}(T_{i+1}\cup\\{v_{i+1}\\})$. This copy of
$K_{s_{2},\ldots,s_{r}}^{r-1}$ together with $T_{i+1}\cup\\{v_{i+1}\\}$ forms
a copy of ordered $\mathbb{K}$ in $\mathcal{H}_{i+1}^{\prime}$ (see Figure 3).
Denoted this copy of ordered $\mathbb{K}$ by $\mathbb{K}^{\prime}_{i+1}$. Let
$B_{i+1}:=B_{i}\cup(V(\mathbb{K}^{\prime}_{i+1})\cap V_{2})$ and notice that
$|B_{i+1}|=|B_{i}|+s-s_{1}=(i+1)(s-s_{1})$. Inductively, we can find a copy of
ordered $\mathbb{K}$, denoted by $\mathbb{K}_{i}^{\prime}$, from
$\mathcal{H}_{i}$ for every $i\in[m_{1}]$ such that
$\mathbb{K}^{\prime}_{1},\ldots,\mathbb{K}^{\prime}_{m_{1}}$ are pairwise
vertex-disjoint. Let $L^{\prime}:=L\setminus\bigcup_{i\in[m_{i}]}T_{i}$ and
$V_{2}^{\prime\prime}:=V_{2}\setminus(B_{m_{1}}\cup B_{S})$. Repeating the
argument above to the induced subgraph of $\mathcal{H}$ on $L^{\prime}\cup
V_{2}^{\prime\prime}$, we can find $\lfloor m/s_{1}\rfloor-m_{1}-\ell$
pairwise vertex-disjoint ordered copies of $\mathbb{K}$ in
$\mathcal{H}[L^{\prime}\cup V_{2}^{\prime\prime}]$, showing that $\mathcal{H}$
contains at least $\left\lfloor m/s_{1}\right\rfloor$ pairwise vertex-disjoint
copies of ordered $\mathbb{K}$ (see Figure 3).

A minor adjustment to the proof of Lemma 5.2 results in the following simple
lemma.

######  Lemma 5.3.

Let $r\geq 2$ and $s_{r}\geq\cdots\geq s_{1}\geq 2$ be integers and
$\alpha<1/s_{1}$ be a nonnegative real number. Let $s:=s_{1}+\cdots+s_{r}$ and
$\mathbb{K}:=K_{s_{1},\ldots,s_{r}}^{r}$. The following statement holds for
sufficiently large $n$. Suppose that $\mathcal{H}$ is an $m$ by $n$
semibipartite $r$-graph on $V_{1}$ and $V_{2}$ that satisfies

$\displaystyle m\leq\frac{(1-\alpha
s_{1})s_{1}}{(r-1)(s-s_{1})}n\quad\text{and}\quad
d_{\mathcal{H}}(v)\geq(1-\alpha)\binom{n}{r-1}\quad\text{for all $v\in
V_{1}$}.$

Then $\mathcal{H}$ contains $\left\lfloor m/s_{1}\right\rfloor$ pairwise
vertex-disjoint copies of ordered $\mathbb{K}$.

Using Lemma 5.1, we can derive the following crude but useful upper bound for
$\mathrm{ex}(n,(t+1)F)$.

######  Lemma 5.4.

Let $r\geq 2$ and $s_{r}\geq\cdots\geq s_{1}\geq 2$ be integers. Let
$s:=s_{1}+\cdots+s_{r}$ and $\mathbb{B}:=B_{s_{1},\ldots,s_{r}}^{r}$ be an
$r$-partite $r$-graph with part sizes $s_{1},\ldots,s_{r}$. For every
$\alpha>0$ there exists $N_{0}$ such that the following statement holds for
all $n\geq N_{0}$ and $t\leq\frac{\alpha n}{9s^{2}r!}$. Every $n$-vertex
$(t+1)\mathbb{B}$-free $r$-graph $\mathcal{H}$ satisfies

$\displaystyle|\mathcal{H}|\leq\left(s_{1}t+\frac{17sr!}{\alpha}\right)\Delta(\mathcal{H})+\frac{\alpha
s_{1}}{2r!}tn^{r-1}+\mathrm{ex}(n-st,\mathbb{B}).$

If, in addition, $\Delta(\mathcal{H})\leq(1-\alpha)\binom{n-1}{r-1}$ and
$t\geq\frac{5}{\alpha
s_{1}}\left(\frac{\mathrm{ex}(n,\mathbb{B})}{\binom{n-1}{r-1}}+\frac{18sr!}{\alpha}\right)$,
then

$\displaystyle|\mathcal{H}|\leq\binom{n}{r}-\binom{n-s_{1}(t-1)}{r}.$

###### Proof.

Fix $\alpha>0$ and let $n$ be sufficiently large. Let $\mathcal{H}$ be a
maximum $n$-vertex $(t+1)\mathbb{B}$-free $r$-graph. Let
$\mathcal{B}=\\{\mathbb{B}_{1},\ldots,\mathbb{B}_{t}\\}$ be a collection of
pairwise vertex-disjoint copies of $\mathbb{B}$ in $\mathcal{H}$. Let

$\displaystyle V:=V(\mathcal{H}),\ V_{1}:=\bigcup_{i\in[t]}V(\mathbb{B}_{i}),\
V_{2}:=V\setminus V_{1},\quad\text{and}\quad L:=\left\\{v\in V_{1}\colon
d_{\mathcal{H}}(v)\geq\frac{\alpha s_{1}n^{r-1}}{2sr!}\right\\}.$

######  Claim 5.5.

We have $|L|\leq\left(t+1+\frac{16sr!}{\alpha s_{1}}\right)s_{1}$.

###### Proof.

Suppose this is not true. Let

$\displaystyle m:=\left\lceil\left(t+1+\frac{16sr!}{\alpha
s_{1}}\right)s_{1}\right\rceil\leq 2\times\frac{\alpha n}{9s^{2}r!}\times
s_{1}\leq\frac{\alpha s_{1}n}{4s^{2}r!}\leq\frac{\alpha(n-m)}{8s}.$

We may assume that $|L|=m$, since otherwise we can replace $L$ by a subset of
size $m$. Let $\mathcal{H}^{\prime}$ be the collection of edges in
$\mathcal{H}$ that have exactly one vertex in $L$. Notice that
$\mathcal{H}^{\prime}$ is semibipartite and for every $v\in L$, we have

$\displaystyle d_{\mathcal{H}^{\prime}}(v)\geq
d_{\mathcal{H}}(v)-|L|\binom{n-2}{r-2}\geq\frac{\alpha
s_{1}n^{r-1}}{2sr!}-m\frac{r-1}{n-1}\binom{n-1}{r-1}\geq\frac{\alpha
s_{1}n^{r-1}}{4sr!}.$

Therefore, by Lemma 5.1, the semibipartite $r$-graph $\mathcal{H}^{\prime}$
contains at least

$\displaystyle\left\lfloor\frac{m}{s_{1}}-4\left(\frac{\alpha
s_{1}}{4sr!}\right)^{-1}\right\rfloor\geq\left\lfloor t+1+\frac{16sr!}{\alpha
s_{1}}-\frac{16sr!}{\alpha s_{1}}\right\rfloor=t+1$

copies of ordered $\mathbb{B}$, a contradiction.

It follows from Claim 5.5 and some simple calculations that

$\displaystyle|\mathcal{H}|$ $\displaystyle=\sum_{v\in
L}d_{\mathcal{H}}(v)+\sum_{v\in V_{1}\setminus
L}d_{\mathcal{H}}(v)+|\mathcal{H}[V_{2}]|$
$\displaystyle\leq\left(s_{1}t+s_{1}+\frac{16sr!}{\alpha}\right)\Delta(\mathcal{H})+st\times\frac{\alpha
s_{1}n^{r-1}}{2sr!}+\mathrm{ex}(n-st,\mathbb{B})$
$\displaystyle\leq\left(s_{1}t+\frac{17sr!}{\alpha}\right)\Delta(\mathcal{H})+\frac{\alpha
s_{1}}{2r!}tn^{r-1}+\mathrm{ex}(n-st,\mathbb{B}).$

Assume additionally that $\Delta(\mathcal{H})\leq(1-\alpha)\binom{n-1}{r-1}$
and $t\geq\frac{5}{\alpha
s_{1}}\left(\frac{\mathrm{ex}(n,\mathbb{B})}{\binom{n-1}{r-1}}+\frac{18sr!}{\alpha}\right)$.
Then it follows from the inequality above that

$\displaystyle|\mathcal{H}|$
$\displaystyle\leq\left(s_{1}t+\frac{17sr!}{\alpha}\right)(1-\alpha)\binom{n-1}{r-1}+\frac{\alpha
s_{1}}{2r!}tn^{r-1}+\mathrm{ex}(n-st,\mathbb{B})$ $\displaystyle\leq
s_{1}t\left(1-\frac{\alpha}{2}\right)\binom{n-1}{r-1}-s_{1}t\frac{\alpha}{2}\binom{n-1}{r-1}+\frac{17sr!}{\alpha}\binom{n-1}{r-1}+\frac{\alpha
s_{1}}{2r!}tn^{r-1}+\mathrm{ex}(n,\mathbb{B}).$

Since $n$ is large and $t\geq\frac{5}{\alpha
s_{1}}\left(\frac{\mathrm{ex}(n,\mathbb{B})}{\binom{n-1}{r-1}}+\frac{18sr!}{\alpha}\right)$,
we have

$\displaystyle-
s_{1}t\frac{\alpha}{2}\binom{n-1}{r-1}+\frac{17sr!}{\alpha}\binom{n-1}{r-1}+\frac{\alpha
s_{1}}{2r!}tn^{r-1}+\mathrm{ex}(n,\mathbb{B})$
$\displaystyle\leq-\left(\frac{\alpha
s_{1}}{2}t-\frac{18sr!}{\alpha}-\frac{\alpha
s_{1}}{2r}t-o(1)-\frac{\mathrm{ex}(n,\mathbb{B})}{\binom{n-1}{r-1}}\right)\binom{n-1}{r-1}-s_{1}\binom{n-1}{r-1}$
$\displaystyle\leq-\left(\frac{\alpha
s_{1}}{5}t-\frac{18sr!}{\alpha}-\frac{\mathrm{ex}(n,\mathbb{B})}{\binom{n-1}{r-1}}\right)\binom{n-1}{r-1}-s_{1}\binom{n-1}{r-1}\leq-
s_{1}\binom{n-1}{r-1}.$

It follows $t\leq\frac{\alpha n}{9s^{2}r!}$, Facts 2.1, and 2.4 that

$\displaystyle\left(1-\frac{\alpha}{2}\right)\binom{n-1}{r-1}$
$\displaystyle\leq\left(1-\frac{\alpha}{2}\right)\left(\frac{n}{n-s_{1}t-r}\right)^{r-1}\binom{n-s_{1}t}{r-1}$
$\displaystyle\leq\left(1-\frac{\alpha}{2}\right)\left(1+\frac{4(r-1)(s_{1}t+r)}{n}\right)\binom{n-s_{1}t}{r-1}$
$\displaystyle\leq\left(1-\frac{\alpha}{2}\right)\left(1+\frac{\alpha}{2}\right)\binom{n-s_{1}t}{r-1}\leq\binom{n-s_{1}t}{r-1}.$

Therefore, we obtain

$\displaystyle|\mathcal{H}|\leq
s_{1}(t-1)\binom{n-s_{1}t}{r-1}+s_{1}\binom{n-1}{r-1}-s_{1}\binom{n-1}{r-1}\leq\binom{n}{r}-\binom{n-s_{1}(t-1)}{r},$

completing the proof of Lemma 5.4.

###  5.2 Hypergraphs: proof of Theorem 1.11

In this subsection, we establish the validity of Theorem 1.11. Our proof
strategy begins by considering the collection $L\subset V(\mathcal{H})$ of all
vertices in an $n$-vertex $(t+1)F$-free $r$-graph $\mathcal{H}$ with degree at
least $\Omega(n^{r-1})$. Our will show that a significant proportion of
vertices in $L$ possess near-maximum degree. Consequently, leveraging Lemma
5.2, we can infer that the size of $L$ is less than $s_{1}(t+1)$.
Subsequently, we show that the induced subgraph $\mathcal{H}-L$ cannot
contains many vertex-disjoint copies of $F$. By employing the size constraint
provided by Lemma 2.13 on $\mathcal{H}-L$, we derive the desired upper bound
on $|\mathcal{H}|$.

###### Proof of Theorem 1.11.

Fix integers $r\geq 2$, $s_{r}\geq\cdots\geq s_{1}\geq 2$, and an $r$-partite
$r$-graph $B_{s_{1},\ldots,s_{r}}^{r}=:\mathbb{B}$ with part sizes
$s_{1},\ldots,s_{r}$. Let

$\displaystyle
s:=\sum_{i\in[r]}s_{i},\quad\delta_{1}:=\frac{1}{16es_{1}s},\quad\delta_{2}:=\frac{1}{2es},\quad\text{and}\quad\varepsilon:=\frac{\delta_{1}}{32s^{2}r!}.$

Let $n$ be sufficiently large and $t$ be an integer satisfying

$\displaystyle\frac{20}{\delta_{1}}\left(\frac{\mathrm{ex}(n,\mathbb{B})}{\binom{n-1}{r-1}}+\frac{20sr!}{\delta_{1}}\right)\leq
t\leq\varepsilon n.$ (18)

Let $\mathcal{H}$ be a maximum $n$-vertex $(t+1)\mathbb{B}$-free $r$-graph
with vertex $V$. Let

$\displaystyle L_{1}:=\left\\{v\in V\colon
d_{\mathcal{H}}(v)\geq(1-\delta_{1})\binom{n-1}{r-1}\right\\},\
L_{2}:=\left\\{v\in V\setminus L_{1}\colon
d_{\mathcal{H}}(v)\geq\delta_{2}\binom{n-1}{r-1}\right\\},$

and

$\displaystyle L$ $\displaystyle:=L_{1}\cup L_{2},\quad U:=V\setminus
L,\quad\ell:=|L|,\quad\ell_{1}:=|L_{1}|,\quad\ell_{2}:=|L_{2}|.$

In addition, let

$\displaystyle\mathcal{H}_{1}:=\mathcal{H}-L_{1},\quad\mathcal{H}_{2}:=\mathcal{H}[U],\quad
n_{1}:=n-\ell_{1},\quad\text{and}\quad
t_{1}:=t-\left\lfloor\ell_{1}/s_{1}\right\rfloor.$

######  Claim 5.6.

We have $\ell_{1}<s_{1}(t+1)$ and $\mathcal{H}_{1}$ is
$(t_{1}+1)\mathbb{B}$-free.

###### Proof.

First, suppose to the contrary that $\ell_{1}\geq s_{1}(t+1)$. We may assume
that $\ell_{1}=s_{1}(t+1)$ since otherwise we can take a subset of $L_{1}$ of
size $s_{1}(t+1)$. Let $\mathcal{G}$ be the collection of edges in
$\mathcal{H}$ that have exactly one vertex in $L_{1}$. Notice that
$\mathcal{G}$ is semibipartite, and for every $v\in L_{1}$ it follows from the
assumptions on $t$ and $\delta_{1}$ that

$\displaystyle d_{\mathcal{G}}(v)\geq
d_{\mathcal{H}}(v)-|L_{1}|\binom{n-2}{r-2}$
$\displaystyle\geq(1-\delta_{1})\binom{n-1}{r-1}-s_{1}(t+1)\frac{r-1}{n-1}\binom{n-1}{r-1}$
$\displaystyle>\left(1-\frac{1}{16s_{1}s}\right)\binom{n-1}{r-1}.$

Since, in addition,
$\left(1-\frac{s_{1}}{16s_{1}s}\right)s_{1}\frac{1}{(r-1)(s-s_{1})}(n-\ell_{1})\geq
2\varepsilon s_{1}n\geq\ell_{1}$ (by (18)), it follows from Lemma 5.3 that
$(t+1)\mathbb{B}\subset(t+1)K_{s_{1},\ldots,s_{r}}^{r}\subset\mathcal{G}$, a
contradiction.

Now suppose to the contrary that there exists a collection
$\mathcal{B}=\\{\mathbb{B}_{1},\ldots,\mathbb{B}_{t_{1}+1}\\}$ of $t_{1}+1$
pairwise vertex-disjoint copies of $\mathbb{B}$ in $\mathcal{H}_{1}$. Let
$B:=\bigcup_{i\in[t_{1}+1]}V(\mathbb{B}_{i})$ and $V^{\prime}:=V\setminus B$.
Let $\mathcal{G}_{1}$ be the collection of edges in $\mathcal{H}[V^{\prime}]$
that contain exactly one vertex in $L_{1}$. Similar to the argument above, we
have

$\displaystyle d_{\mathcal{G}_{1}}(v)\geq d_{\mathcal{H}}(v)-|L_{1}\cup
B_{1}|\binom{n-2}{r-2}$
$\displaystyle\geq(1-\delta_{1})\binom{n-1}{r-1}-2s(t+1)\frac{r-1}{n-1}\binom{n-1}{r-1}$
$\displaystyle>\left(1-\frac{1}{16s_{1}s}\right)\binom{n-1}{r-1}.$

Similarly, it follows from (18) and Lemma 5.3 that
$\lfloor\ell_{1}/s_{1}\rfloor\mathbb{B}\subset\mathcal{G}_{1}$, which together
with $\mathcal{B}$ implies that $(t+1)\mathbb{B}\subset\mathcal{H}$, a
contradiction.

By Claim 5.6, we obtain

$\displaystyle n_{1}-r=n-\ell_{1}-r\geq n-s_{1}(t+1)-r\geq(1-2\varepsilon
s_{1})n.$

Combined with the definition of $L_{1}$, Facts 2.1, and 2.4, we obtain

$\displaystyle\Delta(\mathcal{H}_{1})\leq(1-\delta_{1})\binom{n-1}{r-1}$
$\displaystyle\leq(1-\delta_{1})\left(\frac{n}{n_{1}-r}\right)^{r-1}\binom{n_{1}-1}{r-1}$
$\displaystyle\leq(1-\delta_{1})\left(1+8\varepsilon
rs_{1}\right)\binom{n_{1}-1}{r-1}$
$\displaystyle\leq(1-\delta_{1})\left(1+\frac{\delta_{1}}{4}\right)\binom{n_{1}-1}{r-1}\leq\left(1-\frac{\delta_{1}}{2}\right)\binom{n_{1}-1}{r-1}.$

Let

$\displaystyle\theta:=\frac{5}{\delta_{1}s_{1}/2}\left(\frac{\mathrm{ex}(n_{1},\mathbb{B})}{\binom{n_{1}-1}{r-1}}+\frac{18sr!}{\delta_{1}/2}\right)\leq\frac{10}{\delta_{1}s_{1}}\left(\frac{2\mathrm{ex}(n,\mathbb{B})}{\binom{n-1}{r-1}}+\frac{36sr!}{\delta_{1}}\right)\leq\frac{t-s+1}{s_{1}}.$

If $t_{1}\geq\theta$, then it follows from $t_{1}\leq
t\leq\frac{\delta_{1}n}{32s^{2}r!}\leq\frac{\delta_{1}n_{1}/2}{9s^{2}r!}$ and
Lemma 5.4 that

$\displaystyle|\mathcal{H}_{1}|\leq\binom{n_{1}}{r}-\binom{n_{1}-s_{1}(t_{1}-1)}{r}=\binom{n-\ell_{1}}{r}-\binom{n-s_{1}t}{r}.$

Consequently,

$\displaystyle|\mathcal{H}|\leq\binom{n}{r}-\binom{n-\ell_{1}}{r}+|\mathcal{H}_{1}|\leq\binom{n}{r}-\binom{n-s_{1}t}{r},$

and we are done. So we may assume that $t_{1}\leq\theta$, which implies that

$\displaystyle\ell_{1}\geq s_{1}\left(t-\theta\right)\geq
s_{1}\left(t-\frac{t-s+1}{s_{1}}\right)=\frac{s_{1}-1}{s_{1}}s_{1}(t+1).$ (19)

Let

$\displaystyle t_{2}:=t-\left\lfloor\ell/s_{1}\right\rfloor\leq
t_{1}\leq\theta.$

######  Claim 5.7.

We have $\ell_{1}+\ell_{2}\leq s_{1}(t+1)-1$, and $\mathcal{H}[U]$ is
$(t_{2}+1)\mathbb{B}$-free.

###### Proof.

The proof is similar to that of Claim 5.6. Suppose to the contrary that Claim
5.7 is not true. If $\ell<s_{1}(t+1)$, then let
$\mathcal{B}^{\prime}:=\left\\{\mathbb{B}_{1}^{\prime},\ldots,\mathbb{B}_{t_{2}+1}^{\prime}\right\\}$
be a collection of pairwise vertex-disjoint copies of $\mathbb{B}$ in
$\mathcal{H}[U]$ and let
$B^{\prime}:=\bigcup_{i\in[t_{2}+1]}V(\mathbb{B}_{i}^{\prime})$. If $\ell\geq
s_{1}(t+1)$, then by removing vertices in $L_{2}$, we may assume that
$\ell=s_{1}(t+1)$. In addition, we set $B^{\prime}:=\emptyset$ in this case.
Let $\mathcal{G}_{2}$ be the collection of all edges in
$\mathcal{H}[V\setminus B^{\prime}]$ that contain exactly one vertex in $L$
(recall that $L=L_{1}\cup L_{2}$). To build a contradiction, it suffices to
show that $\lfloor\ell/s_{1}\rfloor\mathbb{B}\subset\mathcal{G}_{2}$. Indeed,
observe that for every $v\in L_{1}$, we have

$\displaystyle d_{\mathcal{G}_{2}}(v)$ $\displaystyle\geq
d_{\mathcal{H}}(v)-|L\cup B^{\prime}|\binom{n-2}{r-2}$
$\displaystyle\geq(1-\delta_{1})\binom{n-1}{r-1}-2s(t+1)\frac{r-1}{n-1}\binom{n-1}{r-1}\geq\binom{n-1}{r-1}-\frac{\delta_{2}n^{r-1}}{4s_{1}},$

and for every $u\in L_{2}$, we have

$\displaystyle d_{\mathcal{G}_{2}}(u)$ $\displaystyle\geq
d_{\mathcal{H}}(u)-|L\cup B^{\prime}|\binom{n-2}{r-2}$
$\displaystyle\geq\delta_{2}\binom{n-1}{r-1}-2s(t+1)\frac{r-1}{n-1}\binom{n-1}{r-1}\geq\frac{\delta_{2}n^{r-1}}{2}.$

Since, in addition, $\ell\leq 2s_{1}t\leq 2\varepsilon
s_{1}n\leq\frac{1}{2}\frac{\delta_{2}n/2}{8(s-s_{1})}\leq\frac{\delta_{2}(n-|B^{\prime}|)/2}{8(s-s_{1})}$,
it follows from (19) and Lemma 5.2 that
$\lfloor\ell/s_{1}\rfloor\mathbb{B}\subset\mathcal{G}_{2}$, a contradiction.

Since $\mathcal{H}[U]$ is $(t_{2}+1)\mathbb{B}$-free and
$\Delta(\mathcal{H}[U])\leq\delta_{2}\binom{n-1}{r-1}\leq\frac{1}{2s}\binom{n-\ell-1}{r-1}$
(by Fact 2.3), it follows from Lemma 2.13 and simple calculations that

$\displaystyle|\mathcal{H}[U]|$ $\displaystyle\leq
st_{2}\times\frac{1}{2s}\binom{n-\ell-1}{r-1}+\mathrm{ex}(n-\ell-
st_{2},\mathbb{B})$ (20)
$\displaystyle\leq\binom{n-\ell}{r}-\binom{n-s_{1}(t+1)+1}{r-1}+\mathrm{ex}(n-s_{1}(t+1)+1,\mathbb{B}).$

It follows that

$\displaystyle|\mathcal{H}|$
$\displaystyle\leq\binom{n}{r}-\binom{n-\ell}{r}+|\mathcal{H}[U]|$
$\displaystyle\leq\binom{n}{r}-\binom{n-\ell}{r}+\binom{n-\ell}{r}-\binom{n-s_{1}(t+1)+1}{r-1}+\mathrm{ex}(n-s_{1}(t+1)+1,\mathbb{B})$
$\displaystyle=\binom{n}{r}-\binom{n-s_{1}(t+1)+1}{r}+\mathrm{ex}(n-s_{1}(t+1)+1,\mathbb{B}),$

completing the proof of Theorem 1.11.

###  5.3 Graphs: proof of Theorem 1.12

In this subsection, we establish the validity of Theorem 1.12. This proof is a
continuation of the argument in the previous subsection. In order to achieve
the precise result we desired, a more detailed analysis of the underlying
structures is necessary.

Given a family $\mathcal{F}$ of $r$-graphs and an integer $t\geq 0$ let

$\displaystyle(t+1)\mathcal{F}:=\left\\{F_{1}\sqcup\cdots\sqcup F_{t+1}\colon
F_{i}\in\mathcal{F}\text{ for all }i\in[t+1]\right\\}.$

We will need the following result which follows essentially from the same
proof for Theorem 1.7.

######  Proposition 5.8.

Let $s_{2}\geq s_{1}\geq 2$ be integers and $\mathbb{B}:=B_{s_{1},s_{2}}$ be
an $s_{1}$ by $s_{2}$ bipartite graph. Let
$\mathbb{B}^{\prime}:=\mathbb{B}[s_{2}+1]$. Suppose that
$t\leq\frac{n}{2e(s_{2}+1)}$. Then

$\displaystyle\mathrm{ex}\left(n,(t+1)\mathbb{B}^{\prime}\right)\leq\mathrm{ex}\left(n,\mathbb{B}^{\prime}\sqcup
tK_{1,s_{2}}\right)\leq\binom{n}{2}-\binom{n-t}{2}+\mathrm{ex}\left(n-t,(t+1)\mathbb{B}^{\prime}\right).$

###### Proof of Theorem 1.12.

Fix integers $s_{2}\geq s_{1}\geq 2$ and fix an $s_{1}$ by $s_{2}$ bipartite
connected graph $B_{s_{1},s_{2}}=:\mathbb{B}$. Let $s:=s_{1}+s_{2}$,
$\hat{t}:=s_{1}(t+1)-1$,

$\displaystyle\delta_{1}:=\frac{1}{16es_{1}s},\quad\delta_{2}:=\frac{1}{2es},\quad\varepsilon:=\frac{\delta_{1}}{64s^{2}},\quad\text{and}\quad\theta:=\frac{20}{\delta_{1}s_{1}}\left(\frac{\mathrm{ex}(n,\mathbb{B})}{n-1}+\frac{18sr!}{\delta_{1}}\right).$

Let $n$ be sufficiently large and $t$ be an integer satisfying

$\displaystyle\max\left\\{\sqrt{32s_{1}sn},\
\frac{20s^{2}\theta}{\delta_{3}s_{1}}\right\\}\leq t\leq\varepsilon n.$ (21)

Let $G$ be a maximum $n$-vertex $(t+1)\mathbb{B}$-free graph on $V$. Let
$L_{1},L_{2},L,U,\ell_{1},\ell_{2},\ell,n_{1},t_{1},t_{2}$ be the same as
defined in the proof of Theorem 1.11 (with $r=2$). All conclusions in the
previous subsection still hold for $G$. To summarize, we have

  * •

$s_{1}(t-\theta)\leq\ell_{1}\leq\ell\leq s_{1}(t+1)-1$,

  * •

$t_{2}:=t-\lfloor\ell/s_{1}\rfloor\leq
t_{1}:=t-\lfloor\ell_{1}/s_{1}\rfloor\leq\theta$,

  * •

$\Delta:=\Delta(G[U])\leq\delta_{2}(n-1)$,

  * •

$G[U]$ is $(t_{2}+1)\mathbb{B}$-free, and hence,

$\displaystyle|G[U]|\leq st_{2}\times\delta_{2}(n-1)+\mathrm{ex}(n-\ell-
st_{2},\mathbb{B})\leq\frac{\theta n}{2}+\mathrm{ex}(n,\mathbb{B})\leq\theta
n.$ (22)

We divide $U$ further by letting

$\displaystyle\delta_{3}:=\frac{1}{2(s_{2}+1)},\quad S:=\left\\{u\in
U\colon|N_{G}(u)\cap L|\leq(1-\delta_{3})|L|\right\\}\quad\text{and}\quad
W:=U\setminus S.$

In particular, since $G[S]\subset G[U]$ is $(t_{2}+1)\mathbb{B}$-free, it
follows from Lemma 2.13 that

$\displaystyle|G[S]|\leq st_{2}|S|+\mathrm{ex}\left(|S|,\mathbb{B}\right)\leq
s\theta|S|+\mathrm{ex}\left(|S|,\mathbb{B}\right).$ (23)

It follows from the definition of $S$ that

$\displaystyle|G[L,U]|\leq|W||L|+|S|\times(1-\delta_{3})|L|=\ell(n-\ell)-\delta_{3}\ell|S|.$
(24)

It follows from (22) and (24) that

$\displaystyle|G|=|G[L]|+|G[L,U]|+|G[U]|$
$\displaystyle\leq\binom{\ell}{2}+\ell(n-\ell)-\delta_{3}\ell|S|+\theta n.$

Combined with $|G|\geq
g_{2}(n,t,\mathbb{B})\geq\binom{n}{2}-\binom{n-s_{1}(t+1)+1}{2}\geq\binom{\ell}{2}+\ell(n-\ell)$,
we obtain

$\displaystyle|S|\leq\frac{\theta n}{s_{1}(t-\theta)}<\frac{n}{2}.$

which combined with Proposition 2.8 implies that

$\displaystyle\frac{\mathrm{ex}\left(n,\mathbb{B}\right)}{n}\geq\left(1-\frac{|S|}{n}\right)\frac{\mathrm{ex}\left(|S|,\mathbb{B}\right)}{|S|}\geq\frac{1}{2}\frac{\mathrm{ex}\left(|S|,\mathbb{B}\right)}{|S|}.$

Consequently, by (21), we obtain

$\displaystyle\frac{\delta_{3}\ell}{2}|S|-\mathrm{ex}\left(|S|,\mathbb{B}\right)\geq\left(\frac{\delta_{3}}{2}\times
s_{1}(t-\theta)-2\frac{\mathrm{ex}\left(n,\mathbb{B}\right)}{n}\right)|S|\geq
0.$ (25)

In addition,

$\displaystyle\frac{\delta_{3}\ell}{2}-s\theta-4s^{2}\theta\geq\frac{\delta_{3}}{2}\times
s_{1}(t-\theta)-s\theta-4s^{2}\theta>0.$ (26)

Let

$\displaystyle t_{3}:=s_{1}(t+1)-1-\ell,\quad S_{1}:=\left\\{v\in
S\colon|N_{G}(v)\cap W|\geq 4s^{2}\theta\right\\},\quad\text{and}\quad
x:=|S_{1}|.$

It follows from (23), (25), (26) and definition of $S_{1}$ that

$\displaystyle|G[S]|+|G[L,S]|+|G[S,W]|$ $\displaystyle\leq
s\theta|S|+\mathrm{ex}\left(|S|,\mathbb{B}\right)+(1-\delta_{3})\ell|S|+x\Delta+4s^{2}\theta|S|$
$\displaystyle\leq\ell|S|-\left(\delta_{3}\ell-s\theta-4s^{2}\theta\right)|S|+\mathrm{ex}\left(|S|,\mathbb{B}\right)+\frac{xn}{2}$
$\displaystyle\leq\ell|S|+\frac{xn}{2}-\frac{\delta_{3}\ell}{2}|S|+\mathrm{ex}\left(|S|,\mathbb{B}\right)\leq\ell|S|+\frac{xn}{2}.$

Consequently,

$\displaystyle|G[L,U]|+|G[S]|+|G[S,W]|$
$\displaystyle=|G[L,W]|+|G[S]|+|G[L,S]|+|G[L,W]|$
$\displaystyle\leq\ell|W|+\ell|S|+\frac{xn}{2}=\ell(n-\ell)+\frac{xn}{2}.$
(27)

For every set $T\subset U$ let $N_{T}:=\bigcap_{u\in T}N_{G}(u)\cap L$ denote
the set of common neighbors of $T$ in $L$. It follows from the definition of
$W$ that for every $(s_{2}+1)$-set $T\subset U$ we have

$\displaystyle|N_{T}|\geq\ell-\sum_{u\in T}\left(\ell-|N_{G}(u)\cap
L|\right)\geq\left(1-\delta_{3}(s_{2}+1)\right)\ell=\frac{\ell}{2}.$ (28)

$L$$W$$S$$S_{1}$ Figure 4: Supplementary diagram for Claim 5.9 when
$F=K_{2,3}$.

Let $\mathbb{B}^{\prime}:=\mathbb{B}[s_{2}+1]$ and note that every
$\mathbb{B}^{\prime}$-free is also $K_{1,s_{2}}$-free.

######  Claim 5.9.

We have $x\leq t_{3}$ and $G[W]$ is $(t_{3}-x+1)K_{1,s_{2}}$-free. Moreover,

$\displaystyle|G[W]|\leq\frac{t_{3}-x}{2}n+\frac{s_{2}}{2}n.$ (29)

###### Proof.

Suppose to the contrary that there exists a $(t_{3}+1)$-set
$\\{v_{1},\ldots,v_{t_{3}+1}\\}\subset S_{1}$ such that $|N_{G}(v_{i})\cap
W|\geq 4s^{2}\theta\geq 2s(t_{3}+1)$ for all $i\in[t_{3}+1]$. Choose an
$s_{2}$-set $X_{i}$ from $N_{G}(v_{i})\cap W$ for each $i\in[t_{2}+1]$ such
that $\\{X_{1},\ldots,X_{t_{3}+1}\\}$ are pairwise disjoint. For each $N_{i}$
choose an $(s_{1}-1)$-set $Y_{i}\subset N_{X_{i}}$ such that
$\\{Y_{1},\ldots,Y_{t_{3}+1}\\}$ are pairwise disjoint (the existence of such
sets are guaranteed by (28)). Notice that $B\subset K_{s_{1},s_{2}}\subset
G[\\{v_{i}\\}\cup X_{i}\cup Y_{i}]$ for $i\in[t_{3}+1]$. Let
$Z:=\bigcup_{i\in[t_{3}+1]}\left(\\{v_{i}\\}\cup X_{i}\cup Y_{i}\right)$ and
$G^{\prime}$ be the induced subgraph of $G$ on $V\setminus Z$. For every $v\in
L_{1}\setminus Z$ we have

$\displaystyle d_{G^{\prime}}(v)\geq
d_{G}(v)-|Z|\geq(1-\delta_{1})(n-1)-s(t_{3}+1)\geq(1-2\delta_{1})(n-1),$

and for every $u\in L_{2}\setminus Z$ we have

$\displaystyle d_{G^{\prime}}(v)\geq
d_{G}(v)-|Z|\geq\delta_{2}(n-1)-s(t_{3}+1)\geq\frac{\delta_{2}}{2}(n-1).$

Since, in addition, $\ell\leq s_{1}(t+1)\leq 2\varepsilon
s_{1}n\leq\frac{\delta_{2}(n-\ell-|Z|)/2}{8(s-s_{1})}$, it follows from Lemma
5.2 that $G^{\prime}$ contains at least

$\displaystyle\left\lfloor\frac{\ell-(s_{1}-1)t_{3}}{s_{1}}\right\rfloor=\ell-(s_{1}-1)(t+1)$

pairwise vertex-disjoint copies of $\mathbb{B}$. This implies that $G$
contains

$\displaystyle
t_{3}+1+\ell-(s_{1}-1)(t+1)=s_{1}(t+1)-1-\ell+1+\ell-(s_{1}-1)(t+1)=t+1$

pairwise vertex-disjoint copies of $\mathbb{B}$, a contradiction. This proves
that $x\leq t_{3}$. The proof for the $(t_{3}-x+1)K_{1,s_{2}}$-freeness of
$G[W]$ is similar (see Figure 4), so we omit the details.

Recall that $\Delta(G[W])\leq\Delta(G[U])\leq\delta_{3}n$, so it follows from
Lemma 2.13 and $(t_{3}-x+1)K_{1,s_{2}}$-freeness of $G[W]$ that

$\displaystyle|G[W]|\leq(t_{3}-x)(s_{2}+1)\times\delta_{3}n+\mathrm{ex}(n,K_{1,s_{2}})\leq\frac{t_{3}-x}{2}n+\frac{s_{2}}{2}n,$

where in the last inequality, we used the trivial bound
$\mathrm{ex}(n,K_{1,s_{2}})\leq\frac{s_{2}}{2}n$.

It follows from (23), (5.3), and (29) that

$\displaystyle|G|$ $\displaystyle=|G[L]|+|G[L,U]|+|G[S]|+|G[S,W]|+|G[W]|$
$\displaystyle\leq\binom{\ell}{2}-|\overline{G[L]}|+\ell(n-\ell)+\frac{xn}{2}+\frac{t_{3}-x}{2}n+\frac{s_{2}}{2}n$
$\displaystyle\leq\binom{n}{2}-\binom{n-s_{1}(t+1)+1}{2}-t_{3}\times\frac{2n}{3}+\frac{t_{3}}{2}n+\frac{s_{2}}{2}n-|\overline{G[L]}|$
$\displaystyle\leq\binom{n}{2}-\binom{n-s_{1}(t+1)+1}{2}+\frac{s_{2}}{2}n-\frac{t_{3}n}{6}-|\overline{G[L]}|.$
(30)

Since $|G|\geq\binom{n}{2}-\binom{n-s_{1}(t+1)-1}{2}$, it follows from the
inequality above that

$\displaystyle t_{3}\leq 3s_{2},$ (31)

and

$\displaystyle|\overline{G[L]}|\leq\frac{s_{2}}{2}n,$ (32)

######  Claim 5.10.

The following statements hold.

  1. (i)

Every set $L^{\prime}\subset L$ of size at least $\sqrt{2s_{1}sn}$ contains a
copy of $K_{s_{1}-1}$,

  2. (ii)

for every $T\in\binom{W}{s_{2}+1}$, the induced graph $G[N_{T}]$ contains
$st_{3}$ pairwise vertex-disjoint copies of $K_{s_{1}-1}$, and

  3. (iii)

$G[W]$ is $(t_{3}-x+1)\mathbb{B}^{\prime}$-free.

###### Proof.

Suppose to the contrary that there exists a set $L^{\prime}\subset L$ of size
$\sqrt{2s_{1}sn}$ such that $G[L^{\prime}]$ is $K_{s_{1}-1}$-free. Then it
follows from Turán’s theorem that
$|G[L^{\prime}]|\leq\left(\frac{1}{2}-\frac{1}{2(s_{1}-1)}\right)|L^{\prime}|^{2}$,
and consequently,

$\displaystyle|\overline{G[L]}|\geq|\overline{G[L^{\prime}]}|\geq\binom{|L^{\prime}|}{2}-\left(\frac{1}{2}-\frac{1}{2(s_{1}-1)}\right)|L^{\prime}|^{2}\geq\frac{|L^{\prime}|^{2}}{4(s_{1}-1)}>\frac{s_{2}n}{2},$

contradicting (32). This proves (i).

Let $T\in\binom{W}{s_{2}+1}$. By (28), (31), and the assumption on $t$, we
have

$\displaystyle|N_{T}|\geq\frac{\ell}{2}\geq\frac{s_{1}(t-\theta)}{2}\geq\frac{t}{2}\geq\frac{\sqrt{32s_{1}sn}}{2}\geq\sqrt{2s_{1}sn}+(s_{1}-1)st_{3}.$

It follows from (i) and a simple greedy argument that $G[N_{T}]$ contains
$st_{3}$ pairwise vertex-disjoint copies of $K_{s_{1}-1}$.

Notice that if $T\in\binom{W}{s_{2}+1}$ contains a copy of some element in
$\mathbb{B}^{\prime}$, then by (i), there are disjoint $(s_{1}-1)$-sets
$T^{\prime}_{1},\ldots,T^{\prime}_{st_{3}}$ in $N_{T}$ such that $T\cup
T^{\prime}_{i}$ contains a copy of $\mathbb{B}$ for all $i\in[st_{3}]$. Using
this fact and a similar argument as in the proof of Claim 5.9 we obtain (iii).

Similar to (5.3), it follows from (5.3), Claim 5.10 (iii), Proposition 5.8,
and Fact 2.14 that

$\displaystyle|G|$
$\displaystyle\leq\binom{\ell}{2}+\ell(n-\ell)+\frac{xn}{2}+\mathrm{ex}\left(n-\ell-x,(t_{3}-x+1)\mathbb{B}^{\prime}\right)$
$\displaystyle\leq\binom{n}{2}-\binom{n-(\ell+x)}{2}+\mathrm{ex}\left(n-\ell-x,(t_{3}-x+1)\mathbb{B}^{\prime}\right)$
$\displaystyle\leq\binom{n}{2}-\binom{n-(\ell+x+t_{3}-x)}{2}+\mathrm{ex}\left(n-\ell-x-(t_{3}-x),\mathbb{B}^{\prime}\right)$
$\displaystyle=\binom{n}{2}-\binom{n-s_{1}(t+1)+1}{2}+\mathrm{ex}\left(n-s_{1}(t+1)+1,\mathbb{B}^{\prime}\right),$

completing the proof of Theorem 1.12.

##  6 Concluding remarks

Fix an $r$-graph $F$ on $m$ vertices. We say a collection
$\left\\{\mathcal{H}_{1},\ldots,\mathcal{H}_{t+1}\right\\}$ of $r$-graphs on
the same vertex set $V$ has a rainbow $F$-matching if there exists a
collection $\left\\{S_{i}\colon i\in[t+1]\right\\}$ of pairwise disjoint
$m$-subsets of $V$ such that $F\subset\mathcal{H}_{i}[S_{i}]$ for all
$i\in[t+1]$. Recently, there has been considerable interest in extending some
classical results to a rainbow version. See e.g. [1, 26, 32, 37, 47, 48] for
some recent progress on the rainbow version of the Erdős Matching Conjecture.
Rainbow versions of theorems in the present work can be obtained without too
change to the corresponding proof. We omit the details and refer the reader to
[31, Theorem 1.8] for more information.

Given (not necessary different) $r$-graphs $F_{1},\ldots,F_{t+1}$, let
$\mathrm{ex}\left(n,\bigsqcup_{i\in[t+1]}F_{i}\right)$ denote the maximum
number of edges in an $n$-vertex $r$-graph without pairwise vertex-disjoint
copies of $F_{1},\ldots,F_{t}$, and $F_{t+1}$. One could also use proofs in
the present work (with minor changes) to obtain some upper bounds for
$\mathrm{ex}\left(n,\bigsqcup_{i\in[t+1]}F_{i}\right)$. We refer the reader to
[31, Theorem 6.1] for more information.

Determining $\mathrm{ex}\left(n,(t+1)F\right)$ for all feasible values of $t$
seems to be a challenging problem for general $r$-graphs $F$. We tend to
believe that for $F=K_{s,\ldots,s}^{r}$, $s\geq 2$, the asymptotic behavior of
$\mathrm{ex}\left(n,(t+1)F\right)$ is governed by the three constructions
$\mathcal{G}_{1}(n,t,F)$, $\mathcal{G}_{2}(n,t,F)$, and
$\mathcal{G}_{3}(n,t,F)$ defined in the first section. However, for general
$r$-graphs $F$, there might be other extremal constructions. Indeed, recall
that for $i\in[r-1]$, a set $S\subset V(F)$ is $i$-independent in $F$ if every
edge in $F$ contains at most $i$ vertices in $S$. Let the $i$-independent
vertex covering number $\tau_{i}(F)$ (if it exists) of $F$ be

$\displaystyle\tau_{i}(F):=\min\left\\{|S|\colon S\subset V(\mathcal{H}),\
\text{$S$ is $i$-independent, and }|S\cap e|\neq\emptyset\text{ for all
}e\in\mathcal{H}\right\\}.$

Observe that for $1\leq i<j\leq r-1$, if $\tau_{i}(F)$ and $\tau_{j}(F)$
exist, then $\tau\leq\tau_{j}(F)\leq\tau_{i}(F)$. For $i\in[r]$ let

$\displaystyle\mathcal{B}\left(n,m,r,i\right):=\left\\{e\in\binom{[n]}{r}\colon
1\leq|e\cap[m]|\leq i\right\\}.$

It is easy to see that $\mathcal{B}\left(n,(t+1)\tau_{i}(F)-1,r,i\right)$ is
$(t+1)F$-free. Therefore, we have the following lower bound.

######  Fact 6.1.

Let $F$ be an $r$-graph and suppose that $\tau_{i}(F)$ exists for some
$i\in[r-1]$. Then

$\displaystyle\mathrm{ex}\left(n,(t+1)F\right)\geq\sum_{j\in[i]}\binom{(t+1)\tau_{i}(F)-1}{j}\binom{n-(t+1)\tau_{i}(F)+1}{r-j}.$

We hope the following natural problem could inspire further research on this
topic.

######  Problem 6.2.

Determine $\mathrm{ex}\left(n,(t+1)C_{4}\right)$ for large $n$ and for all
$t\leq n/4$.

We would like to remind the reader that constructions in
$\mathcal{G}_{3}(n,t,C_{4})$ are not maximal. Indeed, for a member
$G\in\mathcal{G}_{3}(n,t,C_{4})$, let $V_{1}\cup V_{2}$ be the partition of
$V(G)$ such that $G[V_{1}]\cong K_{2t+1}$ and $G[V_{2}]$ is maximum
$C_{4}$-free. Let $\hat{G}$ be a graph obtained from $G$ by adding a matching
$M$ crossing $V_{1}$ and $V_{2}$ such that the set $V(M)\cap V_{2}$ is an
independent set in $G[V_{2}]$. It is easy to see that $\hat{G}$ is still
$(t+1)C_{4}$-free. The orthogonal polarity graphs show that the size of $M$
can have order $(n-2t-1)^{3/4}$ for some special values of $n-2t-1$ (see e.g.
[5, 11, 12, 21, 22, 54]). This construction shows that determining the exact
value of $\mathrm{ex}\left(n,(t+1)C_{4}\right)$ when $t$ is close to $n/4$ is
probably challenging.

######  Problem 6.3.

Let $n\geq\alpha\geq 1$ be integers. What is the maximum number of edges in an
$n$-vertex $C_{4}$-free graph with independence number at least $\alpha$?

It would be interesting to know whether the lower bound $\sqrt{32s_{2}sn}$ for
$t$ in Theorem 1.12 is necessary in general. We will show that this lower
bound is not necessary for a special class of bipartite graphs including even
cycles in [29].

######  Problem 6.4.

Characterize the family of bipartite graphs $B_{s_{1},s_{2}}$ for which the
lower bound $\sqrt{32s_{2}(s_{1}+s_{2})n}$ for $t$ in Theorem 1.12 can be
omitted.

In order to refine the bound presented in Theorem 1.11, it appears essential
to address the following problem first.

######  Problem 6.5.

Let $n\geq r\geq 3$, $s_{r}\geq\cdots\geq s_{1}\geq 2$, and
$m\leq\binom{n-1}{r-1}$ be integers. What is the maximum number of edges in an
$n$-vertex $K_{s_{1},\ldots,s_{r}}^{r}$-free $r$-graph $\mathcal{H}$ with an
$(s_{1}-1)$-set $L\subset V(\mathcal{H})$ such that
$d_{\mathcal{H}}(v)\geq\binom{n-1}{r-1}-m$ for all $v\in L$?

Recall that the shadow of an $r$-graph $\mathcal{H}$ is

$\displaystyle\partial\mathcal{H}:=\left\\{A\in\binom{V(\mathcal{H})}{r-1}\colon
A\subset E\text{ for some }E\in\mathcal{H}\right\\}.$

The classical Kruskal-Katone Theorem [33, 40] determines the maximum size of
an $r$-graph with bounded shadow size. It seems that Problem 6.5 is related to
the following Kruskal-Katone type problem.

######  Problem 6.6.

Let $r\geq 3$ and $F$ be a degenerate $r$-graph. Let $m\leq\binom{n}{r-1}$ be
an integer. What is the maximum number of edges in an $n$-vertex $F$-free
$r$-graph $\mathcal{H}$ with $|\partial\mathcal{H}|\leq m$?

An analogous problem for nondegenerate $r$-graphs was studied systematically
in [44] (see also [42, 46]).

Theorem 1.7 motivates the following analogous problem to [31, Problem 6.4].

######  Problem 6.7.

Let $r\geq 2$ be an integers and $F$ be a degenerate $r$-graph. What is the
largest value of $s(F)$ such that for sufficiently large $n$,

$\displaystyle\mathrm{ex}(n,(t+1)F)=g_{1}(n,t,F)\quad\text{holds for all
}t\leq\left(s(F)-o(1)\right)\frac{\mathrm{ex}(n,F)}{\binom{n-1}{r-1}}?$

Theorem 1.7 also motivates the following question for nondegenerate
hypergraphs.

######  Problem 6.8.

Let $r\geq 4$ be an integer. Find sufficient and/or necessary conditions for a
nondegenerate $r$-graph $F$ to satisfy $\pi(F)<\frac{1}{v(F)}$.

By Erdős’ theorem [8], every nondegenerate $r$-graph $F$ satisfies the lower
bound $\pi(F)\geq\frac{r!}{r^{r}}$. This, together with straightforward
calculations and constructions of $K_{4}^{3-}$-free $3$-graphs (see e.g.
[53]), shows that there is no nondegenerate $r$-graph $F$ with
$\pi(F)<\frac{1}{v(F)}$ when $r\leq 3$.

## Acknowledgement

XL would like to thank Jie Han for helpful discussions on related topics and
for reminding him about the references [25, 28].

## References

  * [1] R. Aharoni and D. Howard.  Size conditions for the existence of rainbow matchings.  http://math.colgate.edu/~dmhoward/rsc.pdf, accessed on 2023-02-02.
  * [2] P. Allen, J. Böttcher, J. Hladký, and D. Piguet.  A density Corrádi-Hajnal theorem.  Canad. J. Math., 67(4):721–758, 2015.
  * [3] N. Alon and R. Yuster.  $H$-factors in dense graphs.  J. Combin. Theory Ser. B, 66(2):269–282, 1996.
  * [4] B. Bollobás.  Three-graphs without two triples whose symmetric difference is contained in a third.  Discrete Math., 8:21–24, 1974.
  * [5] W. G. Brown.  On graphs that do not contain a Thomsen graph.  Canad. Math. Bull., 9:281–285, 1966.
  * [6] K. Corradi and A. Hajnal.  On the maximal number of independent circuits in a graph.  Acta Math. Acad. Sci. Hungar., 14:423–439, 1963.
  * [7] P. Erdős.  Über ein Extremalproblem in der Graphentheorie.  Arch. Math. (Basel), 13:222–227, 1962.
  * [8] P. Erdős.  On extremal problems of graphs and generalized graphs.  Israel J. Math., 2:183–190, 1964.
  * [9] P. Erdős.  A problem on independent $r$-tuples.  Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 8:93–95, 1965\.
  * [10] P. Erdős and T. Gallai.  On maximal paths and circuits of graphs.  Acta Math. Acad. Sci. Hungar., 10:337–356 (unbound insert), 1959\.
  * [11] P. Erdős and A. Rényi.  On a problem in the theory of graphs.  Magyar Tud. Akad. Mat. Kutató Int. Közl., 7:623–641, 1962\.
  * [12] P. Erdős, A. Rényi, and V. T. Sós.  On a problem of graph theory.  Studia Sci. Math. Hungar., 1:215–235, 1966.
  * [13] P. Erdős and M. Simonovits.  A limit theorem in graph theory.  Studia Sci. Math. Hungar., 1:51–57, 1966.
  * [14] P. Erdös and A. H. Stone.  On the structure of linear graphs.  Bull. Amer. Math. Soc., 52:1087–1091, 1946.
  * [15] P. Frankl.  Improved bounds for Erdős’ matching conjecture.  J. Combin. Theory Ser. A, 120(5):1068–1072, 2013.
  * [16] P. Frankl.  On the maximum number of edges in a hypergraph with given matching number.  Discrete Appl. Math., 216(part 3):562–581, 2017.
  * [17] P. Frankl.  Proof of the Erdős matching conjecture in a new range.  Israel J. Math., 222(1):421–430, 2017.
  * [18] P. Frankl and Z. Füredi.  A new generalization of the Erdős-Ko-Rado theorem.  Combinatorica, 3(3-4):341–349, 1983.
  * [19] P. Frankl and Z. Füredi.  An exact result for $3$-graphs.  Discrete Math., 50(2-3):323–328, 1984.
  * [20] P. Frankl and Z. Füredi.  Extremal problems whose solutions are the blowups of the small Witt-designs.  J. Combin. Theory Ser. A, 52(1):129–147, 1989.
  * [21] Z. Füredi.  Graphs without quadrilaterals.  J. Combin. Theory Ser. B, 34(2):187–190, 1983.
  * [22] Z. Füredi.  Quadrilateral-free graphs with maximum number of edges.  preprint, 1994.
  * [23] Z. Füredi.  On the number of edges of quadrilateral-free graphs.  J. Combin. Theory Ser. B, 68(1):1–6, 1996.
  * [24] Z. Füredi and M. Simonovits.  The history of degenerate (bipartite) extremal graph problems.  In Erdös centennial, volume 25 of Bolyai Soc. Math. Stud., pages 169–264. János Bolyai Math. Soc., Budapest, 2013.
  * [25] L. Gan, J. Han, L. Sun, and G. Wang.  Large ${Y}_{k,b}$-tilings and Hamilton $\ell$-cycles in $k$-uniform hypergraphs.  arXiv preprint arXiv:2109.00722, 2021.
  * [26] J. Gao, H. Lu, J. Ma, and X. Yu.  On the rainbow matching conjecture for 3-uniform hypergraphs.  Sci. China Math., 65(11):2423–2440, 2022.
  * [27] A. Hajnal and E. Szemerédi.  Proof of a conjecture of P. Erdős.  In Combinatorial theory and its applications, I-III (Proc. Colloq., Balatonfüred, 1969), pages 601–623. North-Holland, Amsterdam, 1970.
  * [28] J. Han, L. Sun, and G. Wang.  Large ${Y}_{3,2}$-tilings in $3$-uniform hypergraphs.  arXiv preprint arXiv:2304.02432, 2023.
  * [29] J. Hou, C. Hu, H. Li, X. Liu, C. Yang, and Y. Zhang.  Many vertex-disjoint even cycles of fixed length in a graph.  In preparation.
  * [30] J. Hou, C. Hu, H. Li, X. Liu, C. Yang, and Y. Zhang.  On the boundedness of some degenerate hypergraphs.  In preparation.
  * [31] J. Hou, H. Li, X. Liu, L.-T. Yuan, and Y. Zhang.  A step towards a general density Corrádi–Hajnal theorem.  arXiv preprint arXiv:2302.09849, 2023.
  * [32] H. Huang, P.-S. Loh, and B. Sudakov.  The size of a hypergraph and its matching number.  Combin. Probab. Comput., 21(3):442–450, 2012.
  * [33] G. Katona.  A theorem of finite sets.  In Theory of graphs (Proc. Colloq., Tihany, 1966), pages 187–207, 1968.
  * [34] G. Katona, T. Nemetz, and M. Simonovits.  On a problem of Turán in the theory of graphs.  Mat. Lapok, 15:228–238, 1964.
  * [35] P. Keevash.  Hypergraph Turán problems.  In Surveys in combinatorics 2011, volume 392 of London Math. Soc. Lecture Note Ser., pages 83–139. Cambridge Univ. Press, Cambridge, 2011.
  * [36] P. Keevash and D. Mubayi.  Stability theorems for cancellative hypergraphs.  J. Combin. Theory Ser. B, 92(1):163–175, 2004.
  * [37] S. Kiselev and A. Kupavskii.  Rainbow matchings in $k$-partite hypergraphs.  Bull. Lond. Math. Soc., 53(2):360–369, 2021.
  * [38] J. Komlós, G. N. Sárközy, and E. Szemerédi.  Proof of the Alon-Yuster conjecture.  volume 235, pages 255–269. 2001.  Combinatorics (Prague, 1998).
  * [39] T. Kövari, V. T. Sós, and P. Turán.  On a problem of K. Zarankiewicz.  Colloq. Math., 3:50–57, 1954.
  * [40] J. B. Kruskal.  The number of simplices in a complex.  In Mathematical optimization techniques, pages 251–278. Univ. of California Press, Berkeley, Calif., 1963.
  * [41] D. Kühn and D. Osthus.  Embedding large subgraphs into dense graphs.  In Surveys in combinatorics 2009, volume 365 of London Math. Soc. Lecture Note Ser., pages 137–167. Cambridge Univ. Press, Cambridge, 2009.
  * [42] X. Liu.  Cancellative hypergraphs and Steiner triple systems.  arXiv preprint arXiv:1912.11917, 2019.
  * [43] X. Liu.  New short proofs to some stability theorems.  European J. Combin., 96:Paper No. 103350, 8, 2021.
  * [44] X. Liu and D. Mubayi.  The feasible region of hypergraphs.  J. Combin. Theory Ser. B, 148:23–59, 2021.
  * [45] X. Liu, D. Mubayi, and C. Reiher.  A unified approach to hypergraph stability.  J. Combin. Theory Ser. B, 158(part 2):36–62, 2023.
  * [46] X. Liu and S. Mukherjee.  Stability theorems for some Kruskal-Katona type results.  European J. Combin., 110:Paper No. 103666, 20, 2023.
  * [47] H. Lu, Y. Wang, and X. Yu.  Rainbow perfect matchings for 4-uniform hypergraphs.  SIAM J. Discrete Math., 36(3):1645–1662, 2022.
  * [48] H. Lu, Y. Wang, and X. Yu.  A better bound on the size of rainbow matchings.  J. Combin. Theory Ser. A, 195:Paper No. 105700, 2023.
  * [49] L. Lu and L. Székely.  Using Lovász local lemma in the space of random injections.  Electron. J. Combin., 14(1):Research Paper 63, 13, 2007.
  * [50] W. Mantel.  Vraagstuk XXVIII.  Wiskundige Opgaven, 10(2):60–61, 1907.
  * [51] J. W. Moon.  On independent complete subgraphs in a graph.  Canadian J. Math., 20:95–102, 1968.
  * [52] D. Mubayi.  On hypergraphs with every four points spanning at most two triples.  Electron. J. Combin., 10:Note 10, 4, 2003.
  * [53] D. Mubayi, O. Pikhurko, and B. Sudakov.  Hypergraph Turán problem: some open questions.  In AIM workshop problem lists, manuscript, page 166, 2011.
  * [54] D. Mubayi and J. Williford.  On the independence number of the Erdős-Rényi and projective norm graphs and a related hypergraph.  J. Graph Theory, 56(2):113–127, 2007.
  * [55] S. Norin and L. Yepremyan.  Turán number of generalized triangles.  J. Combin. Theory Ser. A, 146:312–343, 2017.
  * [56] O. Pikhurko.  An exact Turán result for the generalized triangle.  Combinatorica, 28(2):187–208, 2008.
  * [57] J. B. Shearer.  A new construction for cancellative families of sets.  Electron. J. Combin., 3(1):Research Paper 15, approx. 3, 1996.
  * [58] A. F. Sidorenko.  On the maximal number of edges in a homogeneous hypergraph that does not contain prohibited subgraphs.  Mat. Zametki, 41(3):433–455, 459, 1987.
  * [59] M. Simonovits.  A method for solving extremal problems in graph theory, stability problems.  In Theory of Graphs (Proc. Colloq., Tihany, 1966), pages 279–319. Academic Press, New York, 1968.

##  Appendix A Proof of Theorem 2.9

######  Theorem A.1 (Erdős [8]).

Suppose that $n\geq r\geq 3$ and $s_{r}\geq\cdots\geq s_{1}\geq 1$ are
integers. Then

$\displaystyle\mathrm{ex}(n,K_{s_{1},\ldots,s_{r}}^{r})\leq\frac{(s_{2}+\ldots+s_{r}-r+1)^{\frac{1}{s_{1}}}}{r}n^{r-\frac{1}{s_{1}\cdots
s_{r-1}}}+\frac{s_{1}-1}{r}\binom{n}{r-1}.$

###### Proof.

We prove this theorem by induction on $r$. The base case $r=2$ is the
Kővári–Sós–Turán Theorem. So we may assume that $r\geq 3$. Let $\mathcal{H}$
be a $K_{s_{1},\cdots,s_{r}}^{r}$-free $r$-graph on $n$ vertices. Let $X$
denote the number of copies of $K_{s_{1},1,\ldots,1}^{r}$ in $\mathcal{H}$. We
use a standard double-counting argument to bound the number of edges in
$\mathcal{H}$. First, it follows from Jensen’s inequality that

$\displaystyle X$
$\displaystyle=\sum_{T\in\binom{n}{r-1}}\binom{|N(T)|}{s_{1}}\geq\binom{n}{r-1}\binom{r|\mathcal{H}|/\binom{n}{r-1}}{s_{1}}$
$\displaystyle\geq\frac{1}{s_{1}!}\binom{n}{r-1}\left(\frac{r|\mathcal{H}|}{\binom{n}{r-1}}-(s_{1}-1)\right)^{s_{1}}.$
(33)

From the other direction, notice that for every $S\in\binom{n}{s_{1}}$, the
common link $L(S)$ is $K_{s_{2},\ldots,s_{r}}^{r-1}$-free. It follows from the
induction hypothesis that

$\displaystyle|L_{\mathcal{H}}(S)|$
$\displaystyle\leq\frac{(s_{3}+\cdots+s_{r}-r+2)^{\frac{1}{s_{2}}}}{r-1}n^{r-1-\frac{1}{s_{2}\cdots
s_{r-1}}}+\frac{s_{2}-1}{r-1}\binom{n}{r-2}$
$\displaystyle\leq(s_{2}+\cdots+s_{r}-r+1)n^{r-1-\frac{1}{s_{2}\cdots
s_{r-1}}}.$ (34)

It follows that

$\displaystyle
X=\sum_{S\in\binom{n}{s_{1}}}|L(S)|\leq(s_{2}+\cdots+s_{r}-r+1)n^{r-1-\frac{1}{s_{2}\cdots
s_{r-1}}}\binom{n}{s_{1}}.$ (35)

Combining (A) and (35), we obtain

$\displaystyle|\mathcal{H}|$
$\displaystyle\leq\frac{1}{r}\left((s_{2}+\cdots+s_{r}-r+1)n^{r-1-\frac{1}{s_{2}\cdots
s_{r-1}}}\frac{n^{s_{1}}}{\binom{n}{r-1}}\right)^{\frac{1}{s_{1}}}\binom{n}{r-1}+\frac{s_{1}-1}{r}\binom{n}{r-1}$
$\displaystyle\leq\frac{\left(s_{2}+\cdots+s_{r}-r+1\right)^{\frac{1}{s_{1}}}}{r}n^{r-\frac{1}{s_{1}\cdots
s_{r-1}}}+\frac{s_{1}-1}{r}\binom{n}{r-1},$

completing the induction.

##  Appendix B Proof of Proposition 2.11

######  Proposition B.1.

Suppose that $r\geq 3$, $s_{r}\geq\cdots\geq s_{1}\geq 1$, and $m,n\geq 1$ are
integers. Then

$\displaystyle
Z(m,n,s_{1},\ldots,s_{r})\leq\frac{\left(s_{2}+\cdots+s_{r}-r+1\right)^{\frac{1}{s_{1}}}}{r}mn^{r-1-\frac{1}{s_{1}\cdots
s_{r-1}}}+\frac{s_{1}-1}{r}\binom{n}{r-1}.$

###### Proof.

Let $\mathcal{H}$ be an $m$ by $n$ semibipartite $r$-graph on $V_{1}$ and
$V_{2}$ with $|V_{1}|=m$ and $|V_{2}|=n$. Suppose that $\mathcal{H}$ does not
contain a copy of $K_{s_{1},\ldots,s_{r}}=K[W_{1},\ldots,W_{r}]$ with $W_{1}$
contained in $V_{1}$ and $W_{2},\ldots,W_{r}$ contained in $V_{2}$. We use a
standard double-counting argument to bound the size of $\mathcal{H}$. Let

$\displaystyle
X:=\sum_{T\in\binom{V_{2}}{r-1}}\binom{|N(T)|}{s_{1}}=\sum_{S\in\binom{V_{1}}{s_{1}}}|L(S)|.$

First, it follows from Jensen’s inequality that

$\displaystyle X$
$\displaystyle\geq\binom{n}{r-1}\binom{\sum_{T\in\binom{V_{2}}{r-1}}|N(T)|/\binom{n}{r-1}}{s_{1}}$
$\displaystyle=\binom{n}{r-1}\binom{r|\mathcal{H}|/\binom{n}{r-1}}{s_{1}}\geq\frac{1}{s_{1}!}\binom{n}{r-1}\left(\frac{r|\mathcal{H}|}{\binom{n}{r-1}}-(s_{1}-1)\right)^{s_{1}}.$
(36)

From the other direction, notice that for every $S\in\binom{V_{1}}{s_{1}}$,
the common link $L_{\mathcal{H}}(S)\subset\binom{V_{2}}{r-1}$ is
$K_{s_{2},\ldots,s_{r}}^{r-1}$-free. So it follows from (A) that

$\displaystyle|L_{\mathcal{H}}(S)|\leq(s_{2}+\cdots+s_{r}-r+1)n^{r-1-\frac{1}{s_{2}\cdots
s_{r-1}}}.$

Consequently,

$\displaystyle X$
$\displaystyle\leq\binom{m}{s_{1}}\times(s_{2}+\cdots+s_{r}-r+1)n^{r-1-\frac{1}{s_{2}\cdots
s_{r-1}}}$
$\displaystyle\leq\frac{1}{s_{1}!}(s_{2}+\cdots+s_{r}-r+1)n^{r-1-\frac{1}{s_{2}\cdots
s_{r-1}}}m^{s_{1}}.$ (37)

Combining (B) and (B) we obtain

$\displaystyle|\mathcal{H}|$
$\displaystyle\leq\frac{1}{r}\left(\frac{(s_{2}+\cdots+s_{r}-r+1)m^{s_{1}}n^{r-1-\frac{1}{s_{2}\cdots
s_{r-1}}}}{\binom{n}{r-1}}\right)^{\frac{1}{s_{1}}}\binom{n}{r-1}+\frac{s_{1}-1}{r}\binom{n}{r-1}$
$\displaystyle\leq\frac{(s_{2}+\cdots+s_{r}-r+1)^{\frac{1}{s_{1}}}}{r}mn^{r-1-\frac{1}{s_{1}\cdots
s_{r-1}}}+\frac{s_{1}-1}{r}\binom{n}{r-1},$

completing the proof of Proposition 2.11.