# On the Maximum $F_{5}$-free Subhypergraphs
of a Random Hypergraph

Igor Araujo111Department of Mathematics, University of Illinois at Urbana-
Champaign, Urbana, Illinois 61801, USA. Email<EMAIL_ADDRESS>József
Balogh222Department 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. Haoran Luo333Department of
Mathematics, University of Illinois at Urbana-Champaign, Urbana, Illinois
61801, USA, E-mail<EMAIL_ADDRESS>
###### Abstract

Denote by $F_{5}$ the $3$-uniform hypergraph on vertex set $\\{1,2,3,4,5\\}$
with hyperedges $\\{123,124,345\\}$. Balogh, Butterfield, Hu, and Lenz proved
that if $p>K\log n/n$ for some large constant $K$, then every maximum
$F_{5}$-free subhypergraph of $G^{3}(n,p)$ is tripartite with high
probability, and showed if $p_{0}=0.1\sqrt{\log n}/n$, then with high
probability there exists a maximum $F_{5}$-free subhypergraph of
$G^{3}(n,p_{0})$ that is not tripartite. In this paper, we sharpen the upper
bound to be best possible up to a constant factor. We prove that when
$p>C\sqrt{\log n}/n$ for some large constant $C$, then every maximum
$F_{5}$-free subhypergraph of $G^{3}(n,p)$ is tripartite with high
probability.

##  1 Introduction

The first theorem in extremal graph theory is Mantel’s Theorem
[mantel1907Pro], which states that every triangle-free graph on $n$ vertices
has at most $\lfloor n^{2}/4\rfloor$ edges. Additionally, the complete
bipartite graph whose part sizes differ by at most one is the unique maximum
triangle-free graph. Later, Turán [turan1941extremalaufgabe] generalized
Mantel’s Theorem for complete graphs. Denote by $K_{s}$ the complete graph on
$s$ vertices and by $T_{s}(n)$ the complete $s$-partite graph on $n$ vertices
where the sizes of the parts differ by at most $1$. Turán’s Theorem states
that $T_{s-1}(n)$ is the unique maximum $K_{s}$-free graph on $n$ vertices.
Turán’s Theorem can also be understood as a property of $K_{n}$. Namely, it
confirms that every maximum $K_{s}$-free subgraph of $K_{n}$ is
$(s-1)$-partite.

Let $G(n,p)$ be the standard binomial model of random graphs, where each edge
in $K_{n}$ is chosen independently with probability $p$. We say an event
occurs _with high probability (w.h.p.)_ if its probability goes to $1$ as $n$
goes to infinity. A question related to Turán’s Theorem arises when $G(n,p)$
replaces the role of $K_{n}$, that is for what $p=p(n)$ we have that every
maximum $K_{s}$-free subgraph of $G(n,p)$ is $(s-1)$-partite with high
probability. This question was first considered by Babai, Simonovits and
Spencer [babai1990extremal], who studied the case when $p=\frac{1}{2}$ and
$s=3$.

DeMarco and Kahn [demarco2015mantel] determined the correct order of $p$ for
$s=3$. They [demarco2015mantel] showed that if $p>K\sqrt{\log n/n}$ for some
large constant $K$, then every maximum triangle-free subgraph of $G(n,p)$ is
w.h.p. bipartite, while if $p=0.1\sqrt{\log n/n}$, then this does not hold
w.h.p., where here and throughout the paper, the logarithms are in natural
base. Finally, DeMarco and Kahn [demarco2015turan] answered this question for
every $s\geqslant 3$.

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

Figure 2: The hypergraph $K_{4}^{-}$.$1$$2$$3$$4$

Similar problems can also be considered for hypergraphs. Denote by $K_{4}^{-}$
the hypergraph obtained from the complete $3$-uniform hypergraph on $4$
vertices by removing one hyperedge. Let $F_{5}$, which sometimes is called the
_generalized triangle_ , be the hypergraph on vertex set $\\{1,2,3,4,5\\}$
with hyperedges $\\{123,124,345\\}$. Denote by $S(n)$ the complete $3$-partite
$3$-uniform hypergraph on $n$ vertices whose parts have sizes $\left\lfloor
n/3\right\rfloor$, $\left\lfloor(n+1)/3\right\rfloor$, and
$\left\lfloor(n+2)/3\right\rfloor$, and let $s(n)=$ $\left\lfloor
n/3\right\rfloor\cdot\left\lfloor(n+1)/3\right\rfloor\cdot\left\lfloor(n+2)/3\right\rfloor$
be the number of hyperedges in $S(n)$. Bollobás [bollobas1974three] proved
that $S(n)$ is the unique maximum $\\{K_{4}^{-},F_{5}\\}$-free $n$-vertex
hypergraph. Frankl and Füredi [frankl1983new] proved that, for $n\geqslant
3000$, the maximum number of hyperedges in an $n$-vertex $F_{5}$-free
$3$-uniform hypergraph is $s(n)$. Later, this result was improved by Keevash
and Mubayi [keevash2004stability], who proved that if $n\geqslant 33$, the
unique maximum $n$-vertex $F_{5}$-free $3$-uniform hypergraph is $S(n)$.

The random version of this theorem was obtained by Balogh, Butterfield, Hu and
Lenz [balogh2016mantel]. Let $G^{3}(n,p)$ be the random $3$-uniform hypergraph
on vertex set $[n]\coloneqq\\{1,\ldots,n\\}$, where each triple in
$\binom{[n]}{3}$ is included in $G^{3}(n,p)$ with probability $p$
independently of each other. Note that when $p$ is very small, then
$G^{3}(n,p)$ itself is tripartite and hence $F_{5}$-free with high
probability. Therefore, the interesting case is when $p$ is large enough. In
[balogh2016mantel], it was proved that when $p>K\log n/n$ for some large
constant $K$, every maximum $F_{5}$-free subhypergraph of $G^{3}(n,p)$ is
w.h.p. tripartite, and it was conjectured that it should be enough to require
$p>C\sqrt{\log n}/n$ for some large constant $C$. In this paper, we verify
this conjecture. Note that this is best possible up to the constant factor, as
it was also shown in [balogh2016mantel] that when $p=0.1\sqrt{\log n}/n$, then
w.h.p. there is a maximum $F_{5}$-free subhypergraph of $G^{3}(n,p)$ that is
not tripartite.

######  Theorem 1.

There exists a constant $C>0$ such that, for every $p>C\sqrt{\log n}/n$,
w.h.p. every maximum $F_{5}$-free subhypergraph of $G^{3}(n,p)$ is tripartite.

Our approach will follow the general structure of [balogh2016mantel]. Several
key lemmas are improved and adapted for this smaller $p$. We trust that the
new ideas used in our proof could be useful for solving other problems when
one of the tasks in the proof is to beat the union bound. In Section 2, we
will introduce the notation and lemmas needed. In Section 3, we give the proof
of Theorem 1.

##  2 Preliminaries

To improve readability, as it is standard in the literature, we will usually
pretend that large numbers are integers to avoid using essentially irrelevant
floor and ceiling symbols. For a set $S$, we use $\binom{S}{k}$ to stand for
the collection of all the subsets of $S$ with size $k$. We will often use the
standard upper bound $\binom{n}{k}\leqslant(\frac{en}{k})^{k}$ for binomial
coefficients. We write $x=(1\pm c)y$ for $(1-c)y\leqslant x\leqslant(1+c)y$.
We use $G$ for $G^{3}(n,p)$ hereinafter and denote by $t(G)$ the number of
hyperedges in a maximum tripartite subhypergraph of $G$. Let $C$ be a large
enough constant such that all assumptions in the lemmas in this section are
satisfied and the proof in Section 3 works.

We will always assume that the hypergraphs are on vertex set
$[n]=\\{1,\ldots,n\\}$, so we can identify a hypergraph $H$ by its hyperedges
and $|H|$ stands for the number of hyperedges of $H$. We use
$\pi=(V_{1},V_{2},V_{3})$ to stand for a $3$-partition of $[n]$. We say a
$3$-partition $\pi$ is _balanced_ if every part has size $(1\pm 10^{-10})n/3$.
Denote by $K_{\pi}$ the set of triples with exactly one vertex in each part of
$\pi$. Let $G_{\pi}:=G\cap K_{\pi}$. For a hypergraph $H\subseteq G$, let
$H_{i}\coloneqq\\{e\in H\;:\;|e\cap V_{i}|\geqslant 2\\}$ for $i=1,2,3$. Let
$H_{\pi}\coloneqq H\cap K_{\pi}$ and $\bar{H}_{\pi}\coloneqq G_{\pi}\setminus
H_{\pi}$. We will call hyperedges in $H_{\pi}$ the _crossing hyperedges_ of
$H$, and the hyperedges in $\bar{H}_{\pi}$ the _missing crossing hyperedges_
of $H$.

For a hypergraph $H$, a partition $\pi=(V_{1},V_{2},V_{3})$,
$v,v^{\prime}\in[n]$, and $S,T\subseteq[n]$, let
$N_{S,T}^{H}(v)\coloneqq\\{\\{y,z\\}:y\in S,z\in T,vyz\in H\\}$ be the _link
graph_ in $H$ of $v$ between $S$ and $T$,
$d_{S,T}^{H}(v)\coloneqq|N^{H}_{S,T}(v)|$ be the _degree_ in $H$ of $v$
between $S$ and $T$, $N_{S}^{H}(v,v^{\prime})\coloneqq\\{z:z\in
S,vv^{\prime}z\in H\\}$ be the _neighbors_ of $v$ and $v^{\prime}$ in $S$, and
$d^{H}_{S}(v,v^{\prime})\coloneqq|N_{S}(v,v^{\prime})|$ be the _codegree_ of
$v$ and $v^{\prime}$ in $S$. Let $L_{S,T}^{H}(v,v^{\prime})\coloneqq
N^{H}_{S,T}(v)\cap N^{H}_{S,T}(v^{\prime})$ be the _common neighborhood_ of
$v$ and $v^{\prime}$ between $S$ and $T$ in $H$. When $S$ or $T$ is $[n]$ or
$H=G$, we omit to write $S$, $T$ or $G$ when there is no ambiguity. When $S$
or $T$ is $V_{i}$, we often just use $i$ in the subscript. For example, $d(x)$
is just the degree of $x$ in $G$ and $N^{H}_{1}(y,z)$ is the neighbors of $y$
and $z$ in $V_{1}$ in $H$. We will often use $xy$ to stand for $\\{x,y\\}$ and
$xyz$ to stand for $\\{x,y,z\\}$. Finally, define

$Q(\pi)\coloneqq\\{xy\subset V_{1}:|L_{2,3}(x,y)|<0.8p^{2}n^{2}/9\\}.$

The first proposition we need from [balogh2016mantel] is the following
stability result, which is a special case of a general transference result of
Conlon and Gowers [conlon2016combinatorial], and as Samotij observed
[samotij2014stability] of Schacht [schacht2016extremal]. It was also proved by
the hypergraph container method [balogh2015independent, saxton2015hypergraph].

######  Proposition 2.

For every $\delta>0$, there exist $\varepsilon>0$ and $C>0$ such that if
$p>C/n$, the follow statement is true. Let $H$ be a maximum $F_{5}$-free
subhypergraph of $G$ and $\pi$ be a $3$-partition maximizing $|H_{\pi}|$. Then
$|H|\geqslant(2/9-\varepsilon)p\binom{n}{3}$, $\pi$ is balanced and
$|H\setminus H_{\pi}|\leqslant\delta pn^{3}$.

The following concentration results are also in [balogh2016mantel]. Lemma 3 is
the standard Chernoff’s bound. Lemma 4 and Lemma 5 are standard properties of
random hypergraphs.

######  Lemma 3.

Let $Y$ be the sum of mutually independent indicator random variables, and let
$\mu=\mathbb{E}[Y]$. For every $\varepsilon>0$, we have

$\mathbb{P}[|Y-\mu|>\varepsilon\mu]<2e^{-c_{\varepsilon}\mu},$

where
$c_{\varepsilon}=\min\left\\{-\log\left(e^{\varepsilon}(1+\varepsilon)^{-(1+\varepsilon)}\right),\,\varepsilon^{2}/2\right\\}$.

######  Lemma 4.

For every $\varepsilon>0$, there exists a positive constant $C$ such that if
$p>C\log n/n^{2}$, then w.h.p. for every vertex $v$, we have
$d(v)=(1\pm\varepsilon)pn^{2}/2$.

######  Lemma 5.

For every $\varepsilon>0$, there exists a positive constant $C$ such that if
$p>C/n$, then w.h.p. for every $3$-partition $\pi=(V_{1},V_{2},V_{3})$ with
$|V_{2}|,|V_{3}|\geqslant n/20$ and every vertex $v\in V_{1}$, we have
$d_{2,3}(v)=(1\pm\varepsilon)p|V_{2}||V_{3}|$.

We also have the following concentration results.

######  Lemma 6.

There exists a positive constant $C$ such that if $p>C\sqrt{\log n}/n$, then
w.h.p. for every pair of vertices $x,y$, we have $d(x,y)\leqslant pn\sqrt{\log
n}/\log\log n$.

###### Proof.

For every pair of vertices $xy$, the probability that
$d(x,y)\geqslant\frac{pn\sqrt{\log n}}{\log\log n}$ is at most
$\binom{n}{\frac{pn\sqrt{\log n}}{\log\log n}}p^{\frac{pn\sqrt{\log
n}}{\log\log n}}$. There are $\binom{n}{2}$ pairs of vertices, so by using a
union bound, the probability that there exists a pair of vertices $xy$ such
that $d(x,y)\geqslant\frac{pn\sqrt{\log n}}{\log\log n}$ is at most

$\displaystyle\binom{n}{2}\binom{n}{pn\frac{\sqrt{\log n}}{\log\log
n}}p^{\frac{pn\sqrt{\log n}}{\log\log n}}\leqslant
n^{2}\left(\frac{enp}{pn\frac{\sqrt{\log n}}{\log\log
n}}\right)^{\frac{pn\sqrt{\log n}}{\log\log n}}\leqslant
n^{2}\left(\frac{e\log\log n}{\sqrt{\log n}}\right)^{\frac{C\log n}{\log\log
n}}$ $\displaystyle\leqslant$ $\displaystyle\exp\left(2\log n+\frac{C\log
n}{\log\log n}\log\frac{e\log\log n}{\sqrt{\log
n}}\right)=\exp\left(\left(2+\frac{C(1+\log\log\log n)}{\log\log
n}-\frac{C}{2}\right)\log n\right),$

where the last expression is $o(1)$ for sufficiently large $C$. ∎

######  Remark 7.

Lemma 6 shows one of the major differences in the proof compared to the case
when $p$ is only at least $C\sqrt{\log n}/n$, whereas in [balogh2016mantel] it
is proved that $d(x,y)\leqslant 2pn$ with high probability when $p>K\log n/n$.
Also note that with a direct application of the Chernoff’s inequality we can
only conclude that $d(x,y)\leqslant pn\sqrt{\log n}$, without the $\log\log n$
factor. As we will see in Section 3, this $\log\log n$ factor plays a vital
role in the proof of Theorem 1 (see Remark 19).

######  Lemma 8.

There exists a constant $C>0$ such that if $p>C\sqrt{\log n}/n$, then w.h.p.
for every subset $S\subseteq[n]$,

$\left|\left\\{\\{x,y\\}\in\binom{[n]\setminus S}{2}\;:\;d_{S}(x,y)\geqslant
3pn\right\\}\right|\leqslant n^{2}e^{-\sqrt{\log n}}.$

###### Proof.

First, consider a fixed set $S$. For every pair of vertices
$\\{x,y\\}\in\binom{[n]\setminus S}{2}$, the probability that $d_{S}(x,y)>3pn$
is at most $\binom{|S|}{3pn}p^{3pn}$. For different pairs $\\{x_{1},y_{1}\\}$
and $\\{x_{2},y_{2}\\}$ in $\binom{[n]\setminus S}{2}$, $d_{S}(x_{1},y_{1})$
and $d_{S}(x_{2},y_{2})$ are independent. Hence, given a family of
$n^{2}e^{-\sqrt{\log n}}$ pairs of vertices in $\binom{[n]\setminus S}{2}$,
the probability that $d_{S}(x,y)\geqslant 3pn$ for every pair $\\{x,y\\}$ in
this family is at most
$\left(\binom{|S|}{3pn}p^{3pn}\right)^{n^{2}e^{-\sqrt{\log n}}}$. Then, by a
union bound over all the families of size $n^{2}e^{-c\sqrt{\log n}}$ of pairs
of vertices not in $S$, we get

$\displaystyle\mathbb{P}\left(\left|\left\\{\\{x,y\\}\in\binom{[n]\setminus
S}{2}\;:\;d_{S}(x,y)\geqslant 3pn\right\\}\right|>n^{2}e^{-\sqrt{\log
n}}\right)$ $\displaystyle\leqslant\binom{n^{2}}{n^{2}e^{-\sqrt{\log n}}}$
$\displaystyle\left(\binom{|S|}{3pn}p^{3pn}\right)^{n^{2}e^{-\sqrt{\log n}}}.$

Finally, using a union bound over all the choices of $S$, the probability of
failure is at most

$2^{n}\binom{n^{2}}{n^{2}e^{-\sqrt{\log
n}}}\left(\binom{n}{3pn}p^{3pn}\right)^{n^{2}e^{-\sqrt{\log n}}}\leqslant
2^{n}\left(e^{1+\sqrt{\log
n}}\left(\frac{e}{3}\right)^{3pn}\right)^{n^{2}e^{-\sqrt{\log n}}}=o(1).\qed$

Let $s=s(n,p)$, $r=r(n,p)$, $i=i(n,p)$ be positive integers depending on $n$
and $p$, where $s\leqslant n$, $r\leqslant\binom{n}{2}$ and $i\leqslant n$.
Let $E_{s,r,i}$ be the event that for every vertex $v\in[n]$ and vertex set
$S\subseteq[n]$, where $v\notin S$ and $|S|=s$, there are at most $r$ pairs of
vertices $\\{y_{k},z_{k}\\}\in\binom{[n]\setminus S}{2}$ such that
$vy_{k}z_{k}\in G$ and $d_{S}(y_{k},z_{k})\geqslant i$ for every $k$, see
Figure 3. Define
$g(p,s,r,i):=n\binom{n}{s}\binom{n^{2}}{r}\left(p\binom{s}{i}p^{i}\right)^{r}$,
and let $O$ be the set of $(s,r,i)$ such that $g(p,s,r,i)=o(n^{-5})$ given
$p>C\sqrt{\log n}/n$. Let $E$ be the event $\bigcap\limits_{(s,r,i)\in
O}E_{s,r,i}$.

Figure 3: The event $E_{s,r,i}$ is that there are at most $r$ pairs of
vertices $\\{y_{k},z_{k}\\}\in\binom{[n]\setminus S}{2}$ such that
$vy_{k}z_{k}\in G$ and $d_{S}(y_{k},z_{k})\geqslant i$ for every
$k$.$v$$x_{i+1}$$x_{2}$$x_{1}$$y_{k}$$z_{k}$$\ldots$$S$

######  Lemma 9.

E happens with high probability.

###### Proof.

First consider $\bar{E}_{s,r,i}$, the complement of the event $E_{s,r,i}$. Fix
distinct vertices $v,y,z\in[n]$ and vertex set $S\subset[n]$ where
$v,y,z\notin S$ and $|S|=s$, then

$\mathbb{P}(vyz\in G)=p,\quad\mathbb{P}(d_{S}(y,z)\geqslant
i)\leqslant\binom{s}{i}p^{i}.$

Note that these two events are independent since $v\notin S$. Therefore, the
probability that there are at least $r$ pairs of vertices
$(y_{k},z_{k})\in\binom{[n]\setminus S}{2}$ where $vy_{k}z_{k}\in G$ and
$d_{S}(y_{k},z_{k})\geqslant i$ is at most
$\binom{n^{2}}{r}(p\binom{s}{i}p^{i})^{r}$. Then, using a union bound over all
choices of $v\in[n]$ and $S\subset[n]$ of size $s$, we get that
$\mathbb{P}(\bar{E}_{s,r,i})\leqslant g(p,s,r,i)=o(n^{-5})$. Then we have

$\mathbb{P}(\bar{E})=\mathbb{P}\Bigg{(}\bigcup_{(s,r,i)\in
O}\bar{E}_{s,r,i}\Bigg{)}\leqslant\sum_{(s,r,i)\in
O}\mathbb{P}(\bar{E}_{s,r,i})\leqslant n\binom{n}{2}n\cdot
o(n^{-5})=o(1).\qed$

In our proof of Theorem 1, we will repeatedly use Lemma 9 to show that for
some given vertex $v$ and vertex set $S$, the number of pairs that are in the
link graph of $v$ and have a large neighborhood in $S$ is small.

######  Remark 10.

Lemma 8 and Lemma 9 are similar and one may hope that we can still keep the
$e^{-\sqrt{\log n}}$ factor by proving $(s,pn^{2}e^{-\sqrt{\log n}},3ps)\in O$
for every $1\leqslant s\leqslant n$. Unfortunately, this is not necessary
true. In the proof of Lemma 8, we have $n^{2}e^{-\sqrt{\log n}}$ in the
exponent, which can beat the number of choices of $S$, whereas
$pn^{2}e^{-\sqrt{\log n}}$ is not larger than $n$. Instead, we have
$(s,pn^{2}/\log n,3pn)\in O$, see Claim 25.

For fixed vertex $v$, vertex set $A\subseteq[n]\setminus\\{v\\}$, subset $T$
of $N_{[n]\setminus A,[n]\setminus A}(v)$ and subset $E$ of $\\{vxw\in
G\;:\>x\in A\\}$, define

$K(v,E,A,T)\coloneqq\\{xyz:x\in A,\,yz\in T,\textrm{ there exists }e\in
E\textrm{ such that }x\in e,\,y\notin e,\,z\notin e\\},$

and $G(v,E,A,T)\coloneqq K(v,E,A,T)\cap G$. We have that
$\mathbb{E}(|G(v,E,A,T)|)=p|K(v,E,A,T)|$; note that here the randomness in
this expectation is of the hyperedges in $\\{xyz\;:\>x\in A,\,yz\in T\\}$
being or not in $G$. Also note that the events of the hyperedges in
$\\{xyz\;:\>x\in A,\,yz\in T\\}$ being or not in $G$ are independent from the
events from hyperedges containing $v$ being in $G$. We will condition on which
hyperedges containing $v$ are present in $G$ in the argument that follows, and
we will do so repeatedly without further notice. Also note that for every
$xyz\in G(v,E,A,T)$ with $x\in A$, $yz\in T$, we can find an
$F_{5}=\\{yzv,yzx,vxw\\}$ in $G$ where $vxw\in E$, see Figure 4. The condition
$y\notin e,\,z\notin e$ in the definition of $K(v,E,A,T)$ guarantees that we
indeed find an $F_{5}$ instead of an $K_{4}^{-}$.

$v$$x$$y$$z$$w\quad\in E$$A$$T$ Figure 4: A copy of $F_{5}$ from $xyz\in
G(v,E,A,T)$.

######  Lemma 11.

For any constants $\varepsilon,\varepsilon_{1},\varepsilon_{2}>0$, there
exists a constant $C>0$ such that if $p>C\sqrt{\log n}/n$, then with high
probability for every choice of $v,E,A,T$ as above with
$|A|\geqslant\varepsilon_{1}n/\sqrt{\log n}$ and
$|T|\geqslant\varepsilon_{2}pn^{2}$, we have
$|G(v,E,A,T)|=(1\pm\varepsilon)p|A||T|$.

The proof of Lemma 11 follows the same lines of the proof of Proposition 9 in
[balogh2016mantel].

###### Proof.

Here we reveal the randomness into two phases. We first reveal the hyperedges
containing $v$; given this choice we can fix $A$, $T$ and $E$. We have at most
$n$ choices for $v$. For sets $A,T$ with $|A|=a$ and $|T|=t$, there are at
most $\binom{n}{a}$ choices for $A$, and with high probability there are at
most $2^{apn\frac{\sqrt{\log n}}{\log\log n}}$ choices for $E$ (by Lemma 6)
and at most $\binom{pn^{2}}{t}$ choices for $T$ (by Lemma 4).

For vertex $x\in A$, let $[x,T]\coloneqq\\{xyz:yz\in T\\}$,
$d^{E}(x)\coloneqq|\\{e\in E:x\in e\\}|$ and $T_{x}\coloneqq\\{yz\in T|vxy\in
E\textrm{ or }vxz\in E\\}$. Let $[A,T]\coloneqq\\{xyz:x\in A,\,yz\in T\\}$.
Note that $[A,T]\supseteq K(v,E,A,T)$. If $d^{E}(x)\geqslant 3$, choose
$vxw_{1},vxw_{2},vxw_{3}$ arbitrarily from $E$. For every $yz\in T$, there
exists some $i\in\\{1,2,3\\}$ such that $y\neq w_{i}$ and $z\neq w_{i}$.
Hence, by the definition of $K(v,E,A,T)$, we have $[x,T]\subseteq K(v,E,A,T)$.
If $d^{E}(x)\leqslant 2$, by Lemma 6, we have $|T_{x}|\leqslant
2\cdot\frac{pn\sqrt{\log n}}{\log\log n}$ and $[x,T\setminus
T_{x}]=\\{xyz:yz\in T\setminus T_{x}\\}\subseteq K(v,E,A,T)$. Therefore,

$|[A,T]|-|K(v,E,A,T)|\leqslant\sum_{x:\>x\in A,\,d^{E}(x)\leqslant
2}|T_{x}|\leqslant|A|\cdot 2pn\frac{\sqrt{\log n}}{\log\log n}.$

We have $|[A,T]|=|A||T|\geqslant|A|\varepsilon_{2}pn^{2}$, so
$|K(v,E,A,T)|=(1-o(1))|A||T|$ with high probability.

Now, we reveal the hyperedges in $[A,T]$, Let
$\mu=\mathbb{E}(G(v,E,A,T))=p|K(v,E,A,T)|=(1-o(1))p|A||T|$. By Lemma 3, we
have

$\mathbb{P}(||G(v,E,A,T)|-\mu|>\varepsilon\mu)<2e^{-c_{\varepsilon}\mu}.$

Then by the union bound, the probability that the statement in the lemma does
not hold is at most

$\displaystyle\sum_{a\geqslant\frac{\varepsilon_{1}n}{\sqrt{\log
n}}}\sum_{t\geqslant\varepsilon_{2}pn^{2}}n\binom{n}{a}2^{apn\frac{\sqrt{\log
n}}{\log\log n}}\binom{pn^{2}}{t}\cdot 2e^{-c_{\varepsilon}\cdot atp/2}$
$\displaystyle\leqslant\;$
$\displaystyle\sum_{a\geqslant\frac{\varepsilon_{1}n}{\sqrt{\log
n}}}\sum_{t\geqslant\varepsilon_{2}pn^{2}}n\exp\left(a\log\frac{en}{a}\right)2^{apn\frac{\sqrt{\log
n}}{\log\log n}}\exp\left(t\log\frac{pn^{2}}{t}\right)\cdot
2e^{-c_{\varepsilon}\cdot atp/2}$ $\displaystyle\leqslant\;$ $\displaystyle
2\sum_{a\geqslant\frac{\varepsilon_{1}n}{\sqrt{\log
n}}}\sum_{t\geqslant\varepsilon_{2}pn^{2}}\exp\left(\log
n+a\log\left(\frac{e}{\varepsilon_{1}}\sqrt{\log n}\right)+apn\frac{\sqrt{\log
n}\log 2}{\log\log
n}+t\log\frac{1}{\varepsilon_{2}}-c_{\varepsilon}atp/2\right)$
$\displaystyle\leqslant\;$ $\displaystyle
2\sum_{a\geqslant\frac{\varepsilon_{1}n}{\sqrt{\log
n}}}\sum_{t\geqslant\varepsilon_{2}pn^{2}}\exp\left(-c_{\varepsilon}atp/4\right)\leqslant
2n^{3}\exp(-n\sqrt{\log n})=o(1).\qed$

##  3 Proof of the Main Theorem

Recall that for a given partition $\pi=(V_{1},V_{2},V_{3})$,

$\displaystyle\bar{H}_{\pi}=G_{\pi}\setminus H_{\pi},$ $\displaystyle
H_{i}=\\{e\in H:|e\cap V_{i}|\geqslant 2\\}\;\;\text{ for $i\in\\{1,2,3\\}$,
\;\;and }$ $\displaystyle Q(\pi)=\\{\\{u,v\\}\subset
V_{1}:|L_{2,3}(u,v)|<0.8p^{2}n^{2}/9\\}.$

For a $3$-uniform hypergraph $H$, the _shadow graph_ of $H$ is the graph on
the same vertex set, where $xy$ is an edge if and only if there exist another
vertex $z$ such that $xyz$ is a hyperedge in $H$.

######  Proposition 12.

Let $H$ be an $F_{5}$-free subhypergraph of $G$ and $\pi=(V_{1},V_{2},V_{3})$
be a balanced partition maximizing $|H_{\pi}|$. Then there exist positive
constants $C$ and $\delta$ such that if $p>C\sqrt{\log n}/n$ and if the
following conditions hold:

  1. 1.

$\sum_{i=1}^{3}|H_{i}|\leqslant\delta pn^{3}$,

  2. 2.

the shadow graph of $H_{1}$ is disjoint from $Q(\pi)$,

then with high probability $|\bar{H}_{\pi}|\geqslant 3|H_{1}|$, where equality
is possible only if $H$ is tripartite.

######  Proposition 13.

There exist positive constants $C$ and $\delta$ such that if $p>C\sqrt{\log
n}/n$ and the $3$-partition $\pi$ is balanced, then with high probability

$t(G)\geqslant|G_{\pi}|+|Q(\pi)|\delta n^{2}p^{2},$

where equality is possible only if $Q(\pi)=\emptyset$.

Based on Propositions 12 and 13, Theorem 1 easily follows, whose proof is
similar to the proof of the main theorem in [balogh2016mantel].

###### Proof of Theorem 1.

Let $H$ be a maximum $F_{5}$-free subhypergraph of $G$. We have $|H|\geqslant
t(G)$, since $F_{5}$ is not tripartite. Let $\pi=(V_{1},V_{2},V_{3})$ be a
$3$-partition of $[n]$ maximizing $|H_{\pi}|$. Without loss of generality, we
may assume $|H_{1}|\geqslant|H_{2}|,|H_{3}|$. Besides, by Proposition 2, we
know that $\pi$ is balanced and $\sum_{i=1}^{3}|H_{i}|\leqslant\delta pn^{3}$,
where $\delta$ is the constant in Proposition 12. Now let

$B(\pi)\coloneqq\\{e\in G:\textrm{there exists }\\{u,v\\}\in Q(\pi)\textrm{
such that }\\{u,v\\}\subset e\\}$

and $H^{\prime}\coloneqq H\setminus B(\pi)$, so the shadow graph of
$H^{\prime}_{1}$ is disjoint from $Q(\pi)$. Since $B(\pi)$ consists of only
non-crossing hyperedges of $H$, $\pi$ is still a partition maximizing
$|H_{\pi}^{\prime}|$ and
$\sum_{i=1}^{3}|H^{\prime}_{i}|\leqslant\sum_{i=1}^{3}|H_{i}|\leqslant\delta
pn^{3}$. Hence, $H^{\prime}$ satisfies the assumptions in Proposition 12. Now,
we have w.h.p.

$\displaystyle|H|\leqslant|H_{\pi}|+3|H_{1}|$
$\displaystyle=|H^{\prime}_{\pi}|+3|H^{\prime}_{1}|+3|H\cap B(\pi)|$
$\displaystyle\leqslant|H^{\prime}_{\pi}|+3|H^{\prime}_{1}|+3|B(\pi)|$
$\displaystyle\leqslant|G_{\pi}|+3|B(\pi)|$ (1)
$\displaystyle\leqslant|G_{\pi}|+3|Q(\pi)|pn\sqrt{\log n}/\log\log n$ (2)
$\displaystyle\leqslant|G_{\pi}|+|Q(\pi)|\delta p^{2}n^{2}$ (3)
$\displaystyle\leqslant t(G).$ (4)

Here we use Proposition 12 for (1), Lemma 6 for (2), the assumption
$p>C\sqrt{\log n}/n$ for (3), and Proposition 13 for (4). $|H|$ cannot be
strictly smaller than $t(G)$, so all the inequalities must hold with equality.
By Propositions 12 and 13, $H^{\prime}$ is tripartite and $Q(\pi)$ is empty.
Then, we conclude that $H=H^{\prime}$ is tripartite. ∎

The proof of Proposition 13 is exactly the same as the one in
[balogh2016mantel], where it is required that $p>K\log n/n$. It can be easily
checked that all the arguments still work verbatim with $p>C\sqrt{\log n}/n$.
It remains to prove Proposition 12. Clearly, we can assume that
$|\bar{H}_{\pi}|\leqslant 3|H_{1}|$ and $|H_{1}|\geqslant|H_{2}|,|H_{3}|$. Let
$\delta$ be small enough so that the following arguments work, and fix three
small positive constants $\varepsilon_{1}$, $\varepsilon_{2}$ and
$\varepsilon_{3}$ such that

$\frac{1}{72\varepsilon_{1}}\geqslant
30,\quad\frac{1}{20}\cdot\frac{1}{2\varepsilon_{2}}\geqslant
10,\quad\frac{1}{10}-\varepsilon_{2}\geqslant\frac{1}{20},\quad\frac{100\delta}{\varepsilon_{1}}\leqslant\varepsilon_{3}\leqslant\varepsilon_{1},\quad\frac{\frac{1}{4}\varepsilon_{1}\varepsilon_{2}}{3\varepsilon_{3}}\geqslant
20.$

For example, we can set

$\delta=10^{-100},\quad\varepsilon_{1}=\frac{1}{3000},\quad\varepsilon_{2}=\frac{1}{400},\quad\varepsilon_{3}=10^{-10}.$

Denote by $J$ the induced subgraph of the shadow graph of $H_{1}$ on the
vertex set $V_{1}$ and use $N^{J}(x)$, $d^{J}(x)$ for neighborhood and degree
of $x$ in graph $J$, respectively. Call a $4$-set $\\{w_{1},w_{2},y,z\\}$ an
$\hat{F}_{5}$ if $w_{1}yz$, $w_{2}yz\in G_{\pi}$ and there exists $e\in H$
such that $w_{1},w_{2}\in e\cap V_{1}$, $y,z\notin e$. Note that
$\\{w_{1}yz,w_{2}yz,e\\}$ forms a copy of $F_{5}$ in $G$, so at least one of
$w_{1}yz$ and $w_{2}yz$ has to be in $\bar{H}_{\pi}$.

Figure 5: The set $\\{w_{1},w_{2},y,z\\}$ is an $\hat{F}_{5}$ if there exists
an edge $e\in H_{1}$ as below.$w_{1}$$w_{2}$$\qquad e\in
H_{1}$$y$$z$$V_{1}$$V_{2}$$V_{3}$

We next count copies of $\hat{F}_{5}$ to lower bound the number of missing
crossing hyperedges $|\bar{H}_{\pi}|$, based on the size of (a subgraph of)
$J$. First, we prove the following claim, which will be used in the proofs of
the next few lemmas.

######  Claim 14.

If $p>C\sqrt{\log n}/n$, then with high probability for every edge
$x_{1}x_{2}\in J\setminus Q(\pi)$, there are at least $p^{2}n^{2}/12$ choices
of $(y,z)$ where $y\in V_{2},z\in V_{3}$ such that $\\{x_{1},x_{2},y,z\\}$
spans an $\hat{F}_{5}$.

###### Proof.

Since $x_{1}x_{2}$ is in $J$, there exists $v_{0}$ such that
$x_{1}x_{2}v_{0}\in H$. Since $x_{1}x_{2}$ is not in $Q(\pi)$, there exists at
least $0.8p^{2}n^{2}/9$ choices of $(y,z)$ such that $y\in V_{2}$, $z\in
V_{3}$, and $x_{1}yz$ and $x_{2}yz$ are both in $G_{\pi}$. By Lemma 6, we know
$d(x_{1},v_{0})$ is at most $pn\frac{\sqrt{\log n}}{\log\log n}$, so there can
be at most $pn\frac{\sqrt{\log n}}{\log\log n}$ vertices $v$ such that
$x_{1}v_{0}v\in G_{\pi}$. Therefore, there are at least
$0.8p^{2}n^{2}/9-pn\frac{\sqrt{\log n}}{\log\log n}\geqslant p^{2}n^{2}/12$
choices of $(y,z)$ such that $x_{1}yz,x_{2}yz\in G_{\pi}$ and
$v_{0}\not\in\\{y,z\\}$. For every such $(y,z)$, $\\{x_{1},x_{2},y,z\\}$ forms
an $\hat{F}_{5}$. ∎

######  Lemma 15.

Suppose the assumptions of Proposition 12 hold. Let $J^{\prime}$ be a subgraph
of $J$ and denote by $\Delta(J^{\prime})$ the maximum degree of $J^{\prime}$.
If $\Delta(J^{\prime})\leqslant\varepsilon_{1}n$, then with high probability

$|\bar{H}_{\pi}|\geqslant 30pn|J^{\prime}|.$

If further $\Delta(J^{\prime})\leqslant\varepsilon_{1}n/\sqrt{\log n}$, then
with high probability

$|\bar{H}_{\pi}|\geqslant 20pn|J^{\prime}|\frac{\sqrt{\log n}}{\log\log n}.$

###### Proof.

For each $wx\in J^{\prime}$, we get $wx\notin Q(\pi)$ by the assumption of
Proposition 12, so there are at least $p^{2}n^{2}/12$ choices of $(y,z)$ such
that $\\{w,x,y,z\\}$ spans an $\hat{F}_{5}$, by Claim 14. Then there are at
least $\frac{1}{12}|J^{\prime}|p^{2}n^{2}=\frac{1}{2}\sum_{x\in
V_{1}}d^{J^{\prime}}(x)\frac{p^{2}n^{2}}{12}$ copies of $\hat{F}_{5}$ in
total.

Now consider missing crossing hyperedges $xyz\in\bar{H}_{\pi}$ with $x\in
V_{1}$. Call $xyz\in\bar{H}_{\pi}$ _bad_ if

$\displaystyle d^{J^{\prime}}(x)\leqslant\frac{\varepsilon_{1}n}{\sqrt{\log
n}}\;\;$ $\displaystyle\text{ and }\;\;|N(y,z)\cap
N^{J^{\prime}}(x)|\geqslant\frac{pn\log\log n}{500\sqrt{\log n}},\;\;\text{
or}$ $\displaystyle\frac{\varepsilon_{1}n}{\sqrt{\log
n}}<d^{J^{\prime}}(x)\leqslant\varepsilon_{1}n\;\;$ $\displaystyle\text{ and
}\;\;|N(y,z)\cap N^{J^{\prime}}(x)|\geqslant 3\varepsilon_{1}pn.$

Otherwise, call $xyz$ _good_. We will show that the number of copies of
$\hat{F}_{5}$ that contain a good hyperedge from $\bar{H}_{\pi}$ is at least
$\frac{1}{4}\sum_{x\in V_{1}}d^{J^{\prime}}(x)\frac{p^{2}n^{2}}{12}$. For
$x\in V_{1}$, let $n_{x}$ be the number of copies of $\hat{F}_{5}$ that
contain vertex $x$ and a bad missing crossing hyperedge, and let $r_{x}$ be
the number of $(y,z)$ such that $y\in V_{2}$, $z\in V_{3}$, and $xyz$ is bad.
We will repeatedly use Lemma 9 for some choices of $(s,r,i)\in O$ to give
upper bounds for $r_{x}$ and then obtain upper bounds for $n_{x}$. For every
$x\in V_{1}$, we consider the following two cases.

  * •

Case 1: If $d^{J^{\prime}}(x)\leqslant\frac{\varepsilon_{1}n}{\sqrt{\log n}}$.
If $d^{J^{\prime}}(x)=0$, then $n_{x}$ is trivially $0$. For every positive
integer $s\leqslant\frac{\varepsilon_{1}n}{\sqrt{\log n}}$,
$r=\frac{pn}{\sqrt{\log n}}s$, and $i=\frac{pn\log\log n}{500\sqrt{\log n}}$,
we have $(s,r,i)\in O$ (see Claim 23 in the Appendix for the proof). Hence, by
Lemma 9, we get $r_{x}\leqslant\frac{pn}{\sqrt{\log n}}d^{J^{\prime}}(x)$. By
Lemma 6, we can assume every pair of vertices has codegree at most
$pn\frac{\sqrt{\log n}}{\log\log n}$ in $G$. We conclude

$n_{x}\leqslant pn\frac{\sqrt{\log n}}{\log\log n}\cdot\frac{pn}{\sqrt{\log
n}}d^{J^{\prime}}(x)\leqslant\frac{p^{2}n^{2}}{100}d^{J^{\prime}}(x).$

  * •

Case 2: If $\frac{\varepsilon_{1}n}{\sqrt{\log
n}}<d^{J^{\prime}}(x)\leqslant\varepsilon_{1}n$. For every integer
$s\in(\frac{\varepsilon_{1}n}{\sqrt{\log n}},\,\varepsilon_{1}n]$,
$r=\frac{pn}{500}s$, and $i=3\varepsilon_{1}pn$, we have $(s,r,i)\in O$ (see
Claim 24 in the Appendix for the proof). Hence, by Lemma 9, we have
$r_{x}\leqslant\frac{pn}{500}d^{J^{\prime}}(x)$. By Lemma 6, we can assume
every pair of vertices has codegree at most $pn\frac{\sqrt{\log n}}{\log\log
n}$ in $G$. Besides, we have $(s,pn^{2}/\log n,3pn)\in O$ for every
$1\leqslant s\leqslant n$ (see Claim 25 in the Appendix for the proof), so
there are at most $pn^{2}/\log n$ pairs $(y,z)$ where $y\in V_{2}$, $z\in
V_{3}$ such that $|N(y,z)\cap N^{J^{\prime}}(x)|\geqslant 3pn$. We conclude

$n_{x}\leqslant\frac{pn^{2}}{\log n}\cdot pn\frac{\sqrt{\log n}}{\log\log
n}+3r_{x}pn\leqslant\frac{p^{2}n^{2}}{\log\log n}\cdot\frac{n}{\sqrt{\log
n}}+\frac{3p^{2}n^{2}}{500}d^{J^{\prime}}(x)\leqslant\frac{p^{2}n^{2}}{100}d^{J^{\prime}}(x).$

Thus, the number of copies of $\hat{F}_{5}$ that contain a good hyperedge from
$\bar{H}_{\pi}$ is at least

$\frac{1}{2}\sum_{x\in V_{1}}d^{J^{\prime}}(x)\frac{p^{2}n^{2}}{12}-\sum_{x\in
V_{1}}\frac{p^{2}n^{2}}{100}d^{J^{\prime}}(x)\geqslant\frac{1}{4}\sum_{x\in
V_{1}}d^{J^{\prime}}(x)\frac{p^{2}n^{2}}{12}=\frac{1}{24}|J^{\prime}|p^{2}n^{2}.$
(5)

If $\Delta(J^{\prime})\leqslant\varepsilon_{1}n$, every good missing crossing
hyperedge is in at most $3\varepsilon_{1}pn$ copies of $\hat{F}_{5}$ estimated
in (5), so

$|\bar{H}_{\pi}|\geqslant\frac{\frac{1}{24}|J^{\prime}|p^{2}n^{2}}{3\varepsilon_{1}pn}\geqslant\frac{pn|J^{\prime}|}{72\varepsilon_{1}}\geqslant
30pn|J^{\prime}|.$

If further $\Delta(J^{\prime})\leqslant\varepsilon_{1}n/\sqrt{\log n}$, then
every good missing crossing hyperedge is in at most $\frac{pn\log\log
n}{500\sqrt{\log n}}$ copies of $\hat{F}_{5}$ estimated in (5), so

$|\bar{H}_{\pi}|\geqslant\frac{\frac{1}{24}|J^{\prime}|p^{2}n^{2}}{pn\log\log
n/(500\sqrt{\log n})}\geqslant\frac{20pn|J^{\prime}|\sqrt{\log n}}{\log\log
n}.\qed$

Now, we divide the rest of the proof into two cases according to the size of
$\bar{H}_{\pi}$. The notations and calculations are similar in both cases.

###  3.1 $|\bar{H}_{\pi}|\leqslant\delta pn^{3}/\log n$

Let $S=\\{x\in V_{1}\;:\>d^{J}(x)\geqslant\varepsilon_{1}n/\sqrt{\log n}\\}$,
$S_{1}=\\{x\in S\;:\>d^{H}_{2,3}(x)\geqslant\varepsilon_{2}pn^{2}\\}$ and
$S_{2}=S\setminus S_{1}$. For the following lemmas, we always assume that
$|\bar{H}_{\pi}|\leqslant\delta pn^{3}/\log n$ and the assumptions of
Proposition 12 hold.

######  Lemma 16.

With high probability $|S|\leqslant\varepsilon_{3}n/\sqrt{\log n}$.

###### Proof.

For each $wx\in J^{\prime}$, we get $wx\notin Q(\pi)$ by the assumption of
Proposition 12, so there are at least $p^{2}n^{2}/12$ choices of $(y,z)$ such
that $\\{w,x,y,z\\}$ spans an $\hat{F}_{5}$, by Claim 14. Then there are at
least $\frac{1}{12}|J^{\prime}|p^{2}n^{2}$ copies of $\hat{F}_{5}$ in total.
On the other hand, at least one of $wyz$ and $xyz$ must be in $\bar{H}_{\pi}$.
For $xyz$ where $d(y,z)\leqslant 3pn$, $xyz$ can be in at most $3pn$ copies of
$\hat{F}_{5}$. Hence the number of copies of $\hat{F}_{5}$ containing a pair
$(y,z)\in V_{2}\times V_{3}$ with $d(y,z)\leqslant 3pn$ is at most
$3|\bar{H}_{\pi}|pn$. By Lemma 8, there can be at most $n^{2}e^{-\sqrt{\log
n}}$ pairs $(y,z)$ with $d(y,z)\geqslant 3pn$, and by Lemma 6, for every pair
$(y,z)$, we can assume $d(y,z)\leqslant pn\frac{\sqrt{\log n}}{\log\log n}$.
Hence the number of copies of $\hat{F}_{5}$ containing a pair $(y,z)\in
V_{2}\times V_{3}$ with $d(y,z)\geqslant 3pn$ is at most $n^{2}e^{-\sqrt{\log
n}}\left(pn\frac{\sqrt{\log n}}{\log\log n}\right)^{2}$. Therefore, we get

$n^{2}e^{-\sqrt{\log n}}\left(pn\frac{\sqrt{\log n}}{\log\log
n}\right)^{2}+|\bar{H}_{\pi}|\cdot 3pn\geqslant\frac{|J|p^{2}n^{2}}{12}.$ (6)

Note that $n^{2}e^{-\sqrt{\log n}}\left(pn\frac{\sqrt{\log n}}{\log\log
n}\right)^{2}\leqslant\frac{\delta p^{2}n^{4}}{\log n}$ and by the assumption
$|\bar{H}_{\pi}|<\frac{\delta pn^{3}}{\log n}$ so $|\bar{H}_{\pi}|\cdot
3pn\leqslant\frac{3\delta p^{2}n^{4}}{\log n}$. We get
$|J|\leqslant\frac{48\delta n^{2}}{\log n}$. Every vertex in $S$ has degree at
least $\frac{\varepsilon_{1}n}{\sqrt{\log n}}$ in $J$, so
$\frac{\varepsilon_{1}n}{\sqrt{\log n}}|S|\leqslant
2|J|\leqslant\frac{96\delta n^{2}}{\log n}$, which confirms that
$|S|\leqslant\frac{100\delta}{\varepsilon_{1}}\cdot\frac{n}{\sqrt{\log
n}}\leqslant\frac{\varepsilon_{3}n}{\sqrt{\log n}}$. ∎

######  Lemma 17.

With high probability $|\bar{H}_{\pi}|\geqslant 20pn^{2}|S_{1}|$.

###### Proof.

We can assume that $|S_{1}|>0$, since otherwise this inequality is trivial.
For every vertex $x\in S_{1}$, define

$T_{x}:=\\{yz\;:\>y\in V_{2},\,z\in V_{3},\,xyz\in H,\,d_{S_{1}}(y,z)\leqslant
3\varepsilon_{3}pn/\sqrt{\log n}\\}.$

By Lemma 16, we know $|S_{1}|\leqslant|S|\leqslant\varepsilon_{3}n/\sqrt{\log
n}$. For every $s\leqslant\varepsilon_{3}n/\sqrt{\log n}$, we have
$(s,\varepsilon_{2}pn^{2}/2,3\varepsilon_{3}pn/\sqrt{\log n})\in O$ (see Claim
26 in the Appendix for the proof), so there can be at most
$\varepsilon_{2}pn^{2}/2$ pairs of $(y,z)$ such that $xyz\in G$ and
$d_{S_{1}}(y,z)\geqslant 3\varepsilon_{3}pn/\sqrt{\log n}$. By the definition
of $S_{1}$, we have $d^{H}_{2,3}(x)\geqslant\varepsilon_{2}pn^{2}$ for every
$x\in S_{1}$. Thus, we get $|T_{x}|\geqslant\varepsilon_{2}pn^{2}/2$.

Now, we count the copies of $\hat{F}_{5}=\\{x,w,y,z\\}$ where $x\in S_{1}$,
$w\in N^{J}(x)$, and $\\{y,z\\}\in T_{x}$. Note that $wyz$ must be in
$\bar{H}_{\pi}$, since $xyz\in H$. We have that
$|N^{J}(x)|\geqslant\varepsilon_{1}n/\sqrt{\log n}$ by the definition of $S$,
and we just confirm $|T_{x}|\geqslant\varepsilon_{2}pn^{2}/2$. Applying Lemma
11 by setting $v=x$, $E=H_{1}$, $A=N^{J}(x)$, and $T=T_{x}$, we get the number
of such copies of $\hat{F}_{5}$ is at least

$\sum_{x\in S_{1}}\frac{1}{2}p|N^{J}(x)||T_{x}|\geqslant\sum_{x\in
S_{1}}\frac{1}{2}p\cdot\frac{\varepsilon_{1}n}{\sqrt{\log
n}}\cdot\frac{1}{2}\varepsilon_{2}pn^{2}\geqslant\frac{\varepsilon_{1}\varepsilon_{2}p^{2}n^{3}|S_{1}|}{4\sqrt{\log
n}}.$ (7)

Every $wyz\in\bar{H}_{\pi}$ can be in at most $3\varepsilon_{3}pn/\sqrt{\log
n}$ copies of $\hat{F}_{5}$ evaluated in (7), because $x$ is assumed to be in
$S_{1}$ and $d_{S_{1}}(y,z)\leqslant 3\varepsilon_{3}pn/\sqrt{\log n}$.
Therefore,

$|\bar{H}_{\pi}|\geqslant\frac{\frac{1}{4}\varepsilon_{1}\varepsilon_{2}p^{2}n^{3}|S_{1}|/\sqrt{\log
n}}{3\varepsilon_{3}pn/\sqrt{\log n}}\geqslant 20pn^{2}|S_{1}|.\qed$

######  Lemma 18.

With high probability $|\bar{H}_{\pi}|\geqslant\frac{1}{20}pn^{2}|S_{2}|$.

###### Proof.

For every vertex $x\in S_{2}$, we have $d^{H}_{2,3}(x)<\varepsilon_{2}pn^{2}$
by the definition of $S_{2}$, but by Lemma 5, $d_{2,3}(x)\geqslant pn^{2}/10$.
Thus, there are at least $pn^{2}/20$ hyperedges in $\bar{H}_{\pi}$ containing
$x$, so $|\bar{H}_{\pi}|\geqslant|S_{2}|pn^{2}/20$. ∎

Finally, we deduce Proposition 12 assuming $|\bar{H}_{\pi}|\leqslant\delta
pn^{3}/\log n$.

###### Proof of Proposition 12.

We will show that with high probability $|\bar{H}_{\pi}|\geqslant 3|H_{1}|$ by
using the lower bounds in Lemmas 15, 17 and 18. Partition $H_{1}$ into the
following three sets.

  * •

$H_{1}(1)=\\{e\in H_{1}:|e\cap S|\geqslant 2\textrm{ or }|e\cap V_{1}\setminus
S|\geqslant 2\\}$.

  * •

$H_{1}(2)=\\{e\in H_{1}\setminus H_{1}(1):|e\cap S_{1}|=1\\}$. Hence,
$H_{1}(2)$ contains those hyperedges in $H_{1}$ with exactly one vertex in
$S_{1}$, one vertex in $V_{1}\setminus S$, and one vertex in $[n]\setminus
V_{1}$.

  * •

$H_{1}(3)=H_{1}\setminus(H_{1}(1)\cup H_{1}(2))$. Hence, $H_{1}(3)$ contains
those hyperedges in $H_{1}$ with exactly one vertex in $S_{2}$, one vertex in
$V_{1}\setminus S$, and one vertex in $[n]\setminus V_{1}$.

There are three cases needed to be handled.

  * •

Case 1: If $3|H_{1}(1)|\geqslant|H_{1}|$.

Let $J^{\prime}\coloneqq J[S]\cup J[V_{1}\setminus S]$, where $J[S]$ and
$J[V_{1}\setminus S]$ are the induced subgraph of $J$ on $S$ and
$V_{1}\setminus S$ separately. By Lemma 6,
$|H_{1}(1)|\leqslant|J^{\prime}|pn\sqrt{\log n}/\log\log n$. For every vertex
$x\in S$, $d^{J^{\prime}}(x)$, the degree of $x$ in $J^{\prime}$, is at most
$|S|-1\leqslant\varepsilon_{3}n/\sqrt{\log
n}\leqslant\varepsilon_{1}n/\sqrt{\log n}$, by Lemma 16. For every vertex
$x\in V\setminus S$, we have $d^{J^{\prime}}(x)\leqslant
d^{J}(x)\leqslant\varepsilon_{1}n/\sqrt{\log n}$, by the definition of $S$.
Hence, $\Delta(J^{\prime})\leqslant\varepsilon_{1}n/\sqrt{\log n}$. Then, by
Lemma 15,

$|\bar{H}_{\pi}|\geqslant\frac{20pn|J^{\prime}|\sqrt{\log n}}{\log\log
n}\geqslant 20|H_{1}(1)|\geqslant 3|H_{1}|.$

  * •

Case 2: If $3|H_{1}(2)|\geqslant|H_{1}|$.

For every vertex $x\in S_{1}$, there are at most $2pn^{2}$ hyperedges in
$H_{1}\setminus H_{1}(1)$ containing it, by Lemma 4. Hence,
$|H_{1}(2)|\leqslant 2pn^{2}|S_{1}|$. Then, by Lemma 17,

$|\bar{H}_{\pi}|\geqslant 20pn^{2}|S_{1}|\geqslant 10|H_{1}(2)|\geqslant
3|H_{1}|.$

  * •

Case 3: If $3|H_{1}(3)|\geqslant|H_{1}|$.

By the definition of $S_{2}$, every vertex $x\in S_{2}$ has
$d^{H}_{2,3}(x)\leqslant\varepsilon_{2}pn^{2}$. Recall that $\pi$ maximizes
$|H_{\pi}|$, so $d^{H}_{1,2}(x),d^{H}_{1,3}(x)\leqslant\varepsilon_{2}pn^{2}$.
Hence, $|H_{1}(3)|\leqslant 2\varepsilon_{2}pn^{2}|S_{2}|$. Then, by Lemma 18,

$|\bar{H}_{\pi}|\geqslant\frac{1}{20}pn^{2}|S_{2}|\geqslant\frac{1}{20}\cdot\frac{|H_{1}(3)|}{2\varepsilon_{2}}\geqslant
10|H_{1}(3)|\geqslant 3|H_{1}|.\qed$

######  Remark 19.

The $\log\log n$ factor in Lemma 6 plays an important role in the case
$3|H_{1}(1)|\geqslant|H_{1}|$. Without this factor, we would need to conclude
$|\bar{H}_{\pi}|\geqslant 20pn|J^{\prime}|\sqrt{\log n}$ from Lemma 15, which
we can only obtain when
$\Delta(J^{\prime})\leqslant\varepsilon_{1}n/\log^{1/2+c}n$ for some constant
$c>0$. Then, we would need to modify the definition of $S$ to be $\\{x\in
V_{1}\;:\>d^{J}(x)\geqslant\varepsilon_{1}n/\log^{1/2+c}n\\}$. However, the
assumption of Lemma 11 is no longer valid for sets $A$ of smaller size.
Therefore, we would not be able to use Lemma 11 in the proof of Lemma 17.

###  3.2 $|\bar{H}_{\pi}|>\delta pn^{3}/\log n$

All the notations and theorems here are similar to those in the previous
subsection, so we will just point out the necessary modifications. Note that
by the assumption in Proposition 12, we have
$|\bar{H}_{\pi}|\leqslant\sum_{i=1}^{3}|H_{i}|\leqslant\delta pn^{3}$. Let
$S^{\prime}=\\{x\in V_{1}:d^{J}(x)\geqslant\varepsilon_{1}n\\}$,
$S^{\prime}_{1}=\\{x\in
S^{\prime}:d^{H}_{2,3}(x)\geqslant\varepsilon_{2}pn^{2}\\}$ and
$S^{\prime}_{2}=S^{\prime}\setminus S^{\prime}_{1}$. For the following lemmas,
we always assume that $|\bar{H}_{\pi}|>\delta pn^{3}/\log n$ and the
assumptions of Proposition 12 hold.

######  Lemma 20.

With high probability $|S^{\prime}|\leqslant\varepsilon_{3}n$.

###### Proof.

Inequality (6) still holds and now we get $|J|\leqslant 48\delta n^{2}$. Every
vertex in $S^{\prime}$ has degree at least $\varepsilon_{1}n$ in $J$, so
$\varepsilon_{1}n|S^{\prime}|\leqslant 2\cdot 48\delta n^{2}$, which gives
$|S^{\prime}|\leqslant\frac{100\delta}{\varepsilon_{1}}n=\varepsilon_{3}n$. ∎

######  Lemma 21.

With high probability $|\bar{H}_{\pi}|\geqslant 20pn^{2}|S^{\prime}_{1}|$.

###### Proof.

We can assume that $|S^{\prime}_{1}|\geqslant 1$, otherwise this inequality is
trivial. For each $x\in S^{\prime}_{1}$, define

$T^{\prime}_{x}:=\\{yz\;:\>y\in V_{2},\,z\in V_{3},\,xyz\in
H,d_{S^{\prime}_{1}}(y,z)\leqslant 3\varepsilon_{3}pn\\}.$

By Lemma 20, $|S^{\prime}_{1}|\leqslant|S^{\prime}|\leqslant\varepsilon_{3}n$.
For every $s\leqslant\varepsilon_{3}n$, we have
$(s,\varepsilon_{2}pn^{2}/2,3\varepsilon_{3}pn)\in O$ (see Claim 27 in the
Appendix for the proof). Then by Lemma 9 and the definition of
$S^{\prime}_{1}$, we get that
$|T^{\prime}_{x}|\geqslant\frac{1}{2}\varepsilon_{2}pn^{2}$. Now we count
those copies of $\hat{F}_{5}=\\{x,w,y,z\\}$ where $x\in S^{\prime}_{1}$, $w\in
N^{J}(x)$, and $\\{y,z\\}\in T^{\prime}_{x}$. By Lemma 11, the number of such
copies of $\hat{F}_{5}$ is at least
$\frac{1}{4}\varepsilon_{1}\varepsilon_{2}p^{2}n^{3}|C_{1}|$. Every
$wyz\in\bar{H}_{\pi}$ can be in at most $3\varepsilon_{3}pn$ such copies of
$\hat{F}_{5}$, because $x$ is assumed to be in $S^{\prime}_{1}$ and
$d_{S^{\prime}_{1}}(y,z)\leqslant 3\varepsilon_{3}pn$. Therefore,

$|\bar{H}_{\pi}|\geqslant\frac{\frac{1}{4}\varepsilon_{1}\varepsilon_{2}p^{2}n^{3}|S_{1}|}{3\varepsilon_{3}pn}\geqslant
20pn^{2}|S_{1}|.\qed$

######  Lemma 22.

With high probability
$|\bar{H}_{\pi}|\geqslant\frac{1}{20}pn^{2}|S^{\prime}_{2}|$.

###### Proof.

Exactly the same as the proof of Lemma 18. ∎

We are now able to conclude the proof of Proposition 12 for the remaining case
that $\frac{\delta pn^{3}}{\log n}<|\bar{H}_{\pi}|\leqslant\delta pn^{3}.$

###### Proof of Proposition 12.

Similarly to the proof in the previous subsection, we define
$H^{\prime}_{1}(1)=\\{e\in H_{1}:|e\cap S^{\prime}|\geqslant 2\textrm{ or
}|e\cap V_{1}\setminus S^{\prime}|\geqslant 2\\}$, $H^{\prime}_{1}(2)=\\{e\in
H_{1}\setminus H^{\prime}_{1}(1):|e\cap S^{\prime}_{1}|=1\\}$ and
$H^{\prime}_{1}(3)=H^{\prime}_{1}\setminus(H^{\prime}_{1}(1)\cup
H^{\prime}_{1}(2))$.

We still split the proof into three cases. The cases
$3|H^{\prime}_{1}(2)|\geqslant|H_{1}|$ and
$3|H^{\prime}_{1}(3)|\geqslant|H_{1}|$ follow with the same proof as in the
previous subsection. For the case $3|H^{\prime}_{1}(1)|\geqslant|H_{1}|$, now
let $J^{\prime}=J[S^{\prime}]\cup J[V_{1}\setminus S^{\prime}]$. By Lemmas 6
and 8,

$|H^{\prime}_{1}(1)|\leqslant|J^{\prime}|\cdot 3pn+n^{2}e^{-\sqrt{\log
n}}\cdot pn\frac{\sqrt{\log n}}{\log\log n}.$ (8)

Recall we have the assumptions that $3|H_{1}|\geqslant|\bar{H}_{\pi}|$, so
$3|H^{\prime}_{1}(1)|\geqslant|H_{1}|\geqslant\delta pn^{3}/(3\log n)$. Hence
by (8), we have that $0.9|H^{\prime}_{1}(1)|\leqslant|J^{\prime}|\cdot 3pn$.
Then, by Lemma 20 and the definition of $S^{\prime}_{1}$, we get that
$\Delta(J^{\prime})\leqslant\varepsilon_{1}n$. Finally, by Lemma 15,
$|\bar{H}_{\pi}|\geqslant 30pn|J^{\prime}|\geqslant
9|H^{\prime}_{1}(1)|\geqslant 3|H_{1}|$. ∎

## References

## Appendix: Final computations

Recall
$g(p,s,r,i)=n\binom{n}{s}\binom{n^{2}}{r}\left(p\binom{s}{i}p^{i}\right)^{r}$
and $O$ is the set of $(s,r,i)$ such that $g(p,s,r,i)=o(n^{-5})$, given
$p>C\sqrt{\log n}/n$. In this appendix, we prove the following claims.

######  Claim 23.

For every positive integer $s\leqslant\frac{\varepsilon_{1}n}{\sqrt{\log n}}$,
$r=\frac{pn}{\sqrt{\log n}}s$, and $i=\frac{pn\log\log n}{500\sqrt{\log n}}$,
we have $(s,r,i)\in O$.

###### Proof.

We have

$\displaystyle g(p,s,r,i)$
$\displaystyle=n\binom{n}{s}\binom{n^{2}}{\frac{pn}{\sqrt{\log
n}}s}\left(p\binom{s}{\frac{pn\log\log n}{500\sqrt{\log
n}}}p^{\frac{pn\log\log n}{500\sqrt{\log n}}}\right)^{\frac{pn}{\sqrt{\log
n}}s}$ $\displaystyle\leqslant
n\left(\frac{en}{s}\right)^{s}\left(\frac{epn^{2}\sqrt{\log
n}}{pns}\left(\frac{500eps\sqrt{\log n}}{pn\log\log
n}\right)^{\frac{pn\log\log n}{500\sqrt{\log n}}}\right)^{\frac{pn}{\sqrt{\log
n}}s}$ $\displaystyle\leqslant
n\left(\frac{en}{s}\right)^{s}\left(\frac{en\sqrt{\log
n}}{s}\left(\frac{500es\sqrt{\log n}}{n\log\log n}\right)^{\frac{pn\log\log
n}{500\sqrt{\log n}}}\right)^{\frac{pn}{\sqrt{\log n}}s}.$ (9)

There are three cases depending on $s$.

  * •

If $1\leqslant s\leqslant\sqrt{n}$.

In this case, (9) is at most

$n(en)^{s}\left(en\sqrt{\log n}\left(\frac{\sqrt{\log
n}}{\sqrt{n}}\right)^{\frac{C\log\log n}{500}}\right)^{Cs}\leqslant
n(en)^{s}\left(\frac{1}{n}\right)^{Cs}=o(n^{-5}).$

  * •

If $\sqrt{n}\leqslant s\leqslant\frac{n}{\log n}$.

In this case, (9) is at most

$\displaystyle n\left(\frac{en}{s}\right)^{s}$
$\displaystyle\left(\frac{en\sqrt{\log
n}}{s}\left(\frac{s}{n}\right)^{100}\right)^{\frac{pn}{\sqrt{\log
n}}s}\leqslant
n\left(\frac{en}{s}\right)^{s}\left(\frac{s}{n}\right)^{\frac{pn}{\sqrt{\log
n}}s}$ $\displaystyle\leqslant
n\left(\frac{en}{s}\right)^{s}\left(\frac{s}{n}\right)^{Cs}\leqslant
n\left(\frac{s}{n}\right)^{s}\leqslant n\left(\frac{1}{\log
n}\right)^{\sqrt{n}}=o(n^{-5}).$

  * •

If $\frac{n}{\log n}\leqslant s\leqslant\frac{\varepsilon_{1}n}{\sqrt{\log
n}}$. In this case, (9) is at most

$\displaystyle n(e\log
n)^{s}\left(e\log^{3/2}n\left(\frac{500e\varepsilon_{1}}{\log\log
n}\right)^{\frac{C\log\log n}{500}}\right)^{\frac{pn}{\sqrt{\log
n}}s}\leqslant$ $\displaystyle n(e\log n)^{s}\left(\left(\frac{1}{\log\log
n}\right)^{\log\log n}\right)^{Cs}$ $\displaystyle\leqslant
n\left(\frac{1}{\log n}\right)^{s}$ $\displaystyle\leqslant
n\left(\frac{1}{\log n}\right)^{\frac{n}{\log n}}=o(n^{-5}).\qed$

######  Claim 24.

For every positive integer $s\in\big{(}\frac{\varepsilon_{1}n}{\sqrt{\log
n}},\,\varepsilon_{1}n\big{]}$, $r=\frac{pn}{500}s$, and
$i=3\varepsilon_{1}pn$, we have $(s,r,i)\in O$.

###### Proof.

We have that $g(p,s,r,i)$ is

$\displaystyle
n\binom{n}{s}\binom{n^{2}}{\frac{pn}{500}s}\left(p\binom{s}{3\varepsilon_{1}pn}p^{3\varepsilon_{1}pn}\right)^{\frac{pn}{500}s}\leqslant
n\left(\frac{en}{s}\right)^{s}\left(\frac{500pn^{2}}{pns}\left(\frac{eps}{3\varepsilon_{1}pn}\right)^{3\varepsilon_{1}pn}\right)^{\frac{pn}{500}s}$
$\displaystyle=n\left(\frac{en}{s}\right)^{s}\left(\frac{500n}{s}\left(\frac{es}{3\varepsilon_{1}n}\right)^{3\varepsilon_{1}pn}\right)^{\frac{pn}{500}s}\leqslant
n\left(\frac{e\sqrt{\log
n}}{\varepsilon_{1}}\right)^{s}\left(\frac{500\sqrt{\log
n}}{\varepsilon_{1}}\left(\frac{e}{3}\right)^{3\varepsilon_{1}C\sqrt{\log
n}}\right)^{Cs\sqrt{\log n}}$ $\displaystyle\leqslant n\left(\frac{e\sqrt{\log
n}}{\varepsilon_{1}}\right)^{s}\left(2^{-\sqrt{\log n}}\right)^{Cs\sqrt{\log
n}}\leqslant n2^{-s}\leqslant n2^{-\frac{\varepsilon_{1}n}{\sqrt{\log
n}}}=o(n^{-5}).\qed$

######  Claim 25.

For every positive integer $s\leqslant n$, we have $\left(s,\frac{pn^{2}}{\log
n},3pn\right)\in O$.

###### Proof.

We have that $g(p,s,r,i)$ is

$\displaystyle n\binom{n}{s}\binom{n^{2}}{\frac{pn^{2}}{\log
n}}\left(p\binom{s}{3pn}p^{3pn}\right)^{\frac{pn^{2}}{\log n}}\leqslant
n2^{n}\binom{n^{2}}{\frac{pn^{2}}{\log
n}}\left(p\binom{n}{3pn}p^{3pn}\right)^{\frac{pn^{2}}{\log n}}$
$\displaystyle\leqslant n2^{n}\left(\frac{epn^{2}\log
n}{pn^{2}}\left(\frac{enp}{3pn}\right)^{3pn}\right)^{\frac{pn^{2}}{\log
n}}\leqslant n2^{n}\left(e\log
n\left(\frac{e}{3}\right)^{3pn}\right)^{\frac{pn^{2}}{\log n}}$
$\displaystyle\leqslant n2^{n}\left(e\log
n\left(\frac{e}{3}\right)^{3C\sqrt{\log n}}\right)^{\frac{Cn}{\sqrt{\log
n}}}\leqslant n2^{n}\left(\left(\frac{e}{3}\right)^{\sqrt{\log
n}}\right)^{\frac{Cn}{\sqrt{\log
n}}}=n2^{n}\left(\frac{e}{3}\right)^{Cn}=o(n^{-5}).\qed$

######  Claim 26.

For every positive integer $s\leqslant\frac{\varepsilon_{3}n}{\sqrt{\log n}}$,
we have
$\left(s,\frac{\varepsilon_{2}pn^{2}}{2},\frac{3\varepsilon_{3}pn}{\sqrt{\log
n}}\right)\in O$.

###### Proof.

We have that $g(p,s,r,i)$ is

$\displaystyle
n\binom{n}{s}\binom{n^{2}}{\frac{1}{2}\varepsilon_{2}pn^{2}}\left(p\binom{s}{\frac{3\varepsilon_{3}pn}{\sqrt{\log
n}}}p^{\frac{3\varepsilon_{3}pn}{\sqrt{\log
n}}}\right)^{\frac{1}{2}\varepsilon_{2}pn^{2}}\leqslant
n\binom{n}{\frac{\varepsilon_{3}n}{\sqrt{\log
n}}}\binom{n^{2}}{\frac{1}{2}\varepsilon_{2}pn^{2}}\left(p\binom{\frac{\varepsilon_{3}n}{\sqrt{\log
n}}}{\frac{3\varepsilon_{3}pn}{\sqrt{\log
n}}}p^{\frac{3\varepsilon_{3}pn}{\sqrt{\log
n}}}\right)^{\frac{1}{2}\varepsilon_{2}pn^{2}}$ $\displaystyle\leqslant
n\left(\frac{en\sqrt{\log
n}}{\varepsilon_{3}n}\right)^{\frac{\varepsilon_{3}n}{\sqrt{\log
n}}}\left(\frac{2epn^{2}}{\varepsilon_{2}pn^{2}}\left(\frac{e\varepsilon_{3}pn}{3\varepsilon_{3}pn}\right)^{\frac{3\varepsilon_{3}pn}{\sqrt{\log
n}}}\right)^{\frac{1}{2}\varepsilon_{2}pn^{2}}$
$\displaystyle=n\left(\frac{e\sqrt{\log
n}}{\varepsilon_{3}}\right)^{\frac{\varepsilon_{3}n}{\sqrt{\log
n}}}\left(\frac{2e}{\varepsilon_{2}}\left(\frac{e}{3}\right)^{\frac{3\varepsilon_{3}pn}{\sqrt{\log
n}}}\right)^{\frac{1}{2}\varepsilon_{2}pn^{2}}$ $\displaystyle\leqslant
n\left(\frac{e\sqrt{\log
n}}{\varepsilon_{3}}\right)^{\frac{\varepsilon_{3}n}{\sqrt{\log
n}}}2^{-\frac{1}{2}\varepsilon_{2}pn^{2}}\leqslant n\left(\frac{e\sqrt{\log
n}}{\varepsilon_{3}}\right)^{\frac{\varepsilon_{3}n}{\sqrt{\log
n}}}2^{-\frac{1}{2}\varepsilon_{2}Cn\sqrt{\log n}}=o(n^{-5}).\qed$

######  Claim 27.

For every positive integer $s\leqslant\varepsilon_{3}n$, we have
$\left(s,\frac{\varepsilon_{2}pn^{2}}{2},3\varepsilon_{3}pn\right)\in O$.

###### Proof.

We have that $g(p,s,r,i)$ is

$\displaystyle
n\binom{n}{s}\binom{n^{2}}{\frac{1}{2}\varepsilon_{2}pn^{2}}\left(p\binom{s}{3\varepsilon_{3}pn}p^{3\varepsilon_{3}pn}\right)^{\frac{1}{2}\varepsilon_{2}pn^{2}}\leqslant
n\binom{n}{\varepsilon_{3}n}\binom{n^{2}}{\frac{1}{2}\varepsilon_{2}pn^{2}}\left(p\binom{\varepsilon_{3}n}{3\varepsilon_{3}pn}p^{3\varepsilon_{3}pn}\right)^{\frac{1}{2}\varepsilon_{2}pn^{2}}$
$\displaystyle\leqslant
n\left(\frac{en}{\varepsilon_{3}n}\right)^{\varepsilon_{3}n}\left(\frac{2epn^{2}}{\varepsilon_{2}pn^{2}}\left(\frac{e\varepsilon_{3}pn}{3\varepsilon_{3}pn}\right)^{3\varepsilon_{3}pn}\right)^{\frac{1}{2}\varepsilon_{2}pn^{2}}=n\left(\frac{e}{\varepsilon_{3}}\right)^{\varepsilon_{3}n}\left(\frac{2e}{\varepsilon_{2}}\left(\frac{e}{3}\right)^{3\varepsilon_{3}pn}\right)^{\frac{1}{2}\varepsilon_{2}pn^{2}}$
$\displaystyle\leqslant n2^{-n\sqrt{\log n}}=o(n^{-5}).\qed$