# Non-degenerate Hypergraphs with Exponentially
Many Extremal Constructions

József Balogh Department of Mathematics, University of Illinois at Urbana-
Champaign, Urbana, Illinois 61801, USA. E-mail<EMAIL_ADDRESS>Research
is partially supported by NSF Grant DMS-1764123 and RTG DMS-1937241, Arnold O.
Beckman Research Award (UIUC Campus Research Board RB 22000), the Langan
Scholar Fund (UIUC), and the Simons Fellowship. Felix Christian Clemen
Department of Mathematics, Karlsruhe Institute of Technology, 76131 Karlsruhe,
Germany, Email<EMAIL_ADDRESS>Research was partially performed while
the second author was at the University of Illinois at Urbana-Champaign.
Haoran Luo Department of Mathematics, University of Illinois at Urbana-
Champaign, Urbana, Illinois 61801, USA. E-mail<EMAIL_ADDRESS>Research is partially supported by UIUC Campus Research Board RB 22000.

###### Abstract

For every integer $t\geqslant 0$, denote by $F_{5}^{t}$ the hypergraph on
vertex set $\\{1,2,\ldots,5+t\\}$ with hyperedges
$\\{123,124\\}\cup\\{34k:5\leqslant k\leqslant 5+t\\}$. We determine
$\mathrm{ex}(n,F_{5}^{t})$ for every $t\geqslant 0$ and sufficiently large $n$
and characterize the extremal $F_{5}^{t}$-free hypergraphs. In particular, if
$n$ satisfies certain divisibility conditions, then the extremal
$F_{5}^{t}$-free hypergraphs are exactly the balanced complete tripartite
hypergraphs with additional hyperedges inside each of the three parts
$(V_{1},V_{2},V_{3})$ in the partition; each part $V_{i}$ spans a
$(|V_{i}|,3,2,t)$-design. This generalizes earlier work of Frankl and Füredi
on the Turán number of $F_{5}:=F_{5}^{0}$.

Our results extend a theory of Erdős and Simonovits about the extremal
constructions for certain fixed graphs. In particular, the hypergraphs
$F_{5}^{6t}$, for $t\geqslant 1$, are the first examples of hypergraphs with
exponentially many extremal constructions and positive Turán density.

##  1 Introduction

For a family of $r$-uniform hypergraphs (_$r$ -graphs_) $\mathcal{F}$, a
hypergraph $H$ is _$\mathcal{F}$ -free_ if $H$ contains no copy of any
$F\in\mathcal{F}$ as a subhypergraph. The _Turán number_
$\mathrm{ex}(n,\mathcal{F})$ is the maximum possible number of hyperedges in
an $n$-vertex $\mathcal{F}$-free $r$-graph. Let
$\pi(\mathcal{F})\coloneqq\lim_{n\to\infty}\mathrm{ex}(n,\mathcal{F})/\binom{n}{r}$
be the _Turán density_ of $\mathcal{F}$. A family $\mathcal{F}$ is _non-
degenerate_ if $\pi(\mathcal{F})>0$. When $\mathcal{F}=\\{F\\}$, we will
simply use $F$-free, $\mathrm{ex}(n,F)$, and $\pi(F)$, respectively. We say an
$n$-vertex $\mathcal{F}$-free $r$-graph $H$ is _extremal_ (or an _extremal
construction_) for $\mathcal{F}$ if $H$ has $\mathrm{ex}(n,\mathcal{F})$
hyperedges. Determining Turán numbers and the corresponding extremal
constructions is one of the central problems in Extremal Combinatorics and has
received extensive attention.

This problem is reasonably well-understood for graphs (the case where $r=2$).
The Erdős-Stone theorem [7], as pointed out by Erdős and Simonovits [5],
determines the Turán density of all graphs. However, for hypergraphs, the
Turán problem is notoriously difficult, and there are only very few exact
results. The _tetrahedron_ , denoted by $K_{4}^{3}$, is the complete $3$-graph
on four vertices. It is a famous problem of Turán [23] to determine the Turán
density of the tetrahedron. There are exponentially many conjectured extremal
constructions by Brown [2], Kostochka [17], Fon-der-Flaass [8], and Frohmader
[10], see also [20] by Razborov.

In this paper, we give the first examples of hypergraphs which share this
(conjectured) property with the tetrahedron in the following sense: each of
them has exponentially many non-isomorphic extremal constructions and positive
Turán density. We note that our extremal constructions are close (i.e.
$O(n^{2})$) to each other in edit-distance, while for the tetrahedron, the
(conjectured) extremal constructions differ more from each other (some of them
have edit-distance $\Omega(n^{3})$). Following Liu, Mubayi [18] and Liu,
Mubayi, Reiher [19], Hou, Li, Liu, Mubayi, and Zhang [13] recently constructed
finite families of $3$-graphs such that each family has $\Omega(n)$ non-
isomorphic extremal constructions far (i.e. $\Omega(n^{3})$) from each other
in edit-distance, which is a new phenomenon compared to graphs. It remains
open to find a single hypergraph with $\omega(1)$ extremal hypergraphs far
from each other in edit-distance. We reiterate that the tetrahedron is
conjectured to be such a hypergraph.

A classical theorem in hypergraph Turán theory is the following result of
Bollobás [1]. The _generalized triangle_ , denoted by $F_{5}$, is the
$3$-graph on vertex set $\\{1,2,3,4,5\\}$ with hyperedges $\\{123,124,345\\}$,
see Figure 2. Let $K_{4}^{-}$ be the $3$-graph on vertex set $\\{1,2,3,4\\}$
with hyperedges $\\{123,124,134\\}$, and denote by $S(n)$ the complete
tripartite $3$-graph on vertex set $[n]\coloneqq\\{1,2,\ldots,n\\}$ with parts
of sizes as equal as possible, see Figure 2. The number of hyperedges in
$S(n)$ is $s(n)\coloneqq\left\lfloor
n/3\right\rfloor\cdot\left\lfloor(n+1)/3\right\rfloor\cdot\left\lfloor(n+2)/3\right\rfloor$.
Bollobás [1] proved that $\mathrm{ex}(n,\\{K_{4}^{-},F_{5}\\})=s(n)$. This
result was extended by Frankl and Füredi [9], who proved that
$\mathrm{ex}(n,F_{5})=s(n)$ for $n\geqslant 3000$, and it was improved again
to $n\geqslant 33$ by Keevash and Mubayi [16].

$1$$2$$3$$4$$5$ Figure 1: Hypergraph $F_{5}$.

$V_{1}$$V_{2}$$V_{3}$ Figure 2: Hypergraph $S(n)$.

For every integer $t\geqslant 0$, denote by $F_{5}^{t}$ the hypergraph on
vertex set $\\{1,2,\ldots,5+t\\}$ with hyperedges
$\\{123,124\\}\cup\\{34k:5\leqslant k\leqslant 5+t\\}$, see Figure 4. Hence
$F_{5}^{0}=F_{5}$. Furthermore, denote by $F_{2}^{t}$ the hypergraph on vertex
set $\\{1,2,\ldots,3+t\\}$ with hyperedges $\\{12k:3\leqslant k\leqslant
3+t\\}$. Note that $F_{2}^{t}$-free hypergraphs are exactly the hypergraphs
with maximum codegree at most $t$, i.e., every pair of vertices is in at most
$t$ hyperedges. Let $\mathcal{H}(n,t)$ be the family of extremal $n$-vertex
$F_{2}^{t}$-free $3$-graphs $H(n,t)$. Define $\mathcal{S}_{t}^{\circ}(n)$ as
the family of $3$-graphs $S_{t}^{\circ}(n)$ on vertex set $[n]$, where
$S_{t}^{\circ}(n)$ is obtained from $S(n)$ by adding a copy of
$H(|V_{i}|,t)\in\mathcal{H}(|V_{i}|,t)$ to every part $V_{i}$ in the partition
of $S(n)$, see Figure 4. Let

$s_{t}^{\circ}(n)\coloneqq\bigg{\lfloor}\frac{n}{3}\bigg{\rfloor}\left\lfloor\frac{n+1}{3}\right\rfloor\left\lfloor\frac{n+2}{3}\right\rfloor+\mathrm{ex}\left(\bigg{\lfloor}\frac{n}{3}\bigg{\rfloor},F_{2}^{t}\right)+\mathrm{ex}\left(\left\lfloor\frac{n+1}{3}\right\rfloor,F_{2}^{t}\right)+\mathrm{ex}\left(\left\lfloor\frac{n+2}{3}\right\rfloor,F_{2}^{t}\right)$

be the number of hyperedges in every
$S_{t}^{\circ}(n)\in\mathcal{S}_{t}^{\circ}(n)$. Our main result is the
following theorem.

######  Theorem 1.1.

For every integer $t\geqslant 0$ and sufficiently large $n$, the
$F_{5}^{t}$-free $3$-graphs on vertex set $[n]$ with maximum number of
hyperedges are exactly the hypergraphs
$S_{t}^{\circ}(n)\in\mathcal{S}_{t}^{\circ}(n)$, and hence
$\mathrm{ex}(n,F_{5}^{t})=s_{t}^{\circ}(n)$.

Thus, we solve the Turán problem for each hypergraph in this infinite family
of forbidden hypergraphs for sufficiently large $n$ and characterize their
extremal constructions. Our extremal constructions
$\mathcal{S}_{t}^{\circ}(n)$ are similar in soul to the following result of
Simonovits [22]. For $r,d\geqslant 2$, let $Q(r,d)$ be the complete
$(d+1)$-partite graph on $rd+1$ vertices with one part of size $1$ and $d$
parts of size $r$. Let $\mathcal{U}(n,r,d)$ be the family of graphs, each of
which is obtained from the $n$-vertex complete $d$-partite graph with parts of
sizes as equal as possible by adding maximum number of edges inside each part
such that every vertex is adjacent to at most $r-1$ other vertices in the same
part. Let $\mathcal{U}^{*}(n,r,d)$ be the family of graphs in
$\mathcal{U}(n,r,d)$ with the extra requirement that there is no triangle
inside any part. Simonovits [22], generalizing an unpublished result of Erdős,
proved that all the graphs in $\mathcal{U}^{*}(n,r,d)$ are extremal
constructions for $Q(r,d)$ and all the extremal constructions for $Q(r,d)$ are
in $\mathcal{U}(n,r,d)$, for sufficiently large $n$.

For our proof of Theorem 1.1, we derive a stability result, followed up by a
cleaning method, which reveals the structure of the extremal $F_{5}^{t}$-free
hypergraphs step by step.

$1$$2$$3$$4$$5$$\ldots$$5+t$ Figure 3: Hypergraph $F_{5}^{t}$.

$V_{1}$$V_{2}$$V_{3}$${\scriptstyle H\left(|V_{1}|,\,t\right)}$${\scriptstyle
H\left(|V_{2}|,\,t\right)}$${\scriptstyle H\left(|V_{3}|,\,t\right)}$ Figure
4: Hypergraph $S_{t}^{\circ}(n)$.

One of the roadblocks in our proof is that there exists another family of
almost extremal $F_{5}^{t}$-free $3$-graphs, whose number of hyperedges is
smaller than $s_{t}^{\circ}(n)$ only by $O(n)$. Hence for the proof of Theorem
1.1, we need to have a good understanding of $\mathrm{ex}(n,F_{2}^{t})$. The
value of $\mathrm{ex}(n,F_{2}^{t})$ is closely related to designs. An
$(n,k,r,t)$_-design_ is a family $X$ of distinct $k$-subsets of an $n$-set
$V$, such that every $r$-subset of $V$ belongs to exactly $t$ elements of $X$.
Hence, if every pair of vertices in hypergraph $H(n,t)\in\mathcal{H}(n,t)$ is
in exactly $t$ hyperedges, then $H(n,t)$ is just an $(n,3,2,t)$-design and
thus $H(n,t)$ has $\frac{t}{3}\binom{n}{2}$ hyperedges. Dehon [3] proved the
following necessary and sufficient condition for the existence of
$(n,3,2,t)$-designs.

######  Theorem 1.2 (Dehon [3]).

Let $t$ and $n$ be integers such that $0\leqslant t\leqslant n-2$. Then, there
exists an $(n,3,2,t)$-design iff $tn(n-1)\equiv 0\pmod{6}$ and $t(n-1)\equiv
0\pmod{2}$.

If $t$ is a multiple of $6$, then there always exists an $(n,3,2,t)$-design
for sufficiently large $n$. Keevash proved that the number of non-isomorphic
$(n,3,2,t)$-designs (see Theorem 6.1 in [15]) is

$t!^{-\binom{n}{2}}\left(\left(\frac{t}{e}\right)^{2}(n-2)+o(n-2)\right)^{\frac{t}{3}\binom{n}{2}}=n^{\Omega(n^{2})}.$

Thus, by Theorem 1.1, there are exponentially many extremal constructions for
$F_{5}^{6t}$ whenever $t\geqslant 1$.

Note that if $n=6k+1$ or $n=6k+3$ for some integer $k\geqslant(t+1)/6$, then
there always exists an $(n,3,2,t)$-design. Thus, we have the following
corollary of Theorem 1.1.

######  Corollary 1.3.

For every $t\geqslant 0$, if $n$ is sufficiently large and $n\equiv 3$ or
$9\pmod{18}$, then

$\mathrm{ex}(n,F_{5}^{t})=\frac{1}{27}n^{3}+\frac{1}{18}tn^{2}-\frac{1}{6}tn.$

There does not exist an $(n,3,2,t)$-design for every $n$ and $t$, and
therefore it is non-trivial to give a reasonably good lower bounds on
$\mathrm{ex}(n,F_{2}^{t})$ in general. In Section 2.2, we derive a lower bound
on $\mathrm{ex}(n,F_{2}^{t})$ which is good enough for our purpose. We cannot
give an explicit formula for $\mathrm{ex}(n,F_{2}^{t})$. Similar phenomena
often occur in Extremal Combinatorics. An interesting classical example is by
Erdős and Simonovits [6]. Denote by $K_{2,2,2}$ the complete tripartite graph
with each part of size $2$. They [6] proved that for sufficiently large $n$,
the extremal $K_{2,2,2}$-free graph is realized by the graphs whose vertex set
can be partitioned into two subsets $A$ and $B$ such that $G[A]$ is
$C_{4}$-free and $G[B]$ is $P_{3}$-free, where $C_{4}$ is the cycle with $4$
vertices and $P_{3}$ is the path with $3$ vertices. However, they did not
determine the exact sizes of $A$ and $B$, as $\mathrm{ex}(n,C_{4})$ is not
known precisely for every $n$. Similarly to $\mathrm{ex}(n,C_{4})$, in our
case $\mathrm{ex}(n,F_{2}^{t})$ is not known precisely for every $n$. We are
still able to confirm the above-mentioned unified description of the extremal
$F_{5}^{t}$-free hypergraphs and in particular, prove that the three parts in
the partition have to be balanced, i.e., they have sizes $\left\lfloor
n/3\right\rfloor$, $\left\lfloor(n+1)/3\right\rfloor$ and
$\left\lfloor(n+2)/3\right\rfloor$.

Our paper is organized as follows. In Section 2, we introduce our notation,
give an estimate on $\mathrm{ex}(n,F_{2}^{t})$ and some useful results about
$S_{t}^{\circ}(n)$, and deduce a stability result for $F_{5}^{t}$. In Section
3, we prove Theorem 1.1, our main result. We discuss some open problems in
Section 4.

##  2 Preliminaries

###  2.1 Notation

For a positive integer $m$, we use $[m]$ for the set $\\{1,2,\ldots,m\\}$. We
write $xy$ for the set $\\{x,y\\}$ and $xyz$ for the set $\\{x,y,z\\}$. For a
set $S$ and a non-negative integer $k$, we use $\binom{S}{k}$ to denote the
family of all $k$-subsets of $S$. For an $n$-vertex $r$-graph $H$, we will
assume its vertex set $V(H)$ is $[n]$. We often use $H$ for the hyperedge set
of $H$ and denote by $|H|$ the number of hyperedges in $H$. Let $H$ be an
$n$-vertex $3$-graph. For vertices $x,y\in[n]$ and (not necessarily disjoint)
subsets of vertices $S,T\subseteq[n]$, let

  * •

$L_{S,T}(x)\coloneqq\\{yz:y\in S,\,z\in T,\,xyz\in H\\}$ be the _link graph_
of $x$ between $S$ and $T$,

  * •

$d_{S,T}(x)\coloneqq|L_{S,T}(x)|$ be the _degree_ of $x$ between $S$ and $T$,

  * •

$L_{S}(x,y)\coloneqq\\{z:z\in S,\,xyz\in H\\}$ be the set of _neighbors_ of
$x$ and $y$ in $S$, and

  * •

$d_{S}(x,y)\coloneqq|L_{S}(x,y)|$ be the _codegree_ of $x$ and $y$ in $S$.

For a given partition $\pi=(V_{1},V_{2},V_{3})$ of a subset of $[n]$, we say
that $\pi$ is _balanced_ if the sizes of its parts differ by at most $1$. We
denote by $K_{\pi}$ the set of triples with exactly one vertex in each part of
$\pi$. Let $H_{\pi}\coloneqq H\cap K_{\pi}$ and $\bar{H}_{\pi}\coloneqq
K_{\pi}\setminus H_{\pi}$. We call hyperedges in $H_{\pi}$ the _crossing
hyperedges_ (of $\pi$) and call hyperedges in $\bar{H}_{\pi}$ the _missing
crossing hyperedges_ (of $\pi$). For $i,j\in\\{1,2,3\\}$, we simply write
$L_{i,j}(x)$ for $L_{V_{i},V_{j}}(x)$ and $L_{i}(x,y)$ for $L_{V_{i}}(x,y)$.
Similarly, we use $d_{i,j}(x)$ for $d_{V_{i},V_{j}}(x)$ and $d_{i}(x,y)$ for
$d_{V_{i}}(x,y)$. We also write $L(x,y)$ for $L_{[n]}(x,y)$, $L(x)$ for
$L_{[n],[n]}(x)$, $d(x,y)$ for $d_{[n]}(x,y)$, and $d(x)$ for
$d_{[n],[n]}(x)$.

###  2.2 Results on $\boldsymbol{s_{t}^{\circ}(n)}$

######  Proposition 2.1.

For every integer $t\geqslant 0$ and sufficiently large $n$, we have

$\displaystyle\frac{t}{3}\binom{n}{2}\geqslant\mathrm{ex}(n,F_{2}^{t})\geqslant\begin{cases}\frac{t}{3}\binom{n}{2}-\frac{n}{3}-\frac{t^{2}}{6}-3t&\text{if
}t\text{ is odd and }n\text{ is even},\\\
\frac{t}{3}\binom{n}{2}-\frac{8t}{3}&\text{if }t\text{ is odd and }n\text{ is
odd},\\\ \frac{t}{3}\binom{n}{2}-\frac{2t}{3}&\text{if }t\text{ is
even}.\end{cases}$

We give the proof of Proposition 2.1 in the Appendix.

######  Lemma 2.2.

For every integer $t\geqslant 0$ and sufficiently large $n$, we have

$s_{t}^{\circ}(n)\in\left[\frac{1}{27}n^{3}+\frac{1}{18}tn^{2}-\left(\frac{1}{6}t+\frac{4}{9}\right)n-\left(\frac{1}{2}t^{2}+\frac{80}{9}t+\frac{2}{27}\right),\,\frac{1}{27}n^{3}+\frac{1}{18}tn^{2}-\frac{1}{6}tn\right].$

###### Proof.

By the definition of $s_{t}^{\circ}(n)$ and Proposition 2.1, we have the
following statements.
Case: $n\equiv 0\pmod{3}$

$\displaystyle s_{t}^{\circ}(n)$
$\displaystyle=\left(\frac{n}{3}\right)^{3}+3\cdot\mathrm{ex}\left(\frac{n}{3},F_{2}^{t}\right)$
$\displaystyle\in\left[\frac{1}{27}n^{3}+\frac{1}{18}tn^{2}-\left(\frac{1}{6}t+\frac{1}{3}\right)n-\left(\frac{1}{2}t^{2}+9t\right),\,\frac{1}{27}n^{3}+\frac{1}{18}tn^{2}-\frac{1}{6}tn\right].$

Case: $n\equiv 1\pmod{3}$

$\displaystyle s_{t}^{\circ}(n)$
$\displaystyle=\left(\frac{n-1}{3}\right)^{2}\left(\frac{n+2}{3}\right)+2\cdot\mathrm{ex}\left(\frac{n-1}{3},F_{2}^{t}\right)+\mathrm{ex}\left(\frac{n+2}{3},F_{2}^{t}\right)$
$\displaystyle\in\Bigg{[}\frac{1}{27}n^{3}+\frac{1}{18}tn^{2}-\left(\frac{1}{6}t+\frac{4}{9}\right)n-\left(\frac{1}{2}t^{2}+\frac{80}{9}t-\frac{2}{27}\right),\,$
$\displaystyle\qquad\qquad\qquad\frac{1}{27}n^{3}+\frac{1}{18}tn^{2}-\left(\frac{1}{6}t+\frac{1}{9}\right)n+\left(\frac{1}{9}t+\frac{2}{27}\right)\Bigg{]}.$

Case: $n\equiv 2\pmod{3}$

$\displaystyle s_{t}^{\circ}(n)$
$\displaystyle=\left(\frac{n-2}{3}\right)\left(\frac{n+1}{3}\right)^{2}+\mathrm{ex}\left(\frac{n-2}{3},F_{2}^{t}\right)+2\cdot\mathrm{ex}\left(\frac{n+1}{3},F_{2}^{t}\right)$
$\displaystyle\in\Bigg{[}\frac{1}{27}n^{3}+\frac{1}{18}tn^{2}-\left(\frac{1}{6}t+\frac{4}{9}\right)n-\left(\frac{1}{2}t^{2}+\frac{80}{9}t+\frac{2}{27}\right),\,$
$\displaystyle\qquad\qquad\qquad\frac{1}{27}n^{3}+\frac{1}{18}tn^{2}-\left(\frac{1}{6}t+\frac{1}{9}\right)n+\left(\frac{1}{9}t-\frac{2}{27}\right)\Bigg{]}.\qed$

For a partition $\pi=(V_{1},V_{2},V_{3})$ of $[n]$, let
$\mathcal{S}_{t,\pi}^{\circ}(n)$ be the family of hypergraphs on vertex set
$[n]$ whose hyperedges contain $K_{\pi}$, and each part $V_{i}$ spans a copy
of $H(|V_{i}|,t)\in\mathcal{H}(|V_{i}|,t)$. Hence,
$\mathcal{S}_{t,\pi}^{\circ}(n)$ is just $\mathcal{S}_{t}^{\circ}(n)$ when
$\pi$ is balanced. Let

$s_{t,\pi}^{\circ}(n)\coloneqq|V_{1}||V_{2}||V_{3}|+\sum_{i=1}^{3}\mathrm{ex}(|V_{i}|,F_{2}^{t})$

be the number of hyperedges in every
$S_{t,\pi}^{\circ}(n)\in\mathcal{S}_{t,\pi}^{\circ}(n)$.

######  Lemma 2.3.

Let $t\geqslant 0$. For every sufficiently large integer $n$, we have
$s_{t}^{\circ}(n)\geqslant s_{t,\pi}^{\circ}(n)$ for every partition $\pi$ of
$[n]$, where equality holds only if $\pi$ is balanced.

###### Proof.

Suppose that there is a partition $\pi=(V_{1},V_{2},V_{3})$ of $[n]$ that
achieves the maximum value of $s_{t,\pi}^{\circ}(n)$, but $\pi$ is not
balanced. Assume that the three parts of $\pi$ have sizes $a_{1}\leqslant
a_{2}\leqslant a_{2}$, where $a_{1}+a_{2}+a_{3}=n$ and $a_{1}+2\leqslant
a_{3}$. We first prove $a_{2}\geqslant(\frac{1}{3}-0.01)n$. Otherwise, by
Proposition 2.1 and Lemma 2.2, we have

$\displaystyle s_{t,\pi}^{\circ}(n)$ $\displaystyle\leqslant
a_{1}a_{2}a_{3}+\frac{t}{3}\left(\binom{a_{1}}{2}+\binom{a_{2}}{2}+\binom{a_{3}}{2}\right)\leqslant\frac{a_{1}+a_{3}}{2}a_{2}\frac{a_{1}+a_{3}}{2}+t\binom{n}{2}$
$\displaystyle=a_{2}\left(\frac{n-a_{2}}{2}\right)^{2}+t\binom{n}{2}\leqslant\left(\frac{1}{3}-0.01\right)n\left(\frac{n-\left(\frac{1}{3}-0.01\right)n}{2}\right)^{2}+t\binom{n}{2}$
$\displaystyle<\left(\frac{1}{27}-10^{-10}\right)n^{3}<s_{t}^{\circ}(n),$

where the third-to-last inequality holds because the function $x\to
x((n-x)/2)^{2}$ is monotone increasing for $x\leqslant n/3$. This contradicts
our choice of $\pi$. Now, let $\pi^{\prime}$ be the partition of $[n]$
obtained from $\pi$ by moving a vertex from $V_{3}$ to $V_{1}$. Then,

$s_{t,\pi^{\prime}}^{\circ}(n)-s_{t,\pi}^{\circ}(n)=(a_{3}-a_{1}-1)a_{2}+\mathrm{ex}(a_{1}+1,F_{2}^{t})+\mathrm{ex}(a_{3}-1,F_{2}^{t})-\mathrm{ex}(a_{1},F_{2}^{t})-\mathrm{ex}(a_{3},F_{2}^{t}).$

By Proposition 2.1,

$\displaystyle\mathrm{ex}(a_{1}+1,F_{2}^{t})-\mathrm{ex}(a_{1},F_{2}^{t})\geqslant\frac{t}{3}\binom{a_{1}+1}{2}-\frac{a_{1}+1}{3}-\frac{t^{2}}{6}-3t-\frac{t}{3}\binom{a_{1}}{2}\geqslant\frac{t}{3}a_{1}-\frac{a_{1}+1}{3}-4t^{2}$

and

$\displaystyle\mathrm{ex}(a_{3}-1,F_{2}^{t})-\mathrm{ex}(a_{3},F_{2}^{t})$
$\displaystyle\geqslant\frac{t}{3}\binom{a_{3}-1}{2}-\frac{a_{3}-1}{3}-4t^{2}-\frac{t}{3}\binom{a_{3}}{2}=-\frac{t+1}{3}(a_{3}-1)-4t^{2}.$

We conclude

$\displaystyle s_{t,\pi^{\prime}}^{\circ}(n)-s_{t,\pi}^{\circ}(n)$
$\displaystyle\geqslant(a_{3}-a_{1}-1)\left(a_{2}-\frac{t}{3}\right)-\frac{a_{1}+a_{3}}{3}-8t^{2}\geqslant\left(a_{2}-\frac{t}{3}\right)-\frac{a_{1}+a_{3}}{3}-8t^{2}$
$\displaystyle=\frac{4}{3}a_{2}-\frac{n}{3}-\frac{t}{3}-8t^{2}>0,$

contradicting our choice of $\pi$. ∎

###  2.3 An almost extremal $\boldsymbol{F_{5}^{t}}$-free hypergraph

For $T=\\{v_{1},\ldots,v_{t}\\}\subseteq[n]$ and a partition
$\varpi=(W_{1},W_{2},W_{3})$ of $[n]\setminus T$, define
$S_{t,\varpi}^{\triangle}(n)$ to be the $3$-graph on vertex set $[n]$ with
hyperedges

$K_{\varpi}\cup\binom{T}{3}\cup\bigcup_{i=1}^{3}\\{vx_{1}x_{2}:v\in
T,\,x_{1},x_{2}\in W_{i}\\}.$

For an illustration of $S_{t,\varpi}^{\triangle}(n)$, see Figure 5. Let

$s_{t,\varpi}^{\triangle}(n)\coloneqq|W_{1}||W_{2}||W_{3}|+t\sum_{i=1}^{3}\binom{|W_{i}|}{2}+\binom{t}{3}$

be the number of hyperedges in $S_{t,\varpi}^{\triangle}(n)$. We remark that
similar constructions were proved by Simonovits to be extremal constructions
for certain graphs (see Theorem 2 in [22]).

$\vdots$$v_{1}$$v_{2}$$v_{3}$$v_{t}$$V_{1}$$V_{2}$$V_{3}$ Figure 5: Hypergraph
$S_{t,\varpi}^{\triangle}(n)$.

######  Lemma 2.4.

Let $t\geqslant 1$. For every sufficiently large integer $n$, we have
$s_{t}^{\circ}(n)>s_{t,\varpi}^{\triangle}(n)+\frac{n}{10}$ for every set
$\\{v_{1},\ldots,v_{t}\\}\subseteq[n]$ and partition $\varpi$ of
$[n]\setminus\\{v_{1},\ldots,v_{t}\\}$.

###### Proof.

Define function

$f_{n,t}(x_{1},x_{2},x_{3})\coloneqq
x_{1}x_{2}x_{3}+t\left(\frac{x_{1}(x_{1}-1)}{2}+\frac{x_{2}(x_{2}-1)}{2}+\frac{x_{3}(x_{3}-1)}{2}\right)+\binom{t}{3}$

on the domain $D:=\\{(x_{1},x_{2},x_{3})\in\mathbb{R}^{3}:\
x_{1},x_{2},x_{3}\geqslant 0,\ x_{1}+x_{2}+x_{3}=n-t\\}$. Note that for every
set $T=\\{v_{1},\ldots,v_{t}\\}\subseteq[n]$ and partition
$\varpi=(W_{1},W_{2},W_{3})$ of $[n]\setminus T$, we have
$s_{t,\varpi}^{\triangle}(n)=f(|W_{1}|,|W_{2}|,|W_{3}|)$. Also note that

$f_{n,t}\left(\frac{n-t}{3},\frac{n-t}{3},\frac{n-t}{3}\right)=\frac{1}{27}n^{3}+\frac{1}{18}tn^{2}-\left(\frac{2}{9}t^{2}+\frac{1}{2}t\right)n+\frac{8}{27}t^{3}+\frac{1}{3}t.$

Since $D$ is compact, $f_{n,t}$ achieves its maximum value at some point
$(y_{1},y_{2},y_{3})\in D$. If $y_{1}\leqslant t$, then

$f_{n,t}(y_{1},y_{2},y_{3})\leqslant
tn^{2}+3t\frac{n^{2}}{2}+t^{3}<\frac{n^{3}}{27}<f_{n,t}\left(\frac{n-t}{3},\frac{n-t}{3},\frac{n-t}{3}\right),$

a contradiction. Thus, $y_{1}>t$. Similarly, $y_{2}>t$ and $y_{3}>t$. We have

$\displaystyle
f_{n,t}\left(y_{1},\frac{y_{2}+y_{3}}{2},\frac{y_{2}+y_{3}}{2}\right)-f_{n,t}\left(y_{1},y_{2},y_{3}\right)=\frac{1}{4}(y_{1}-t)(y_{2}-y_{3})^{2}\geqslant
0,$

with equality iff $y_{2}=y_{3}$. Using the symmetry of $f$, we conclude that
the maximum value of $f_{n,t}$ is achieved when
$x_{1}=x_{2}=x_{3}=\frac{n-t}{3}$. For $t\geqslant 1$, by Lemma 2.2, we have

$s_{t}^{\circ}(n)-f_{n,t}\left(\frac{n-t}{3},\frac{n-t}{3},\frac{n-t}{3}\right)\geqslant\left(\frac{2}{9}t^{2}+\frac{1}{3}t-\frac{4}{9}\right)n-\left(\frac{8}{27}t^{3}+\frac{1}{2}t^{2}+\frac{83}{9}t+\frac{2}{27}\right)>\frac{n}{10}.$

Therefore, $s_{t}^{\circ}(n)>s_{t,\varpi}^{\triangle}(n)+\frac{1}{10}n$. ∎

###  2.4 Stability result

In this section, we prove the following stability theorem for $F_{5}^{t}$.

######  Theorem 2.5 (Stability theorem for $F_{5}^{t}$).

For every $t\geqslant 0$ and $\varepsilon>0$, there exist
$\delta\in(0,\varepsilon)$ and $N>0$ such that for every $n>N$, the following
statement holds. Let $H$ be an $F_{5}^{t}$-free $3$-graph $H$ on vertex set
$[n]$ with at least $(\frac{1}{27}-\delta)n^{3}$ hyperedges, and let
$\pi=(V_{1},V_{2},V_{3})$ be a partition of $[n]$ that maximizes $|H_{\pi}|$.
Then $|H\setminus H_{\pi}|\leqslant\varepsilon n^{3}$.

######  Claim 2.6.

The partition $\pi=(V_{1},V_{2},V_{3})$ in Theorem 2.5 has the following
additional properties.

  1. (i)

For $i\in[3]$, we have
$(\frac{1}{3}-3\varepsilon^{1/2})n<|V_{i}|<(\frac{1}{3}+6\varepsilon^{1/2})n$.

  2. (ii)

For $\\{i,j,k\\}=[3]$, we have $|\\{xy:x\in V_{i},\,y\in
V_{j},\,d_{k}(x,y)\leqslant|V_{k}|-\varepsilon^{1/2}n\\}|\leqslant
2\varepsilon^{1/2}n^{2}.$

  3. (iii)

For $\\{i,j,k\\}=[3]$ and every $x\in V_{i}$, we have
$d_{i,j}(x),\;d_{i,k}(x)\leqslant 3\varepsilon^{1/2}n^{2}.$

We need the following theorems and definitions for proving Theorem 2.5. For an
$r$-graph $H$, a _blow-up_ of $H$ is an $r$-graph obtained from $H$ by
replacing every vertex $v$ by a set $S_{v}$, where $S_{v_{1}}\cap
S_{v_{2}}=\varnothing$ for distinct vertices $v_{1},v_{2}$ and replacing every
hyperedge $\\{v_{1},\ldots,v_{r}\\}$ by the complete $r$-partite $r$-graph on
$S_{v_{1}}\cup\ldots\cup S_{v_{r}}$. When $|S_{v}|=t$ for every vertex $v$,
the blow-up is called the $t$-_blow-up_ of $H$ and denoted by $H[t]$. Note
that $F_{5}^{t}$ is a blow-up of $F_{5}$ and $F_{5}^{t}\subseteq F_{5}[t+1]$
for every $t\geqslant 0$. We will see that Theorem 2.5 follows easily from the
stability result for $F_{5}$ and the fact that blow-ups inherit the stability
of the original hypergraph.

######  Theorem 2.7 (Stability result for $F_{5}$, Keevash and Mubayi [16]).

For every $a>0$, there exist $b>0$ and $N>0$ such that if $n>N$ and $H$ is an
$F_{5}$-free $3$-graph on vertex set $[n]$ with at least
$(\frac{1}{27}-b)n^{3}$ hyperedges, then there exists a partition
$\pi=(V_{1},V_{2},V_{3})$ of $[n]$ such that $|H\setminus H_{\pi}|\leqslant
an^{3}$.

######  Lemma 2.8 (e.g. [14]).

For fixed integers $l\geqslant r\geqslant 2$, $t\geqslant 1$ and every
$\alpha>0$, there exists $n_{0}=n_{0}(l,r,t,\alpha)$ such that the following
holds. Let $F$ be an $r$-graph on $l$ vertices and $H$ be an $r$-graph on
$n\geqslant n_{0}$ vertices. If $H$ contains at least $\alpha n^{l}$ copies of
$F$, then $H$ contains a copy of $F[t]$.

We also use the hypergraph removal lemma.

######  Theorem 2.9 (Rödl, Nagle, Skokan, Schacht, and Kohayakawa [21], Gower
[12]).

For fixed integers $l\geqslant r\geqslant 2$ and every $\mu>0$, there exists
$\zeta=\zeta(l,r,\mu)>0$ and $n_{0}=n_{0}(l,r,\mu)$ such that the following
holds. Let $F$ be an $r$-graph on $l$ vertices and $H$ be an $r$-graph on
$n\geqslant n_{0}$ vertices. If $H$ contains at most $\zeta n^{l}$ copies of
$F$, then one can delete $\mu n^{r}$ hyperedges of $H$ to make it $F$-free.

###### Proof of Theorem 2.5.

Assume that $n$ is sufficiently large. Let $b$ be given by Theorem 2.7 when
applying it for $a=\varepsilon/2$. Let $\delta:=\min(b/2,\varepsilon/2)$. Let
$H$ be an $F_{5}^{t}$-free $3$-graph on vertex set $[n]$ with at least
$(\frac{1}{27}-\delta)n^{3}$ hyperedges and let $\pi$ be a $3$-partition of
$[n]$ maximizing $|H_{\pi}|$.

Setting $\mu=\delta$, $l=5$, and $r=3$ in Theorem 2.9, we get that there
exists $\zeta>0$ such that if an $n$-vertex $3$-graph $F$ contains at most
$\zeta n^{5}$ copies of $F_{5}$, then we can delete at most $\delta n^{3}$
hyperedges to make it $F_{5}$-free. Setting $\alpha=\zeta$ in Theorem 2.8, we
get that if $H$ contains at least $\zeta n^{5}$ copies of $F_{5}$, then $H$
contains a copy of $F[t+1]\supseteq F_{5}^{t}$, a contradiction to that $H$ is
$F_{5}^{t}$-free, so $H$ indeed contains at most $\zeta n^{5}$ copies of
$F_{5}$. Therefore, $H$ contains a spanning $F_{5}$-free subhypergraph
$H^{\prime}$ with at least $|H|-\delta
n^{3}\geqslant(\frac{1}{27}-2\delta)n^{3}\geqslant(\frac{1}{27}-b)n^{3}$
hyperedges. By Theorem 2.7, there exists a $3$-partition $\pi^{\prime}$ of
$[n]$ such that $|H^{\prime}\setminus
H^{\prime}_{\pi^{\prime}}|\leqslant\varepsilon n^{3}/2$. Thus,

$|H\setminus H_{\pi}|\leqslant|H\setminus
H_{\pi^{\prime}}|\leqslant|H\setminus H^{\prime}|+|H^{\prime}\setminus
H_{\pi^{\prime}}|=|H\setminus H^{\prime}|+|H^{\prime}\setminus
H^{\prime}_{\pi^{\prime}}|\leqslant\varepsilon n^{3}.\qed$

###### Proof of Claim 2.6.

For (i), assume $|V_{i}|\leqslant(\frac{1}{3}-3\varepsilon^{1/2})n$ for some
$i\in[3]$. The function $x\to x((n-x)/2)^{2}$ is monotone increasing when
$x<n/3$, and therefore

$|H|\leqslant|V_{1}||V_{2}||V_{3}|+|H\setminus
H_{\pi}|\leqslant|V_{i}|\left(\frac{n-|V_{i}|}{2}\right)^{2}+\varepsilon
n^{3}\leqslant\left(\frac{1}{27}-\frac{5}{4}\varepsilon-\frac{27}{4}\varepsilon^{3/2}\right)n^{3}<|H|,$

a contradiction. Thus $|V_{i}|>(\frac{1}{3}-3\varepsilon^{1/2})n$ for every
$i\in[3]$. Since $|V_{1}|+|V_{2}|+|V_{3}|=n$, we have
$|V_{i}|<(\frac{1}{3}+6\varepsilon^{1/2})n$ for $i\in[3]$.

Assume that (ii) does not hold. Then $|\bar{H}_{\pi}|>\varepsilon^{1/2}n\cdot
2\varepsilon^{1/2}n^{2}=2\varepsilon n^{3}$, and thus

$\displaystyle|H|=|V_{1}||V_{2}||V_{3}|-|\bar{H}_{\pi}|+|H\setminus
H_{\pi}|\leqslant\left(\frac{n}{3}\right)^{3}-2\varepsilon n^{3}+\varepsilon
n^{3}<|H|,$

a contradiction.

For (iii), assume for contradiction that $d_{i,j}(x)>3\varepsilon^{1/2}n^{2}$
for some $x\in V_{i}$. Then, by (ii), there exist $x^{\prime}\in V_{i}$ and
$y\in V_{j}$ such that $xx^{\prime}y\in H$ and
$d_{k}(x^{\prime},y)>|V_{k}|-\varepsilon^{1/2}n$. By our assumption that $\pi$
maximizes $|H_{\pi}|$, we have $d_{j,k}(x)\geqslant
d_{i,j}(x)>3\varepsilon^{1/2}n^{2}$; otherwise moving $x$ to $V_{k}$ will
strictly increase $|H_{\pi}|$. There exists a vertex $z\in V_{k}$ such that
$x^{\prime}yz\in H$ and $d_{j}(x,z)\geqslant t+2$; otherwise for every $z$
with $x^{\prime}yz\in H$ we have $d_{j}(x,z)\leqslant t+1$ and then

$\displaystyle
d_{j,k}(x)\leqslant(t+1)d_{k}(x^{\prime},y)+|V_{j}|\left(|V_{k}|-d_{k}(x^{\prime},y)\right)\leqslant(t+1)n+n\cdot\varepsilon^{1/2}n<3\varepsilon^{1/2}n^{2},$

a contradiction. Now choose distinct vertices $y_{1},\ldots,y_{t+1}\in
L_{j}(x,z)\setminus\\{y\\}$. The hyperedges
$\\{x^{\prime}yx,x^{\prime}yz,xzy_{1},\ldots,xzy_{t+1}\\}$ form a copy of
$F_{5}^{t}$ in $H$, a contradiction. ∎

##  3 Proof of Theorem 1.1

In Section 3.1, using the stability result for $F_{5}^{t}$, Theorem 2.5, we
show that if $H$ is an extremal $F_{5}^{t}$-free hypergraph, then
$|\bar{H}_{\pi}|=O(n^{2})$ for some partition $\pi$. For a hypergraph $H$ on
vertex set $[n]$, denote by $\delta(H)\coloneqq\min\\{d(v):v\in[n]\\}$ the
_minimum degree_ of $H$. In Sections 3.2, 3.3, and 3.4, we prove Theorem 1.1
with an extra assumption on the minimum degree, by distinguishing “typical”
and “non-typical” vertices and using their respective properties. Finally, in
Section 3.5, we derive Theorem 1.1.

###  3.1 Upper bound on $\boldsymbol{|\bar{H}_{\pi}|}$

######  Lemma 3.1.

Let $H$ be an $F_{5}^{t}$-free $3$-graph on vertex set $[n]$. For every pair
of vertices $x,x^{\prime}\in[n]$ with $d(x,x^{\prime})\geqslant t+1$ and
disjoint subsets of vertices $S,T\subseteq[n]$, we have

$d_{S,T}(x)+d_{S,T}(x^{\prime})\leqslant|S||T|+(t+3)n$

and

$d_{S,S}(x)+d_{S,S}(x^{\prime})\leqslant\frac{1}{2}|S|^{2}+(t+4)n.$

###### Proof.

Fix $t+1$ distinct vertices $v_{1},\ldots,v_{t+1}\in L(x,x^{\prime})$. There
are at least $(|S|-t-3)(|T|-t-3)$ pairs $yz$ such that $y\in S$, $z\in T$, and
$\\{y,z\\}\cap\\{x,x^{\prime},v_{1},\ldots,v_{t+1}\\}=\varnothing$. For each
such pair, $yzx\notin H$ or $yzx^{\prime}\notin H$; otherwise the hyperedges
$\\{yzx$, $yzx^{\prime}$, $xx^{\prime}v_{1}$, …, $xx^{\prime}v_{t+1}\\}$ form
a copy of $F_{5}^{t}$ in $H$. Then,

$d_{S,T}(x)+d_{S,T}(x^{\prime})\leqslant
2|S||T|-(|S|-t-3)(|T|-t-3)\leqslant|S||T|+(t+3)n.$

Similarly, there are at least $\binom{|S|-t-3}{2}$ pairs $yz$ such $y,z\in S$
and $\\{y,z\\}\cap\\{x,x^{\prime},v_{1},\ldots,v_{t+1}\\}=\varnothing$. Again,
for each such pair, $yzx\notin H$ or $yzx^{\prime}\notin H$. We conclude

$\displaystyle d_{S,S}(x)+d_{S,S}(x^{\prime})$ $\displaystyle\leqslant
2\binom{|S|}{2}-\binom{|S|-t-3}{2}\leqslant\frac{1}{2}|S|^{2}+(t+4)n.\qed$

######  Theorem 3.2.

For every $t\geqslant 0$ and $\varepsilon>0$, there exists $N>0$ such that if
$n>N$ the following holds. Let $H$ be an $F_{5}^{t}$-free $3$-graph on vertex
set $[n]$ with $|H|\geqslant s_{t}^{\circ}(n)$ and $\pi$ be a partition of
$[n]$ maximizing $|H_{\pi}|$. Then,
$|\bar{H}_{\pi}|\leqslant\left(\frac{1}{9}+\varepsilon\right)tn^{2}.$

###### Proof.

We can assume that $\varepsilon$ is sufficiently small and $n$ is sufficiently
large. Let $\beta>0$ be the real number such that
$\varepsilon=(2t+25)\beta^{1/2}$. For $i\in[3]$, we define

$\displaystyle P_{i}\coloneqq\\{xx^{\prime}:x,x^{\prime}\in
V_{i},\,d(x,x^{\prime})\leqslant t\\}\quad\textrm{and}\quad
Q_{i}\coloneqq\\{xx^{\prime}:x,x^{\prime}\in V_{i},\,d(x,x^{\prime})\geqslant
t+1\\}.$

Let $M_{i}$ be a maximum matching of $Q_{i}$, and let $E_{i}$ be the set of
endpoints of the pairs in $M_{i}$, i.e., the vertices $x\in V_{i}$ such that
there exists $x^{\prime}\in V_{i}$ with $xx^{\prime}\in M_{i}$. Note that
$|E_{i}|=2|M_{i}|$ and every pair in $Q_{i}$ contains at least one point in
$E_{i}$, since $M_{i}$ is a maximum matching of $Q_{i}$.

######  Claim 3.3.

We have $|Q_{i}|\leqslant(t+2)\beta^{1/2}n^{2}$ and
$|M_{i}|\leqslant(t+2)\beta^{1/2}n$ for $i\in[3]$.

###### Proof.

For $\\{i,j,k\\}=[3]$, define $S_{j,k}$ to be the set of pairs $yz$ such that
$y\in V_{j},z\in V_{k}$, and $d_{i}(y,z)\geqslant|V_{i}|-\beta^{1/2}n$. By
Claim 2.6 (i) and (ii),

$|S_{j,k}|\geqslant|V_{j}||V_{k}|-2\beta^{1/2}n^{2}\geqslant\left(\left(\frac{1}{3}-3\beta^{1/2}\right)n\right)^{2}-2\beta^{1/2}n^{2}\geqslant\frac{n^{2}}{10}.$

Thus, we can choose $t+2$ pairwise disjoint pairs
$y_{1}z_{1},\ldots,y_{t+2}z_{t+2}$ from $S_{j,k}$. Define $U_{i}$ to be the
set of vertices $x\in V_{i}$ such that $xy_{a}z_{a}\notin H$ for some
$a\in[t+2]$. Then, $|U_{i}|\leqslant(t+2)\beta^{1/2}n$.

For $x_{1},x_{2}\in V_{i}\setminus U_{i}$, we have $x_{1}x_{2}\notin Q_{i}$;
otherwise there are $t+1$ distinct vertices $v_{1},\ldots,v_{t+1}\in
L(x_{1},x_{2})$ and there is some $a\in[t+2]$ such that
$\\{v_{1},\ldots,v_{t+1}\\}\cap\\{y_{a},z_{a}\\}=\varnothing$, and hence, the
hyperedges
$\\{y_{a}z_{a}x_{1},y_{a}z_{a}x_{2},x_{1}x_{2}v_{1},\ldots,x_{1}x_{2}v_{t+1}\\}$
form a copy of $F_{5}^{t}$ in $H$, a contradiction. Therefore, every pair in
$Q_{i}$ contains at least one vertex in $U_{i}$. We conclude
$|Q_{i}|\leqslant|U_{i}||V_{i}|\leqslant(t+2)\beta^{1/2}n^{2}$ and
$|M_{i}|\leqslant|U_{i}|\leqslant(t+2)\beta^{1/2}n$. ∎

######  Claim 3.4.

We have

$|H\setminus
H_{\pi}|\leqslant\left(\frac{1}{6}+6\beta^{1/2}+54\beta\right)tn^{2}+|M|(2t+16)\beta^{1/2}n^{2}.$

###### Proof.

For $i\in[3]$, let $H_{i}$ be the set of hyperedges in $H$ containing at least
two vertices in $V_{i}$. The number of hyperedges in $H_{i}$ that contain a
pair in $P_{i}$ is most $t|P_{i}|$, because every pair in $P_{i}$ has codegree
at most $t$ by definition. The number of hyperedges in $H_{i}$ that contain no
pair in $P_{i}$ and also no vertex in $[n]\setminus V_{i}$ is at most
$|E_{i}||Q_{i}|$. The number of hyperedges in $H_{i}$ that contain no pair in
$P_{i}$ but a vertex in $[n]\setminus V_{i}$ is at most $|E_{i}|\cdot 2\cdot
3\beta^{1/2}n^{2}$ by Claim 2.6 (iii). Adding up the number of hyperedges of
these three types, we get

$\displaystyle|H_{i}|$ $\displaystyle\leqslant
t\binom{\left(\frac{1}{3}+6\beta^{1/2}\right)n}{2}+2(t+2)\beta^{1/2}n^{2}|M_{i}|+12\beta^{1/2}n^{2}|M_{i}|$
$\displaystyle\leqslant\left(\frac{1}{18}+2\beta^{1/2}+18\beta\right)tn^{2}+(2t+16)\beta^{1/2}n^{2}|M_{i}|,$

where the first inequality follows from Claims 2.6 (i) and 3.3. Then,

$|H\setminus
H_{\pi}|=\sum_{i=1}^{3}|H_{i}|\leqslant\left(\frac{1}{6}+6\beta^{1/2}+54\beta\right)tn^{2}+|M|(2t+16)\beta^{1/2}n^{2}.\qed$

######  Claim 3.5.

We have

$|\bar{H}_{\pi}|+\sum_{i=1}^{3}\mathrm{ex}(|V_{i}|,F_{2}^{t})\geqslant|M|\left(\frac{1}{9}-(2t+7)\beta^{1/2}\right)n^{2}+\left(\frac{1}{18}-2\beta^{1/2}\right)tn^{2}.$

###### Proof.

For $\\{i,j,k\\}=[3]$ and $x_{1}x_{2}\in M_{i}$, by Lemma 3.1, we have

$d_{V_{j}\setminus E_{j},V_{k}\setminus E_{k}}(x_{1})+d_{V_{j}\setminus
E_{j},V_{k}\setminus E_{k}}(x_{2})\leqslant|V_{j}\setminus
E_{j}||V_{k}\setminus E_{k}|+(t+3)n,$

so there are at least

$|M_{i}|\left(2|V_{j}\setminus E_{j}||V_{k}\setminus
E_{k}|-\left(|V_{j}\setminus E_{j}||V_{k}\setminus
E_{k}|+(t+3)n\right)\right)$

missing crossing hyperedges containing exactly one vertex in each of $E_{i}$,
$V_{j}\setminus E_{j}$, and $V_{k}\setminus E_{k}$. By Claims 2.6 (i) and 3.3,
we have

$|\bar{H}_{\pi}|\geqslant|M|\left(\left(\left(\frac{1}{3}-3\beta^{1/2}-2(t+2)\beta^{1/2}\right)n\right)^{2}-(t+3)n\right)\geqslant|M|\left(\frac{1}{9}-(2t+7)\beta^{1/2}\right)n^{2}.$

By Claim 2.6 (i) and the lower bounds on $\mathrm{ex}(n,F_{2}^{t})$ in
Proposition 2.1, we have

$\displaystyle\sum_{i=1}^{3}\mathrm{ex}(|V_{i}|,F_{2}^{t})\geqslant
t\binom{\left\lfloor\left(\frac{1}{3}-3\beta^{1/2}\right)n\right\rfloor}{2}-\frac{n}{3}-\frac{t^{2}}{2}-9t\geqslant\left(\frac{1}{18}-2\beta^{1/2}\right)tn^{2}.$
(1)

Summing them up, we get the lower bound desired. ∎

######  Claim 3.6.

We have $|M|\leqslant t$.

###### Proof.

Assume $|M|\geqslant t+1$. We get $|H\setminus
H_{\pi}|<|\bar{H}_{\pi}|+\sum_{i=1}^{3}\mathrm{ex}(|V_{i}|,F_{2}^{t})$ by
Claims 3.4 and 3.5. This implies $|H|<s_{t,\pi}^{\circ}(n)<s_{t}^{\circ}(n)$
by Lemma 2.3, a contradiction. ∎

Finally, Theorem 3.2 follows from a short calculation. Since $|H|\geqslant
s_{t,\pi}^{\circ}(n)$, we have $|\bar{H}_{\pi}|\leqslant|H\setminus
H_{\pi}|-\sum_{i=1}^{3}\mathrm{ex}(|V_{i}|,F_{2}^{t})$ and thus by Claims 3.4,
3.6, and (1), we get

$\displaystyle|\bar{H}_{\pi}|$
$\displaystyle\leqslant\left(\frac{1}{6}+6\beta^{1/2}+54\beta\right)tn^{2}+(2t+16)\beta^{1/2}tn^{2}-\left(\frac{1}{18}-2\beta^{1/2}\right)tn^{2}$
$\displaystyle\leqslant\left(\frac{1}{9}+(2t+25)\beta^{1/2}\right)tn^{2}=\left(\frac{1}{9}+\varepsilon\right)tn^{2}.\qed$

######  Remark 3.7.

For $t=0$, Theorem 3.2 states that an extremal $F_{5}$-free $n$-vertex
$3$-graph is complete tripartite for sufficiently large $n$. This proves
Theorem 1.1 in the case $F_{5}^{0}=F_{5}$.

###  3.2 Typical and non-typical vertices

For every integer $t\geqslant 0$, let $c=c(t)\coloneqq(t+100)^{-1000}$. For a
$3$-graph $H$ on vertex set $[n]$ and a partition $\pi=(V_{1},V_{2},V_{3})$ of
$[n]$, define

$\displaystyle B_{i}\coloneqq\\{x\in V_{i}:d_{j,k}(x)\leqslant cn^{2}\\},\quad
A_{i}\coloneqq V_{i}\setminus B_{i},\quad\textrm{for $\\{i,j,k\\}=[3]$},$
$\displaystyle B\coloneqq B_{1}\cup B_{2}\cup B_{3},\quad\text{and}\quad
A\coloneqq A_{1}\cup A_{2}\cup A_{3}.$

We call vertices in $A$ _typical_ and vertices in $B$ _non-typical_. In
Sections 3.2.1 and 3.2.2, we prove properties of non-typical and typical
vertices, respectively.

####  3.2.1 Non-typical vertices

######  Lemma 3.8.

Let $t\geqslant 0$, $n$ be sufficiently large, and $H$ be an $F_{5}^{t}$-free
$3$-graph on vertex set $[n]$ with $|H|\geqslant s_{t}^{\circ}(n)$ and
$\delta(H)\geqslant\frac{1}{9}n^{2}-n$. Further, let $\pi=(V_{1},V_{2},V_{3})$
be a partition of $[n]$ maximizing $|H_{\pi}|$ and $c,B$ be defined as above.
The following statements hold.

  1. (i)

$|B|\leqslant t$.

  2. (ii)

For every vertex $v\in B$, we have $d_{1,2}(v),d_{1,3}(v),d_{2,3}(v)\leqslant
cn^{2}$.

  3. (iii)

For every pair of distinct vertices $v,v^{\prime}\in B$, we have
$d(v,v^{\prime})\leqslant t$.

###### Proof of (i).

By Claim 2.6 (i), Theorem 3.2, and the definition of $B_{i}$, we first have
$|B_{i}|\leqslant t$ for $i\in[3]$. Let $\\{i,j,k\\}=[3]$. For every $x\in
B_{i}$, the number of missing crossing hyperedges that contain $x$ and do not
contain any vertex from $B_{j}\cup B_{k}$ is at least

$\displaystyle(|V_{j}|-|B_{j}|)(|V_{k}|-|B_{k}|)-cn^{2}\geqslant\left(\frac{1}{3}-4c\right)^{2}n^{2}-cn^{2}\geqslant\left(\frac{1}{9}-4c\right)n^{2}.$

Thus, by Theorem 3.2, we have
$|B|\left(\frac{1}{9}-4c\right)n^{2}\leqslant|\bar{H}_{\pi}|\leqslant\left(\frac{1}{9}+c\right)tn^{2},$
implying $|B|\leqslant t$. ∎

###### Proof of (ii).

Let $\\{i,j,k\\}=[3]$. By the definition of $B_{i}$, we have
$d_{j,k}(x)\leqslant cn^{2}$ for every $x\in B_{i}$. As $\pi$ maximizes
$|H_{\pi}|$, we have $d_{i,j}(x),d_{i,k}(x)\leqslant d_{j,k}(x)\leqslant
cn^{2}$. ∎

###### Proof of (iii).

Assume for contradiction that there exist vertices $v,v^{\prime}\in B$ such
that $d(v,v^{\prime})\geqslant t+1$. By Claim 2.6 (i) and Lemma 3.1, we have

$\sum_{i=1}^{3}\left(d_{i,i}(v)+d_{i,i}(v^{\prime})\right)\leqslant\sum_{i=1}^{3}\left(\frac{1}{2}|V_{i}|^{2}+(t+4)n\right)\leqslant\frac{n^{2}}{5}.$

Thus, without loss of generality, we can assume that
$\sum_{i=1}^{3}d_{i,i}(v)\leqslant\frac{1}{10}n^{2}$. By (ii), we have

$d(v)=\sum_{i=1}^{3}d_{i,i}(v)+\sum_{1\leqslant i<j\leqslant
3}d_{i,j}(v)\leqslant\frac{1}{10}n^{2}+3cn^{2}<\frac{1}{9}n^{2}-n,$

contradicting the minimum degree assumption. ∎

####  3.2.2 Typical vertices

######  Lemma 3.9.

Let $t\geqslant 0$, $n$ be sufficiently large, and $H$ be an $F_{5}^{t}$-free
$3$-graph on vertex set $[n]$ with $|H|\geqslant s_{t}^{\circ}(n)$ and
$\delta(H)\geqslant\frac{1}{9}n^{2}-n$. Further, let $\pi=(V_{1},V_{2},V_{3})$
be a partition of $[n]$ maximizing $|H_{\pi}|$ and $c,A_{1},A_{2},A_{3}$ be
defined as above. The following statements hold.

  1. (i)

Let $\\{i,j,k\\}=[3]$. For every vertex $x\in A_{i}$, we have

    1. (a)

$d_{i,j}(x),d_{i,k}(x)\leqslant 3cn^{2}$,

    2. (b)

$d_{i,i}(x)\leqslant n^{3/2}$,

    3. (c)

$d_{j,j}(x),d_{k,k}(x)\leqslant cn^{2}$, and

    4. (d)

$d_{j,k}(x)\geqslant(\frac{1}{9}-10c)n^{2}$.

  2. (ii)

For $i\in[3]$ and every pair of distinct vertices $x,x^{\prime}\in A_{i}$, we
have $d(x,x^{\prime})\leqslant t$.

  3. (iii)

For $i\neq j\in[3]$ and vertices $x\in A_{i}$, $y\in A_{j}$, if
$d_{A_{i}}(x,y)+d_{A_{j}}(x,y)>0$, then we have $d_{A_{k}}(x,y)\leqslant
50cn$.

###### Proof of (i).

(a) follows from Claim 2.6 (iii). For (b), assume for contradiction that there
exists vertex $x\in A_{i}$ such that $d_{i,i}(x)>n^{3/2}$. Let
$S_{x}\coloneqq\\{x^{\prime}\in V_{i}:d_{i}(x,x^{\prime})\geqslant t+1\\}$.
Then

$n^{3/2}<d_{i,i}(x)\leqslant\frac{1}{2}\left(|S_{x}||V_{i}|+|V_{i}\setminus
S_{x}|\cdot t\right)\leqslant\frac{1}{2}\left(|S_{x}|n+tn\right),$

implying $|S_{x}|\geqslant n^{1/2}$. For every $x^{\prime}\in S_{x}$, by Lemma
3.1, we have $d_{j,k}(x)+d_{j,k}(x^{\prime})\leqslant|V_{j}||V_{k}|+(t+3)n$.
By the definition of $A_{i}$, we have $d_{j,k}(x)\geqslant cn^{2}$ and hence
$d_{j,k}(x^{\prime})\leqslant|V_{j}||V_{k}|+(t+3)n-cn^{2}\leqslant|V_{j}||V_{k}|-\frac{1}{2}cn^{2}$.
Thus,

$\displaystyle|\bar{H}_{\pi}|=\sum_{x^{\prime}\in
V_{i}}\left(|V_{j}||V_{k}|-d_{j,k}(x^{\prime})\right)\geqslant\sum_{x^{\prime}\in
S_{x}}\left(|V_{j}||V_{k}|-d_{j,k}(x^{\prime})\right)\geqslant|S_{x}|\cdot\frac{1}{2}cn^{2}\geqslant\frac{1}{2}cn^{\frac{5}{2}},$

contradicting Theorem 3.2. Next, we prove (c). For every $x\in V_{i}$, define
$W_{j}\coloneqq\\{y\in V_{j}:d_{j}(x,y)>n^{3/4}\\}$, $W_{k}\coloneqq\\{z\in
V_{k}:d_{k}(x,z)>n^{3/4}\\}$, $\widebar{W}_{j}\coloneqq V_{j}\setminus W_{j}$,
and $\widebar{W}_{k}\coloneqq V_{k}\setminus W_{k}$. By the definitions of
$W_{j}$ and $W_{k}$, we have

$d_{W_{j},\widebar{W}_{j}}(x),d_{\widebar{W}_{j},\widebar{W}_{j}}(x),d_{W_{k},\widebar{W}_{k}}(x),d_{\widebar{W}_{k},\widebar{W}_{k}}(x)\leqslant
n^{3/4}\cdot n\leqslant n^{7/4}.$

Further, for every $y\in W_{j}$, we have $d_{k}(x,y)\leqslant n^{3/4}$;
otherwise either there exist $y^{\prime}\in L_{j}(x,y)$ and $z\in L_{k}(x,y)$
satisfying $d_{i}(y^{\prime},z)\geqslant t+2$, and we find a copy of
$F_{5}^{t}$ in $H$; or for every $y^{\prime}\in L_{j}(x,y)$ and $z\in
L_{k}(x,y)$, it holds that $d_{i}(y^{\prime},z)<t+2$, in which case

$|\bar{H}_{\pi}|\geqslant d_{j}(x,y)d_{k}(x,y)(|V_{i}|-t-2)\geqslant
n^{3/2}(|V_{i}|-t-2),$

contradicting Theorem 3.2 by Claim 2.6 (i). We conclude
$d_{W_{j},W_{k}}(x),d_{W_{j},\widebar{W}_{k}}(x)\leqslant n^{7/4}$, and by a
similar argument also $d_{\widebar{W}_{j},W_{k}}(x)\leqslant n^{7/4}$.
Therefore,

$d_{j,j}(x)+d_{j,k}(x)+d_{k,k}(x)\leqslant\binom{|W_{j}|}{2}+(|V_{j}|-|W_{j}|)(|V_{k}|-|W_{k}|)+\binom{|W_{k}|}{2}+7n^{7/4}.$
(2)

On the other hand, by (a), (b), and the minimum degree assumption, we have

$d_{j,j}(x)+d_{j,k}(x)+d_{k,k}(x)\geqslant
d(x)-d_{i,i}(x)-d_{i,j}(x)-d_{i,k}(x)\geqslant\left(\frac{1}{9}-7c\right)n^{2}.$
(3)

Combining (2) and (3) and using Claim 2.6 (i), we get

$\frac{1}{2}|W_{j}|^{2}+\left(\left(\frac{1}{3}+6c\right)n-|W_{j}|\right)\left(\left(\frac{1}{3}+6c\right)n-|W_{k}|\right)+\frac{1}{2}|W_{k}|^{2}\geqslant\left(\frac{1}{9}-8c\right)n^{2},$

which implies $|W_{j}|+|W_{k}|\leqslant 50cn$ or
$|W_{j}|+|W_{k}|\geqslant(\frac{2}{3}-38c)n$. If
$|W_{j}|+|W_{k}|\geqslant(\frac{2}{3}-38c)n$, then by the definition of
$A_{i}$, we have

$\displaystyle cn^{2}$
$\displaystyle<d_{j,k}(x)=d_{\widebar{W}_{j},\widebar{W}_{k}}(x)+d_{W_{j},\widebar{W}_{k}}(x)+d_{\widebar{W}_{j},W_{k}}(x)+d_{W_{j},W_{k}}(x)$
$\displaystyle\leqslant\left(\left(\frac{1}{3}+6c\right)n-|W_{j}|\right)\left(\left(\frac{1}{3}+6c\right)n-|W_{k}|\right)+3n^{7/4}$
$\displaystyle\leqslant\left(25cn\right)^{2}+3n^{7/4}<cn^{2},$

a contradiction. We conclude $|W_{j}|,|W_{k}|\leqslant 50cn$ and thus

$d_{j,j}(x)=d_{W_{j},W_{j}}(x)+d_{W_{j},\widebar{W}_{j}}(x)+d_{\widebar{W}_{j},\widebar{W}_{j}}(x)\leqslant\binom{50cn}{2}+2n^{7/4}\leqslant
cn^{2}.$

Similarly, $d_{k,k}(x)\leqslant cn^{2}$. Finally, (d) follows by the minimum
degree assumption, (a), (b), and (c). ∎

###### Proof of (ii).

If $x,x^{\prime}\in A_{i}$ are distinct vertices such that
$d(x,x^{\prime})\geqslant t+1$, then by Lemma 3.1,
$d_{j,k}(x)+d_{j,k}(x^{\prime})\leqslant|V_{j}||V_{k}|+(t+3)n\leqslant\frac{1}{8}n^{2}$.
This contradicts (d) in (i). ∎

###### Proof of (iii).

Fix vertex $v\in A_{i}\cup A_{j}$ such that $xyv\in H$. Without loss of
generality, we assume $v\in A_{i}$. By (i) and Lemma 3.8 (i), we have

$\displaystyle d_{A_{j},A_{k}}(v)\geqslant
d_{j,k}(v)-d_{B_{j},V_{k}}(v)-d_{V_{j},B_{k}}(x)\geqslant
d_{j,k}(v)-t|V_{i}|-t|V_{j}|\geqslant\left(\frac{1}{9}-11c\right)n^{2}.$ (4)

For every $z\in L_{A_{k}}(x,y)$, we have $d_{A_{j}}(v,z)\leqslant t+1$;
otherwise there exist $y_{1},\ldots,y_{t+1}\in A_{j}\setminus\\{y\\}$ and then
hyperedges $\\{xyv,xyz,vzy_{1},\ldots,vzy_{t+1}\\}$ form a copy of $F_{5}^{t}$
in $H$. Therefore,

$\displaystyle d_{A_{j},A_{k}}(v)$
$\displaystyle\leqslant(t+1)d_{A_{k}}(x,y)+|A_{j}|\left(|A_{k}|-d_{A_{k}}(x,y)\right).$
(5)

Combining (4) with (5) and Claim 2.6 (i), we get $d_{A_{k}}(x,y)\leqslant
50cn$. ∎

###  3.3 All vertices are typical

######  Theorem 3.10.

Let $t\geqslant 0$, $n$ be sufficiently large, and $H$ be an $F_{5}^{t}$-free
$3$-graph on vertex set $[n]$ with $|H|\geqslant s_{t}^{\circ}(n)$ and
$\delta(H)\geqslant\frac{1}{9}n^{2}-n$. Further, let $\pi=(V_{1},V_{2},V_{3})$
be a partition of $[n]$ maximizing $|H_{\pi}|$, and let $B$ be defined as in
Section 3.2. Then, $|B|=0$.

Let $c$, $A_{1}$, $A_{2}$, $A_{3}$, $A$, $B_{1}$, $B_{2}$, and $B_{3}$ be
defined as in Section 3.2. We write $\varpi$ for the $3$-partition with parts
$(A_{1},A_{2},A_{3})$, and let $A_{4}:=B$. For $i,j,k\in[4]$, define $H_{ijk}$
to be the set of hyperedges $xyz\in H$ where $x\in A_{i}$, $y\in A_{j}$, and
$z\in A_{k}$. Further, define $H_{bad}\coloneqq\bigcup_{i,j\in[3],\ i\neq
j}H_{iij}$. Then,

$|H|=|H_{123}|+\sum_{i=1}^{3}|H_{iii}|+|H_{bad}|+\sum_{1\leqslant i\leqslant
j\leqslant 3}|H_{ij4}|+\sum_{i=1}^{4}|H_{i44}|.$ (6)

Recall that we defined $H_{\varpi}=H_{123}$ and
$\bar{H}_{\varpi}=K_{\varpi}\setminus H_{\varpi}$ in Section 2.1. Note that
$H_{\varpi}\subseteq H_{\pi}$ and $\bar{H}_{\varpi}\subseteq\bar{H}_{\pi}$.
For $i\in[3]$, by Claim 2.6 (i) and Lemma 3.8 (i), we have

$\displaystyle\left(\frac{1}{3}-3c\right)n-t\leqslant\left(\frac{1}{3}-3c\right)n-|B|\leqslant|A_{i}|\leqslant|V_{i}|\leqslant\left(\frac{1}{3}+6c\right)n.$
(7)

For $i\neq j\in[3]$, let $G_{ij}$ be an auxiliary bipartite graph on
$A_{i}\cup A_{j}$, where there is an edge between $x\in A_{i}$ and $y\in
A_{j}$ iff there exists a vertex $v\in(A_{i}\cup A_{j})$ such that $xyv\in H$.
Denote by $d_{G_{ij}}(x)$ the degree of vertex $x$ in $G_{ij}$.

###### Proof of Theorem 3.10.

The proof is split into several claims.

######  Claim 3.11.

$|H_{bad}|\leqslant 12tc^{1/2}n^{2}$.

###### Proof.

We bound $|H_{ijj}|$ for every $i\neq j\in[3]$. For every $xy\in G_{ij}$, by
Lemma 3.9 (iii), we have $d_{A_{k}}(x,y)\leqslant 50cn$. By Theorem 3.2, we
have

$|G_{ij}|\left(|A_{k}|-50c\right)\leqslant|\bar{H}_{\varpi}|\leqslant|\bar{H}_{\pi}|\leqslant\left(\frac{1}{9}+c\right)tn^{2},$

implying $|G_{ij}|\leqslant tn$ by (7). We partition $A_{i}=S\cup T$, where
$S$ is the set of vertices $x\in A_{i}$ satisfying $d_{G_{ij}}(x)>c^{1/2}n$
and $T:=A_{i}\setminus S$. Since $|G_{ij}|\leqslant tn$, we have $|S|\leqslant
tc^{-1/2}$. By Lemma 3.9 (i), we have $d_{A_{j},A_{j}}(x)\leqslant
d_{j,j}(x)\leqslant cn^{2}$ for every $x\in S$. Therefore, the number of
hyperedges in $H_{ijj}$ containing a vertex in $S$ is at most $tc^{1/2}n^{2}$.
The number of hyperedges in $H_{ijj}$ containing a vertex in $T$ is at most

$\sum_{x\in T}\binom{d_{G_{ij}}(x)}{2}\leqslant\sum_{x\in
T}d_{G_{ij}}^{2}(x)\leqslant c^{1/2}n\sum_{x\in T}d_{G_{ij}}(x)\leqslant
c^{1/2}n|G_{ij}|\leqslant tc^{1/2}n^{2}.$

We conclude $|H_{ijj}|\leqslant 2tc^{1/2}n^{2}$ and thus $|H_{bad}|\leqslant
12tc^{1/2}n^{2}$. ∎

######  Claim 3.12.

For every vertex $v\in B$, we have
$d_{A_{i},A_{i}}(v)\geqslant\binom{|A_{i}|}{2}-c^{1/3}n^{2}$ for $i\in[3]$.

###### Proof.

Assume that there exist vertex $v\in B$ and $k\in[3]$ such that
$d_{A_{k},A_{k}}(v)<\binom{|A_{k}|}{2}-c^{1/3}n^{2}$. Then, for every
$i\in[3]$,

$|H_{ii4}|\leqslant|B|\binom{|A_{i}|}{2}-\mathbbm{1}_{\\{i=k\\}}c^{1/3}n^{2}\quad\text{and}\quad
3|H_{iii}|+|H_{ii4}|\leqslant t\binom{|A_{i}|}{2},$

where the second inequality holds by Lemma 3.9 (ii). Combining these two
inequalities, we get

$\displaystyle\sum_{i=1}^{3}(|H_{iii}|+|H_{ii4}|)\leqslant\left(\frac{t}{3}+\frac{2|B|}{3}\right)\left(\sum_{i=1}^{3}\binom{|A_{i}|}{2}\right)-\frac{2}{3}c^{1/3}n^{2}\leqslant\frac{t}{18}n^{2}+\frac{|B|}{9}n^{2}-\frac{1}{2}c^{1/3}n^{2},$
(8)

where the last inequality holds by (7). Now we have

$\displaystyle|H_{123}|\leqslant|A_{1}||A_{2}||A_{3}|\leqslant\left(\frac{n-|B|}{3}\right)^{3}=\frac{1}{27}n^{3}-\frac{1}{9}|B|n^{2}+\frac{1}{9}|B|^{2}n-\frac{1}{27}|B|^{3},$
(9) $\displaystyle\sum_{1\leqslant i<j\leqslant 3}|H_{ij4}|\leqslant|B|\cdot
3cn^{2}\leqslant 3tcn^{2}\quad\text{by Lemma~{}\ref{lem::B} (i)
(ii),}\quad\text{and}$ (10)
$\displaystyle\sum_{i=1}^{4}|H_{i44}|\leqslant\binom{|B|}{2}t\leqslant
t^{3}\quad\text{by Lemma~{}\ref{lem::B} (i) (iii).}$ (11)

Combining (6), (8), (9), (10), (11), and Claim 3.11, we get

$|H|\leqslant\frac{1}{27}n^{3}+\left(\frac{1}{18}t-\frac{1}{3}c^{1/3}\right)n^{2}<s_{t}^{\circ}(n),$

a contradiction. ∎

######  Claim 3.13.

For vertex $v\in B$ and $i\in[3]$, let $S_{v,i}\coloneqq\\{x\in
A_{i}:d_{A_{i}}(v,x)\leqslant t+2\\}$. Then $|S_{v,i}|\leqslant 10c^{1/3}n$.

###### Proof.

By the definition of $S_{v,i}$ and Claim 3.12,

$\binom{|A_{i}|-|S_{v,i}|}{2}+|S_{v,i}|(t+2)\geqslant
d_{A_{i},A_{i}}(v)\geqslant\binom{|A_{i}|}{2}-c^{1/3}n^{2},$

so $|S_{v,i}|\leqslant 10c^{1/3}n$, where we also use (7). ∎

######  Claim 3.14.

If $|B|\geqslant 1$, then $|H_{iii}|\leqslant(t+1)c^{1/3}n^{2}$ for $i\in[3]$.

###### Proof.

Let $v\in B$ and $i\in[3]$. By Claim 3.13, $|S_{v,i}|\leqslant 10c^{1/3}n$.
For every $xx^{\prime}x^{\prime\prime}\in H_{iii}$ where $x^{\prime\prime}\in
A_{i}\setminus S_{v,i}$, we have $xx^{\prime}\notin L_{A_{i},A_{i}}(v)$;
otherwise there exist distinct vertices $x_{1},\ldots,x_{t+1}\in
L_{A_{i}}(v,x^{\prime\prime})\setminus\\{x,x^{\prime}\\}$, and the hyperedges
$\\{xx^{\prime}v,xx^{\prime}x^{\prime\prime}$,
$vx^{\prime\prime}x_{1},\ldots,vx^{\prime\prime}x_{t+1}\\}$ form an
$F_{5}^{t}$ in $H$, a contradiction. By Lemma 3.9 (ii), every pair in $A_{i}$
has codegree at most $t$. By Claim 3.12, there are at most
$\left(\binom{|A_{i}|}{2}-d_{A_{i},A_{i}}(v)\right)t\leqslant tc^{1/3}n^{2}$
hyperedges in $H_{iii}$ containing at least one vertex in $A_{i}\setminus
S_{v,i}$. There are at most $\binom{|S_{v,i}|}{2}t\leqslant c^{1/3}n^{2}$
hyperedges in $H_{iii}$ containing three vertices in $S_{v,i}$. Therefore,
$|H_{iii}|\leqslant(t+1)c^{1/3}n^{2}$. ∎

######  Claim 3.15.

$|B|\notin[1,t-1]$.

###### Proof.

Assume $|B|\in[1,t-1]$. By Claim 3.14, $\sum_{i=1}^{3}|H_{iii}|\leqslant
3(t+1)c^{1/3}n^{2}$. By (7),
$\sum_{i=1}^{3}|H_{ii4}|\leqslant|B|\sum_{i=1}^{3}\binom{|A_{i}|}{2}\leqslant|B|(\frac{1}{6}+7c)n^{2}$.
Then, by (6), (9), (10), (11), and Claim 3.11, we get

$\displaystyle|H|\leqslant\frac{n^{3}}{27}+\frac{|B|n^{2}}{18}+0.01n^{2}<s_{t}^{\circ}(n),$

a contradiction. ∎

######  Claim 3.16.

$|B|\neq t$.

###### Proof.

Assume $|B|=t$. By Lemma 3.9 (ii), we have

$\displaystyle\sum_{i=1}^{3}|H_{iii}|+|H_{bad}|+\sum_{i=1}^{3}|H_{ii4}|\leqslant
t\sum_{i=1}^{3}\binom{|A_{i}|}{2}.$ (12)

If $\sum_{1\leqslant i<j\leqslant 3}|H_{ij4}|\leqslant\frac{n}{11}$, then by
(6), (11), (12), and Lemma 2.4,

$|H|\leqslant|A_{1}||A_{2}||A_{3}|+t\sum_{i=1}^{3}\binom{|A_{i}|}{2}+\frac{n}{11}+t^{3}\leqslant
s_{t,\varpi}^{\triangle}(n)+\frac{n}{10}<s_{t}^{\circ}(n),$

a contradiction. Hence, $\sum_{1\leqslant i<j\leqslant
3}|H_{ij4}|>\frac{n}{11}$, so there exist $v\in B$ and $i\neq j\in\\{1,2,3\\}$
such that $d_{A_{i},A_{j}}(v)\geqslant\frac{n}{33t}$. For every $x\in
A_{i},y\in A_{j}$ with $xyv\in H$ and every $z\in L_{A_{k}}(x,y)$, we have
$d_{A_{k}}(v,z)<t+1$; otherwise there exist distinct vertices
$z_{1},\ldots,z_{t+1}\in L_{A_{k}}(v,z)$, and then hyperedges
$\\{xyv,xyz,vzz_{1},\ldots,vzz_{t+1}\\}$ form a copy of $F_{5}^{t}$ in $H$, a
contradiction. By Claim 3.13, $d_{A_{k}}(x,y)\leqslant|S_{v,k}|\leqslant
10c^{1/3}n$. Thus,
$|\bar{H}_{\varpi}|\geqslant\frac{n}{33t}(|A_{k}|-10c^{1/3}n)$.

Let $\\{i,j,k\\}=[3]$. For every vertex $v\in B_{i}$, by Lemma 3.8 (ii), there
are at least $|A_{j}||A_{k}|-cn^{2}$ missing crossing hyperedges in
$\bar{H}_{\pi}$ containing $v$ and two vertices in $A$. By (7), we conclude

$|\bar{H}_{\pi}|\geqslant|\bar{H}_{\varpi}|+t\left(\left(\frac{1}{3}n-3cn-t\right)^{2}-cn^{2}\right)>\left(\frac{t}{9}+\frac{1}{100t}\right)n^{2}>\left(\frac{1}{9}+c\right)tn^{2},$

contradicting Theorem 3.2. ∎

By Lemma 3.8 (i) and Claims 3.15 and 3.16, $|B|=0$. ∎

###  3.4 Proof of Theorem 1.1 with a minimum degree assumption

######  Theorem 3.17.

For every $t\geqslant 0$ and sufficiently large $n$, let $H$ be a $3$-graph on
vertex set $[n]$ with maximum number of hyperedges among the $n$-vertex
$F_{5}^{t}$-free $3$-graphs satisfying $\delta(H)\geqslant\frac{1}{9}n^{2}-n$.
Then, $H\in\mathcal{S}_{t}^{\circ}(n)$.

###### Proof.

Let $\pi=(V_{1},V_{2},V_{3})$ be a partition of $[n]$ maximizing $|H_{\pi}|$,
and let $c$, $A_{1}$, $A_{2}$, $A_{3}$, $B$ be defined as in Section 3.2. Note
that
$\delta(S_{t}^{\circ}(n))\geqslant\delta(S(n))\geqslant\frac{1}{9}n^{2}-n$, so
$|H|\geqslant s_{t}^{\circ}(n)$. By Theorem 3.10, $|B|=0$, and hence
$V_{i}=A_{i}$ for $i\in[3]$. We will prove $H_{bad}=\varnothing$. Without loss
of generality, we assume
$|H_{112}|+|H_{221}|\geqslant|H_{113}|+|H_{331}|\geqslant|H_{223}|+|H_{332}|$.

######  Claim 3.18.

If $|H_{bad}|\geqslant 1$, then $|G_{12}|>\frac{1}{4}n^{1/2}$.

###### Proof.

By Lemma 2.3, we have $|H|\geqslant s_{t}^{\circ}(n)\geqslant
s_{t,\pi}^{\circ}(n)$, and hence,

$\sum_{i=1}^{3}|H_{iii}|+|H_{bad}|=|H\setminus
H_{\pi}|\geqslant|\bar{H}_{\pi}|+\sum_{i=1}^{3}\mathrm{ex}(|V_{i}|,F_{2}^{t}).$
(13)

For $i\in[3]$, by Lemma 3.9 (ii), every pair of distinct vertices in $A_{i}$
has codegree at most $t$, so
$|H_{iii}|\leqslant\mathrm{ex}(|V_{i}|,F_{2}^{t})$. Hence, we have
$|H_{bad}|\geqslant|\bar{H}_{\pi}|$. By (7) and Lemma 3.9 (iii), we have

$|\bar{H}_{\pi}|\geqslant|G_{12}|\cdot\left(\frac{1}{3}-3c-50c\right)n.$ (14)

If $|H_{bad}|\geqslant 1$, then $|H_{112}|+|H_{221}|\geqslant 1$ and hence
$|G_{12}|\geqslant 1$ by the definition of $G_{12}$. we have

$2\binom{|G_{12}|}{2}\geqslant|H_{112}|+|H_{221}|\geqslant\frac{1}{3}|H_{bad}|\geqslant\frac{1}{3}|\bar{H}_{\pi}|\geqslant\frac{1}{3}\left(\frac{1}{3}-53c\right)n,$

implying $|G_{12}|>\frac{1}{4}n^{1/2}$. ∎

######  Claim 3.19.

If $|H_{bad}|\geqslant 1$, then there exist $x_{0}\in V_{1}$, $y_{0}\in V_{2}$
such that $d_{G_{12}}(x_{0})+d_{G_{12}}(y_{0})\geqslant(\frac{1}{3}-54c)n$.

###### Proof.

By Lemma 3.9 (ii),

$3|H_{iii}|+|H_{iij}|+|H_{iik}|\leqslant t\binom{|V_{i}|}{2}\quad\textrm{for
$\\{i,j,k\\}=[3]$.}$ (15)

By the definition of $G_{12}$,

$|H_{iij}|+|H_{jji}|\leqslant|H_{112}|+|H_{221}|\leqslant\sum_{x\in
V_{1}}\binom{d_{G_{12}}(x)}{2}+\sum_{y\in
V_{2}}\binom{d_{G_{12}}(y)}{2}\quad\textrm{for $i\neq j\in[3]$.}$ (16)

Combining (15) and (16), we have

$\displaystyle\sum_{i=1}^{3}|H_{iii}|+|H_{bad}|$
$\displaystyle\leqslant\frac{1}{3}t\sum_{i=1}^{3}\binom{|V_{i}|}{2}+\frac{2}{3}\cdot
3\left(\sum_{x\in V_{1}}\binom{d_{G_{12}}(x)}{2}+\sum_{y\in
V_{2}}\binom{d_{G_{12}}(y)}{2}\right)$
$\displaystyle\leqslant\sum_{i=1}^{3}\mathrm{ex}(|V_{i}|,F_{2}^{t})+\frac{n}{3}+\frac{t^{2}}{2}+9t+\sum_{x\in
V_{1}}d_{G_{12}}^{2}(x)+\sum_{y\in V_{2}}d_{G_{12}}^{2}(y),$ (17)

where for the last inequality, we use the lower bound on
$\mathrm{ex}(m,F_{2}^{t})$ from Proposition 2.1. By (13) and (17),

$\sum_{\\{x,y\\}\in G_{12}}(d_{G_{12}}(x)+d_{G_{12}}(y))=\sum_{x\in
V_{1}}d_{G_{12}}^{2}(x)+\sum_{y\in
V_{2}}d_{G_{12}}^{2}(y)\geqslant|\bar{H}_{\pi}|-\frac{n}{3}-\frac{t^{2}}{2}-9t.$
(18)

Using (14) and (18), we get

$\sum_{\\{x,y\\}\in
G_{12}}(d_{G_{12}}(x)+d_{G_{12}}(y))\geqslant|G_{12}|\left(\frac{1}{3}-53c\right)n-\frac{n}{3}-\frac{t^{2}}{2}-9t\geqslant|G_{12}|\left(\frac{1}{3}-54c\right)n,$

where the last inequality holds by Claim 3.18. By the pigeon-hole principle,
there exist $x_{0}\in V_{1}$, $y_{0}\in V_{2}$ such that
$d_{G_{12}}(x_{0})+d_{G_{12}}(y_{0})\geqslant(\frac{1}{3}-54c)n$. ∎

######  Claim 3.20.

$H_{bad}=\varnothing$.

###### Proof.

Assume for contradiction that $|H_{bad}|\geqslant 1$. By Claim 3.19, we can
assume that there exists $x_{0}\in V_{1}$ such that
$d_{G_{12}}(x_{0})\geqslant(\frac{1}{6}-27c)n$. By (7) and Lemma 3.9 (iii),
$x_{0}$ is contained in at least
$(\frac{1}{6}-27c)n\cdot(\frac{1}{3}-53c)n>\frac{1}{20}n^{2}$ missing crossing
hyperedges, contradicting Lemma 3.9 (i). Hence, $H_{bad}=\varnothing$. ∎

By Claim 3.20 and Lemmas 3.9 (ii) and 2.3, we get $|H|\leqslant
s_{t,\pi}^{\circ}(n)\leqslant s_{t}^{\circ}(n)$, where equality holds iff
$H\in\mathcal{S}_{t}^{\circ}(n)$. ∎

###  3.5 Proof of Theorem 1.1

###### Theorem 3.17 $\Rightarrow$ Theorem 1.1.

Assume that the statement of Theorem 1.1 does not hold. Then, for some
$t\geqslant 0$, there exist infinitely many positive integers $n$ such that
there exists an $n$-vertex $F_{5}^{t}$-free hypergraph
$H_{n}\notin\mathcal{S}_{t}^{\circ}(n)$ with $|H_{n}|\geqslant
s_{t}^{\circ}(n)$. Choose a sufficiently large $n$ among them. If $H_{n}$
contains a vertex $v$ with degree less than $\frac{1}{9}n^{2}-n$, let
$H_{n-1}=H_{n}-v$. Repeat this process until there is no such low-degree
vertex. We obtain a sequence of hypergraphs $H_{n},H_{n-1},\ldots$, where
$H_{m}$ is obtained from $H_{m+1}$ by deleting a vertex in $H_{m+1}$ with
degree less than $\frac{1}{9}(m+1)^{2}-(m+1)$. Note that we have
$|H_{n-l}|\geqslant s_{t}^{\circ}(n-l)+l$, since
$s_{t}^{\circ}(m)-s_{t}^{\circ}(m-1)>\frac{1}{9}m^{2}-m$ for sufficiently
large $m$ by Lemma 2.2. This sequence is finite and ends with more than
$n_{0}=\frac{1}{100}n^{1/3}$ vertices remaining; otherwise there would be at
least $n-n_{0}>\binom{n_{0}}{3}$ hyperedges in $H_{n_{0}}$. When the process
ends, we reach an $\hat{n}$-vertex $F_{5}^{t}$-free $3$-graph $H_{\hat{n}}$,
where $\hat{n}>n_{0}$, $|H_{\hat{n}}|>s_{t}^{\circ}(\hat{n})$, and the minimum
degree of $H_{\hat{n}}$ is at least $\frac{1}{9}\hat{n}^{2}-\hat{n}$.

Now taking $n$ to infinity, we have that there are infinitely many integers
$m$ such that there exists an $m$-vertex $F_{5}^{t}$-free $3$-graph $H_{m}$
with $|H_{m}|>s_{t}^{\circ}(m)$ and
$\delta(H_{m})\geqslant\frac{1}{9}m^{2}-m$, contradicting Theorem 3.17. ∎

##  4 Concluding Remarks

Recall that $S(n)$ denotes the complete tripartite $3$-graph on vertex set
$[n]$ and $s(n)=|S(n)|$. An interesting question is to determine all
$3$-graphs $H$ with $\mathrm{ex}(n,H)=s(n)$ for sufficiently large $n$.
However, this seems to be rather difficult. A more approachable question is
the following one. Recall that we write $F_{5}[t]$ for the $t$-blow-up of
$F_{5}$. For $t\geqslant 1$, let $\mathcal{H}^{t}$ be the family of $3$-graphs
$F$ such that $F_{5}\subseteq F\subseteq F_{5}[t]$.

######  Question 4.1.

For which $F\in\mathcal{H}^{t}$ does $\mathrm{ex}(n,F)=s(n)$ hold for
sufficiently large $n$?

Let $S^{\prime}(m)$ be the $3$-graph obtained from $S(m)$ by adding a
hyperedge containing three vertices in $V_{1}$, see Figure 7. Let
$S^{\prime\prime}(m)$ be the $3$-graph obtained from $S(m)$ by adding a
hyperedge containing two vertices in $V_{1}$ and one vertex in $V_{2}$, see
Figure 7. Inspired by Simonovits’s result [22] about critical graphs, one may
have the natural guess that $\mathrm{ex}(n,F)=s(n)$ for sufficiently large $n$
iff $F\subseteq S^{\prime}(m)$ and $F\subseteq S^{\prime\prime}(m)$ for some
$m\geqslant 1$. This assumption is necessary, since
$|S^{\prime}(n)|=|S^{\prime\prime}(n)|=s(n)+1$. However, it is not sufficient,
as shown by the following example.

$\vdots$$x_{1}$$x_{2}$$x_{3}$$V_{1}$$V_{2}$$V_{3}$ Figure 6: Hypergraph
$S^{\prime}(m)$.

$\vdots$$x_{1}$$x_{2}$$y_{1}$$V_{1}$$V_{2}$$V_{3}$ Figure 7: Hypergraph
$S^{\prime\prime}(m)$.

Let $\hat{F}$ be the $3$-graph with vertex set

$\\{1,2,3,4,5\\}\cup\\{c_{12},c_{23},c_{31}\\}\cup\bigcup_{\begin{subarray}{c}l=1,2\\\
i=1,2,3\end{subarray}}\\{a_{i}^{l},b_{i}^{l}\\}$

and hyperedge set

$\\{123,124,345\\}\cup\\{c_{12}b_{1}^{2}a_{2}^{2},c_{23}b_{2}^{2}a_{3}^{2},c_{31}b_{3}^{2}a_{1}^{2}\\}\cup\bigcup_{i=1,2,3}\\{5a_{i}^{1}b_{i}^{1},5a_{i}^{1}b_{i}^{2},5a_{i}^{2}b_{i}^{1},5a_{i}^{2}b_{i}^{2}\\},$

see Figure 8. Hence, the $3$-graph $\hat{F}$ contains $F_{5}$ and other
hyperedges such that the link graph of vertex $5$ contains three extra
disjoint complete bipartite graphs on
$\\{a_{i}^{1},a_{i}^{2}\\}\cup\\{b_{i}^{1},b_{i}^{2}\\}$. Besides, there are
three vertices $c_{12},c_{23},c_{31}$ connecting these three complete
bipartite graphs.

$\vdots$$1$$2$$3$$4$$5$${a^{1}_{1}}$$a^{2}_{1}$$b^{1}_{1}$$b^{2}_{1}$$c_{12}$$a^{1}_{2}$$a^{2}_{2}$$b^{1}_{2}$$b^{2}_{2}$$c_{23}$$a^{1}_{3}$$a^{2}_{3}$$b^{1}_{3}$$b^{2}_{3}$$c_{31}$
Figure 8: Hypergraph $\hat{F}$.

######  Claim 4.2.

We have $F_{5}\subseteq\hat{F}\subseteq F_{5}[7]$, $\hat{F}\subseteq
S^{\prime}(30),S^{\prime\prime}(30)$, and $\mathrm{ex}(n,\hat{F})>s(n)$ for
sufficiently large $n$.

###### Proof.

The first two claims hold by the definition of $\hat{F}$. For the third claim,
let $\hat{S}(n)$ be the $3$-graph obtained from $S(n-1)$ by adding a new
vertex $v$ and adding hyperedges such that $L_{1,1}(v)$ and $L_{2,2}(v)$ are
complete graphs $K_{|V_{1}|}$ and $K_{|V_{2}|}$ respectively, and $L_{3,3}(v)$
is an extremal $K_{2,2}$-free graph. We have $|\hat{S}(n)|>s(n)$ for
sufficiently large $n$, since $\mathrm{ex}(n,K_{2,2})\geqslant cn^{3/2}$ for
some constant $c>0$ by Erdős, Rényi, and Sós [4]. If there exists a copy of
$\hat{F}$ in $\hat{S}(n)$, then the vertex in $\hat{S}(n)$ corresponding to
vertex $5$ in $\hat{F}$ can only be the new vertex $v$, and then
$\\{a_{i}^{1},a_{i}^{2},b_{i}^{1},b_{i}^{2}\\}$ is in different parts of the
partition of $\hat{S}(n)$ for different $i$. However, $L_{3,3}(v)$ is
$K_{2,2}$-free, a contradiction. ∎

We have the following sufficient condition for Question 4.1. Let $S^{+}(m)$ be
the $3$-graph obtained from $S(m-1)$ by adding a new vertex $v$ and a
hyperedge containing $v$ and two vertices in $V_{1}$, see Figure 10. Note that
$S^{+}(m)\subseteq S^{\prime}(m+3),S^{\prime\prime}(m+3)$. Using a cleaning
method similar to the one in Section 3, we can prove the following claim; we
omit its proof.

######  Claim 4.3.

For $3$-graph $F\in\mathcal{H}^{t}$, if $F\subseteq S^{+}(m)$ for some
$m\geqslant 1$, then $\mathrm{ex}(n,F)=s(n)$ for sufficiently large $n$.

However, this is not a complete answer to Question 4.1, due to the following
example. Let $F_{5}^{\prime}$ be the $3$-graph on vertex set
$\\{1,2,3,3^{\prime},4,4^{\prime},5\\}$ with hyperedges
$\\{123,124,345,3^{\prime}4^{\prime}5\\}$, see Figure 10.

$\vdots$$x_{1}$$x_{2}$$v$$V_{1}$$V_{2}$$V_{3}$ Figure 9: Hypergraph
$S^{+}(m+1)$.

$\vdots$$1$$2$$3$$4$$5$$3^{\prime}$$4^{\prime}$ Figure 10: Hypergraph
$F^{\prime}_{5}$.

######  Claim 4.4.

We have $F_{5}\subseteq F_{5}^{\prime}\subseteq F_{5}[2]$, $F_{5}^{\prime}$ is
not a subhypergraph of $S^{+}(m)$ for any $m\geqslant 1$, and
$\mathrm{ex}(n,F_{5}^{\prime})=s(n)$ for every sufficiently large $n$.

###### Proof.

The first claim holds by the definition of $F_{5}^{\prime}$. Assume that
$S^{+}(m)$ contains a copy of $F_{5}^{\prime}$. Then, only the new vertex $v$
in $S^{+}(m)$ can be the vertex $5$ in $F_{5}^{\prime}$. However, vertex $5$
has degree two in $F_{5}^{\prime}$ while $v$ has degree one in $S^{+}(m)$, a
contradiction.

Trivially, we have
$\mathrm{ex}(n,F_{5}^{\prime})\geqslant\mathrm{ex}(n,F_{5})\geqslant s(n)$.
For the other direction, using a similar argument as in Section 3.5, we can
assume that the extremal $F_{5}^{\prime}$-free $3$-graph has minimum degree at
least $\frac{1}{9}n^{2}-n$. For every $n$-vertex $3$-graph $H$ with
$|H|>s(n)$, by Theorem 1.1, $H$ contains a copy of $F_{5}$. Let this copy be
$\\{v_{1}v_{2}v_{3},v_{1}v_{2}v_{4},v_{3}v_{4}v_{5}\\}$. By the minimum degree
assumption, $v_{5}$ is contained in a hyperedge $e$ that does contain any
$v_{i}$ for $i\in[4]$. Now,
$\\{v_{1}v_{2}v_{3},v_{1}v_{2}v_{4},v_{3}v_{4}v_{5},e\\}$ forms a copy of
$F_{5}^{\prime}$. Therefore, $\mathrm{ex}(n,F_{5}^{\prime})=s(n)$ for every
sufficiently large $n$. ∎

##### Acknowledgments.

We are very grateful to Xizhi Liu, Dhruv Mubayi, and Oleg Pikhurko for many
helpful comments on our work. This project started as an IGL 2021 Summer
program. The undergraduate students Junsheng Liu, Alexander Roe, Yuzhou Wang,
and Zihan Zhou took part in the initial discussions. During Summer 2021,
Alexander Roe was partially supported by RTG NSF grant DMS-1937241.

## References

  * [1] B. Bollobás.  Three-graphs without two triples whose symmetric difference is contained in a third.  Discrete Math., 8:21–24, 1974.
  * [2] W. G. Brown.  On an open problem of Paul Turán concerning $3$-graphs.  In Studies in pure mathematics, pages 91–93. Birkhäuser, Basel, 1983.
  * [3] M. Dehon.  On the existence of $2$-designs $S_{\lambda}(2,\,3,\,v)$ without repeated blocks.  Discrete Math., 43(2–3):155–171, 1983.
  * [4] 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.
  * [5] P. Erdős and M. Simonovits.  A limit theorem in graph theory.  Studia Sci. Math. Hungar., 1:51–57, 1966.
  * [6] P. Erdős and M. Simonovits.  An extremal graph problem.  Acta Math. Acad. Sci. Hungar., 22:275–282, 1971/72.
  * [7] P. Erdős and A. H. Stone.  On the structure of linear graphs.  Bull. Amer. Math. Soc., 52:1087–1091, 1946.
  * [8] D. G. Fon-Der-Flaass.  A method for constructing $(3,4)$-graphs.  Mat. Zametki, 44(4):546–550, 559, 1988.
  * [9] P. Frankl and Z. Füredi.  A new generalization of the Erdős-Ko-Rado theorem.  Combinatorica, 3(3-4):341–349, 1983.
  * [10] A. Frohmader.  More constructions for Turán’s $(3,4)$-conjecture.  Electron. J. Combin., 15(1):Research Paper 137, 23, 2008.
  * [11] S. Glock, D. Kühn, A. Lo, and D. Osthus.  The existence of designs via iterative absorption: hypergraph $F$-designs for arbitrary $F$.  arXiv:1611.06827, 2016.
  * [12] W. T. Gowers.  Hypergraph regularity and the multidimensional Szemerédi theorem.  Ann. of Math. (2), 166(3):897–946, 2007.
  * [13] J. Hou, H. Li, X. Liu, D. Mubayi, and Y. Zhang.  Hypergraphs with infinitely many extremal constructions.  arXiv:2206.03948, 2022.
  * [14] 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.
  * [15] P. Keevash.  Counting designs.  J. Eur. Math. Soc. (JEMS), 20(4):903–927, 2018.
  * [16] P. Keevash and D. Mubayi.  Stability theorems for cancellative hypergraphs.  J. Combin. Theory Ser. B, 92(1):163–175, 2004.
  * [17] A. V. Kostochka.  A class of constructions for Turán’s $(3,\,4)$-problem.  Combinatorica, 2(2):187–192, 1982.
  * [18] X. Liu and D. Mubayi.  A hypergraph Turán problem with no stability.  Combinatorica, Feb 2022.
  * [19] X. Liu, D. Mubayi, and C. Reiher.  Hypergraphs with many extremal configurations.  arXiv:2102.02103, 2021.
  * [20] A. A. Razborov.  On the Fon-der-Flaass interpretation of extremal examples for Turán’s $(3,4)$-problem.  Tr. Mat. Inst. Steklova, 274(Algoritmicheskie Voprosy Algebry i Logiki):269–290, 2011.
  * [21] V. Rödl, B. Nagle, J. Skokan, M. Schacht, and Y. Kohayakawa.  The hypergraph regularity method and its applications.  Proc. Natl. Acad. Sci. USA, 102(23):8109–8113, 2005.
  * [22] 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.
  * [23] P. Turán.  Eine Extremalaufgabe aus der Graphentheorie.  Mat. Fiz. Lapok, 48:436–452, 1941.

## Appendix

In this appendix, we prove Proposition 2.1. The upper bound follows directly
from the fact that an $F_{2}^{t}$-free hypergraph has maximum codegree at most
$t$ and the equality is achieved only for $(n,3,2,t)$-designs. Next, we prove
the lower bounds.

Let $G$ and $F$ be $r$-graphs. An $(F,t)$_-design_ of $G$ is a family
$\mathcal{F}$ of distinct copies of $F$ in $G$ such that every hyperedge of
$G$ is contained in exactly $t$ of these copies. The main tool for proving
Proposition 2.1 is a result by Glock, Kühn, Lo, and Osthus [11], which gives
sufficient conditions on $G$ to contain an $(F,t)$-design. Denote by $K_{n}$
the complete graph on $n$ vertices. Here, we will only state their result for
the case we are interested in: $r=2$ and $F=K_{3}$. An $n$-vertex graph $G$ is
$(c,h,p)$_-typical_ if for every set $A\subseteq V(G)$ with $|A|\leqslant h$,
we have $(1-c)np^{|A|}\leqslant|\bigcap_{v\in A}N(v)|\leqslant(1+c)np^{|A|}$,
where $N(v)$ is the set of neighbors of $v$ in $G$. A graph $G$ is
$(K_{3},t)$_-divisible_ if $t|E(G)|$ is divisible by $3$ and $t|N(v)|$ is
divisible by $2$ for every $v\in V(G)$.

######  Theorem 5.1 (Glock, Kühn, Lo, and Osthus [11]).

For $h=2812$ and every $c,p\in\left(0,1\right]$ with $c\leqslant
0.9(p/2)^{h}/(36^{2}\cdot 4^{36})$, there exist $n_{0}$ and $\gamma>0$ such
that the following holds for all $n\geqslant n_{0}$. Let $t$ be a positive
integer with $t\leqslant\gamma n$. Suppose that $G$ is a $(c,h,p)$-typical
graph on $n$ vertices. Then, $G$ has a $(K_{3},t)$-design if it is
$(K_{3},t)$-divisible.

We are ready to prove the following lemmas corresponding to the lower bounds
in Proposition 2.1.

######  Lemma 5.2.

For every even $t\geqslant 1$ and sufficiently large $n$, we have
$\mathrm{ex}(n,F_{2}^{t})\geqslant\frac{t}{3}\binom{n}{2}-\frac{2t}{3}.$

###### Proof.

Let $G_{1}=K_{n}$, $G_{2}$ be the graph obtained from $K_{n}$ by removing an
edge and $G_{3}$ be the graph obtained from $K_{n}$ by removing a matching
containing two edges. Note that $G_{1},G_{2},G_{3}$ are all
$(c,2812,1)$-typical for every $c\leqslant 0.9(1/2)^{2812}/(36^{2}\cdot
4^{36})$. We have $|E(G_{1})|=|E(G_{2})|+1=|E(G_{3})|+2,$ and hence there
exists $i\in\\{1,2,3\\}$ such that $3$ divides $|E(G_{i})|$. Therefore,
$G_{i}$ is $(K_{3},t)$-divisible. By Theorem 5.1, there exists a
$(K_{3},t)$-design of $G_{i}$. The corresponding hypergraph $H$, i.e., the
$n$-vertex $3$-graph where a triple is a hyperedge in $H$ if it is a $K_{3}$
in the $(K_{3},t)$-design, satisfies that every pair of vertices has codegree
at most $t$ and
$|H|\geqslant\frac{t}{3}\left(\binom{n}{2}-2\right)=\frac{t}{3}\binom{n}{2}-\frac{2t}{3}.$
∎

######  Lemma 5.3.

For every odd $t\geqslant 1$ and sufficiently large odd $n$, we have
$\mathrm{ex}(n,F_{2}^{t})\geqslant\frac{t}{3}\binom{n}{2}-\frac{8t}{3}.$

###### Proof.

Denote by $C_{4}$ the cycle with $4$ vertices. Let $G_{1}=K_{n}$, $G_{2}$ be
the graph obtained from $K_{n}$ by removing $4$ edges that form a copy of
$C_{4}$ and $G_{3}$ be the graph obtained from $K_{n}$ by removing $8$ edges
that form two vertex-disjoint copies of $C_{4}$. Note that $G_{1},G_{2},G_{3}$
are all $(c,2812,1)$-typical for every $c\leqslant
0.9(1/2)^{2812}/(36^{2}\cdot 4^{36})$ and every vertex in each of these three
graphs has an even degree. We have $|E(G_{1})|=|E(G_{2})|+4=|E(G_{3})|+8,$ and
hence there exists $i\in\\{1,2,3\\}$ such that $3$ divides $|E(G_{i})|$.
Therefore, $G_{i}$ is $(K_{3},t)$-divisible. By Theorem 5.1, there exists a
$(K_{3},t)$-design of $G_{i}$. The corresponding hypergraph $H$ satisfies that
every pair of vertices has codegree at most $t$ and
$|H|\geqslant\frac{t}{3}\left(\binom{n}{2}-8\right)=\frac{t}{3}\binom{n}{2}-\frac{8t}{3}.$
∎

######  Claim 5.4.

For every even $n\geqslant 4$, there exists an $n$-vertex $3$-graph $H$ with
$d(x,y)\geqslant 1$ for every $x,y\in V(H)$ and
$|H|\leqslant\frac{1}{3}\binom{n}{2}+\frac{n}{3}$.

###### Proof.

Since $n$ is even, by Theorem 1.2, there exists an $(n-1,3,2,1)$-design or an
$(n+1,3,2,1)$-design. In the first case, take an $(n-1,3,2,1)$-design on
$[n-1]$, and add one vertex $n$ and hyperedges $\\{2i-1,2i,n\\}$ for
$i=1,\ldots,n/2-1$ and hyperedge $\\{1,n-1,n\\}$. The resulting hypergraph $H$
has the desired properties: $d(x,y)\geqslant 1$ for every $x,y\in[n]$ and

$\displaystyle|H|=\frac{1}{3}\binom{n-1}{2}+\frac{n}{2}=\frac{1}{3}\binom{n}{2}+\frac{n}{6}+\frac{1}{3}\leqslant\frac{1}{3}\binom{n}{2}+\frac{n}{3}.$

Now, suppose there exists an $(n+1,3,2,1)$-design on $[n+1]$. Let
$\\{v_{i}u_{i}(n+1)\\}$ be the hyperedges containing vertex $n+1$. Remove
vertex $n+1$, and then add hyperedge $v_{i}u_{i}z_{i}$, where $z_{i}$ is an
arbitrary vertex, for every $i$. The resulting hypergraph $H$ has the desired
properties: $d(x,y)\geqslant 1$ for every $x,y\in[n]$ and

$|H|\leqslant\frac{1}{3}\binom{n+1}{2}=\frac{1}{3}\binom{n}{2}+\frac{n}{3}.\qed$

######  Claim 5.5.

For every odd $t\geqslant 1$, there exists a $(t+3)$-vertex $3$-graph $H$ with
$|H|\geqslant\frac{t}{3}\binom{t+3}{2}-\frac{t+3}{3}$ such that each pair of
vertices has codegree at most $t$.

###### Proof.

Take a copy of the complete $3$-graph on $t+3$ vertices and remove the
hyperedge set of a $(t+3)$-vertex $3$-graph $H^{\prime}$, where
$|H^{\prime}|\leqslant\frac{1}{3}\binom{t+3}{2}+\frac{t+3}{3}$ and
$d(x,y)\geqslant 1$ for every pair of vertices $x,y$ in $H^{\prime}$. Such a
hypergraph exists by Claim 5.4. The resulting hypergraph $H$ has the desired
properties: every pair of vertices has codegree at most $t$ and

$|H|\geqslant\binom{t+3}{3}-\left(\frac{1}{3}\binom{t+3}{2}+\frac{t+3}{3}\right)=\frac{t}{3}\binom{t+3}{2}-\frac{t+3}{3}.\qed$

######  Lemma 5.6.

For odd $t\geqslant 1$ and sufficiently large even $n$, we have
$\mathrm{ex}(n,F_{2}^{t})\geqslant\frac{t}{3}\binom{n}{2}-\frac{n}{3}-\frac{t^{2}}{6}-3t.$

###### Proof.

Let $s=s(n):=\left\lfloor\frac{n}{t+3}\right\rfloor$. Partition $[n]$ into
disjoint sets $B_{1}\cup\ldots\cup B_{s}\cup J$, where $|B_{k}|=t+3$ for each
$k\in[s]$ and $0\leqslant|J|<t+3$. Note that $|B_{k}|$ and $|J|$ are both
even. Assume $J=\\{w_{1},\ldots,w_{|J|}\\}$. Define $G_{1}$ to be the
$n$-vertex graph where $uv\not\in E(G_{1})$ iff $u,v\in B_{k}$ for some
$k\in[s]$ or $\\{u,v\\}=\\{w_{2j-1},w_{2j}\\}$ for some $j\in[|J|/2]$. Let
$G_{2}$ be the graph obtained from $G_{1}$ by removing $4$ edges that form a
copy of $C_{4}$, every vertex of which comes from a different set $B_{k}$. Let
$G_{3}$ be the graph obtained from $G_{1}$ by removing $8$ edges that form two
vertex-disjoint copies of $C_{4}$, where every vertex in these two $C_{4}$’s
comes from a different set $B_{k}$. Note that $G_{1},G_{2},G_{3}$ are all
$(c,2812,1)$-typical for every $c\leqslant 0.9(1/2)^{2812}/(36^{2}\cdot
4^{36})$ and every vertex in the graphs $G_{1},G_{2}$ and $G_{3}$ has an even
degree. Further, we have that $|E(G_{1})|=|E(G_{2})|+4=|E(G_{3})|+8,$ and
hence there exists $i\in\\{1,2,3\\}$ such that 3 divides $|E(G_{i})|$.
Therefore, $G_{i}$ is $(K_{3},t)$-divisible. By Theorem 5.1, there exists a
$(K_{3},t)$-design of $G_{i}$. Let $H$ be the corresponding $3$-graph. Note
that if $u,v\in B_{k}$ for some $k\in[s]$, then $uv\notin E(G_{i})$, and hence
$d(u,v)=0$ in $H$. We have

$|H|\geqslant\frac{t}{3}\left(\binom{n}{2}-s\binom{t+3}{2}-\frac{|J|}{2}-8\right).$

Now, we construct an $n$-vertex hypergraph $H^{\prime}$ from $H$ by adding to
every set $B_{k}$ a copy of a $(t+3)$-vertex $3$-graph with at least
$\frac{t}{3}\binom{t+3}{2}-\frac{t+3}{3}$ hyperedges, each pair of vertices in
which has codegree at most $t$. Such a hypergraph exists by Claim 5.5. Then,
$H^{\prime}$ satisfies that every pair of vertices has codegree at most $t$
and

$\displaystyle|H^{\prime}|$
$\displaystyle\geqslant\frac{t}{3}\left(\binom{n}{2}-s\binom{t+3}{2}-\frac{|J|}{2}-8\right)+s\left(\frac{t}{3}\binom{t+3}{2}-\frac{t+3}{3}\right)$
$\displaystyle=\frac{t}{3}\binom{n}{2}-\frac{t|J|}{6}-\frac{8t}{3}-\frac{s(t+3)}{3}\geqslant\frac{t}{3}\binom{n}{2}-\frac{t^{2}}{6}-3t-\frac{n}{3}.\qed$