$B_{u}^{f}=V_{j_{0}}$. Then for each $u,v,w\in[k]$ and $f\in I$, define
$Q_{A_{u}B_{v}^{f}}=P_{i_{u},j_{0}}^{\alpha_{u}}$,
$Q_{A_{u}C_{w}}=P_{i_{u},k_{0}}^{\beta_{u}}$ and
$Q_{B_{v}^{f}C_{w}}=P_{j_{0}k_{0}}^{\gamma_{f(v,w)}}$. For each $u,v,w\in[k]$
and $f\in I$, let

$\displaystyle G_{uvw}^{f}$ $\displaystyle=(A_{u}\cup B^{f}_{v}\cup
C_{w},Q_{A_{u}C_{w}}\cup Q_{A_{u}B_{v}^{f}}\cup Q_{B_{v}^{f}C_{w}})\text{ and
}$ $\displaystyle H_{uvw}^{f}$ $\displaystyle=(A_{u}\cup B^{f}_{v}\cup
C_{w},E\cap K_{3}^{(2)}(G_{uvw}^{f})).$

By Proposition 2.22, we know that for each $u,v,w\in[k]$ and $f\in I$,
$(H_{uvw}^{f},G_{uvw}^{f})$ satisfies
$\textnormal{disc}_{2,3}(\delta_{3},\delta_{2}(\ell))$, with density at least
$1-\epsilon_{1}$ if $u\leq f(v,w)$ and at most $\epsilon_{1}$ if $u>f(u,w)$.
By Theorem 3.1, there are at least $(1/\ell)^{m\choose
2}(1-\epsilon_{1})^{m\choose 3}(n/t)^{m}>0$ many tuples
$(a_{u})_{u\in[k]}(b^{f}_{v})_{v\in[k],f\in
I}(c_{w})_{w\in[k]}\in\prod_{u=1}^{k}A_{u}\times\prod_{v\in[k],f\in
I}B_{v}^{f}\times\prod_{w=1}^{k}C_{w}$ such that $a_{u}b_{v}^{f}c_{w}\in E$ if
and only if $u\leq f(v,w)$. Note that for each such tuple, $a_{u}\in
V_{i_{u}}$ for each $u\in[k]$, $\\{b_{v}^{f}:v\in[k],f\in I\\}\subseteq
V_{j_{0}}$, and $\\{c_{w}:w\in[k]\\}\subseteq V_{k_{0}}$. Thus (1) holds.

To prove (2), we proceed in the same way, but make the following small
adjustments in the third paragraph. For each $u\in[k]$, set $C_{u}=V_{j_{0}}$,
and for each $v\in[k]$ and $f\in I$, set $B_{v}^{f}=V_{k_{0}}$. As before,
define $A_{u}=V_{i_{u}}$ for each $u\in[k]$. Then for each $u,v,w\in[k]$ and
$f\in I$, define $Q_{A_{u}B_{v}^{f}}=P_{i_{u},k_{0}}^{\alpha_{u}}$,
$Q_{A_{u}C_{w}}=P_{i_{u},j_{0}}^{\beta_{u}}$ and
$Q_{B_{v}^{f}C_{w}}=P_{j_{0}j_{0}}^{\gamma_{f(v,w)}}$. One then finishes the
proof in the same way to obtain (2). ∎

Note that in Proposition 5.7, we in fact found many copies of $F(k)$ in
$\text{Trip}(H)$. We are now able to prove Theorem 5.5.

Proof of Theorem 5.5: Suppose that $\mathcal{H}$ encodes $U(k)$. Let
$\epsilon_{1}>0$ and $\epsilon_{2}:\mathbb{N}\rightarrow(0,1]$ be as in
Proposition 5.6. Let $T=T(\epsilon_{1},\epsilon_{2})$ and
$L=(\epsilon_{1},\epsilon_{2})$ be as in the definition of $U(k)$ being
encoded in $\mathcal{H}$. Let $N=N(T,L)$ be as in Proposition 5.6. Since
$U(k)$ is encoded in $\mathcal{H}$ there is $H=(V,E)\in\mathcal{H}$ with
$|V|\geq N$, some $t\leq T$, $\ell\leq L$, a
$(t,\ell,\epsilon_{1},\epsilon_{2}(\ell))$-decomposition $\mathcal{P}$ of $V$,
and an encoding of $U(k)$ in $(H,\mathcal{P})$. By Proposition 5.6, $H$ has
$k$-$\operatorname{IP}_{2}$, so $\mathcal{H}$ has $k$-$\operatorname{IP}_{2}$.

Suppose now that $\mathcal{H}$ encodes $H(k)$. Let $\epsilon_{1}>0$ and
$\epsilon_{2}:\mathbb{N}\rightarrow(0,1]$ be as in Proposition 5.7. Let
$T=T(\epsilon_{1},\epsilon_{2})$ and $L=(\epsilon_{1},\epsilon_{2})$ be as in
the definition of $H(k)$ being encoded in $\mathcal{H}$. Let $N=N(T,L)$ be as
in Proposition 5.6. Since $H(k)$ is encoded in $\mathcal{H}$ there are
$H=(V,E)\in\mathcal{H}$ with $|V|\geq N$, some $t\leq T$, $\ell\leq L$, a
$(t,\ell,\epsilon_{1},\epsilon_{2}(\ell))$-decomposition $\mathcal{P}$ of $V$,
and an encoding of $H(k)$ in $(H,\mathcal{P})$. By Proposition 5.7, $H$ has
$k$-$\operatorname{FOP}_{2}$, so $\mathcal{H}$ has
$k$-$\operatorname{FOP}_{2}$. ∎

Theorem 5.5 showed that if $\mathcal{H}$ encodes $H(k)$ (respectively $U(k)$)
for all $k$ , then $\mathcal{H}$ has $\operatorname{FOP}_{2}$ (respectively
$\operatorname{IP}_{2}$). Our next goal is to show that the converse of these
implications is also true, i.e. if $\mathcal{H}$ has $\operatorname{FOP}_{2}$
(respectively $\operatorname{IP}_{2}$), then it encodes $H(k)$ (respectively
$U(k)$) for all $k$.

We will first prove this for $\operatorname{FOP}_{2}$. This will require Lemma
5.8 below, which shows we can construct certain $3$-graphs from $F(n)$, when
$n$ is large.

######  Lemma 5.8.

For all $m,k\geq 1$, there is $N$ such that the following holds. Suppose
$n\geq N$, $U$ and $W$ are sets of size $m$, $\bigcup_{\alpha\leq
k}P^{\alpha}$ is a partition of $K_{2}[U,W]$, and $H=(A\cup B\cup C,E)$ is a
clean copy of $F(n)$.

Then there exist disjoint sets $Z_{1},\ldots,Z_{k}\subseteq C$, each of size
$m$, along with $\\{a_{1},\ldots,a_{m}\\}\subseteq A$ and
$\\{b_{1},\ldots,b_{m}\\}\subseteq B$ such that the following hold, where
$Q^{\alpha}=\\{x_{i}y_{j}:u_{i}w_{j}\in P^{\alpha}\\}$. For all $z\in
Z_{\beta}$ and $xy\in Q^{\alpha}$, $xyz\in E$ if and only if
$\beta\leq\alpha$.

###### Proof.

Fix $m,k\geq 1$. Choose $N\gg m,k$. Suppose $U$ and $W$ are sets of size $m$
and $\bigcup_{\alpha\leq k}P^{\alpha}$ is a partition of $K_{2}[U,W]$.

Assume $n\geq N$ and $H=(A\cup B\cup C,E)$ is a clean copy of $F(n)$. We may
assume that $A=\\{a_{i}:i\in[n]\\}$,
$B=\\{b_{i}^{f}:i\in[n],f:[n]^{2}\rightarrow[n]\\}$, and
$C=\\{c_{i}:i\in[n]\\}$ are such that $a_{i}b_{j}^{f}c_{s}\in E$ if and only
if $s\leq f(i,j)$.

Define a function $g:[n]^{2}\rightarrow[n]$, as follows. For each
$(s,t)\in[m]^{2}$, set let $g(s,t)=m\alpha$, where $\alpha$ is such that
$u_{s}w_{t}\in P_{UW}^{\alpha}$. For all $(s,t)\in[n]^{2}\setminus[m]^{2}$,
define $g(s,t)=1$. Let $X=\\{a_{1},\ldots,a_{m}\\}$ and
$Y=\\{b_{1}^{g},\ldots,b_{n}^{g}\\}$. For each $1\leq i\leq k$, define
$Z_{\alpha}=\\{c_{j}:j\in((\alpha-1)m,\alpha m]\\}$. For each $\alpha\leq k$,
let $Q^{\alpha}=\\{a_{i}b^{g}_{j}:u_{i}w_{j}\in P_{UW}^{\alpha}\\}$. Now
consider some $1\leq i,j,s\leq m$, and $a_{i}b_{j}^{g}c_{s}\in
K_{3}[X,Y,Z_{1}\cup\ldots\cup Z_{k}]$. By construction there are some
$\alpha,\beta\in[k]$ so that $c_{s}\in Z_{\beta}$ and $a_{i}b_{j}^{g}\in
Q^{\alpha}$. By assumption on $H$, $a_{i}b^{g}_{j}c_{s}\in E$ if and only if
$s\leq g(i,j)$. By definition of $g$, $g(i,j)=m\alpha$, and by definition of
$Z_{\beta}$, $(\beta-1)<s\leq\beta m$. Thus $s\leq g(i,j)$ if and only if
$\beta\leq\alpha$. ∎

Note that in Lemma 5.8, the partition of $K_{2}[U,W]$ is completely arbitrary.
This will be used in the “(2) $\Rightarrow$ (1)” direction of the following
equivalence.

######  Proposition 5.9.

Suppose $\mathcal{H}$ is a hereditary $3$-graph property. Then the following
are equivalent.

  1. (1)

$H(k)$ is encoded in $\mathcal{H}$ for all $k\geq 1$,

  2. (2)

$\mathcal{H}$ has $k$-$\operatorname{FOP}_{2}$ for all $k\geq 1$.

###### Proof.

That (1) implies (2) is immediate from Proposition 5.7 and Definition 5.4. We
now prove (2) implies (1). Suppose $\mathcal{H}$ has
$m$-$\operatorname{FOP}_{2}$ for all $m$. Fix $k\geq 1$. We show $H(k)$ is
binary encoded in $\mathcal{H}$. Fix $\epsilon_{1},\rho>0$,
$\epsilon_{2}:\mathbb{N}\rightarrow(0,1]$. Let $N,T,L\geq 1$ be as in Theorem
1.13 for $\epsilon_{1}$, $\epsilon_{2}$, $t_{0}=2k+k^{2k}$, and $\ell_{0}=1$.
Let $n\gg_{\epsilon_{1},\epsilon_{2},T,L}N$. Fix sets
$U,W,V_{1},\ldots,V_{k}$, each of size $n$, and any partitions
$K_{2}[U,W]=\bigcup_{\alpha\leq k}P_{UW}^{\alpha}$,
$K_{2}[V_{i},U]=\bigcup_{\alpha\leq k}P_{V_{i}U}^{\alpha}$, and
$K_{2}[V_{i},W]=\bigcup_{\alpha\leq k}P_{V_{i}W}^{\alpha}$ such that each
$P_{V_{i}U}^{\alpha}$, $P_{V_{i}W}^{\alpha}$, and $P_{WU}^{\alpha}$ satisfy
$\textnormal{disc}_{2}(\epsilon_{2}(L),1/k)$. Such a partition exists by Lemma
2.24.

Let $M\gg n$. Since $\mathcal{H}$ has $\operatorname{FOP}_{2}$, by Lemma 2.31,
it contains a clean copy of $F(M)$, say $H=(X\sqcup Y\sqcup Z,E)$. By Lemma
5.8, there are $X^{\prime}=\\{x_{1},\ldots,x_{n}\\}\subseteq X$,
$Y^{\prime}=\\{y_{1},\ldots,y_{n}\\}\subseteq Y$, and
$Z_{1}^{\prime},\ldots,Z_{k}^{\prime}\subseteq Z$ such that if
$Q_{XY}^{\alpha}=\\{x_{i}y_{j}:u_{i}w_{j}\in P_{WU}^{\alpha}\\}$, then the
following holds: for all $z\in Z_{\beta}$ and $x_{i}y_{j}\in Q_{XY}^{\alpha}$,
$zx_{i}y_{j}\in E$ if and only if $\beta\leq\alpha$.

For each $m\in[k]$ and $\alpha\in[k]$, choose partitions
$K_{2}[X^{\prime},Z^{\prime}_{m}]=\bigcup_{\alpha\leq k}Q_{XZ_{m}}^{\alpha}$
and $K_{2}[Y^{\prime},Z^{\prime}_{m}]=\bigcup_{\alpha\leq
k}Q_{YZ_{m}}^{\alpha}$ so that for each $\alpha\leq k$, $Q_{XZ_{m}}^{\alpha}$
and $Q_{YZ_{m}}^{\alpha}$ satisfy $\textnormal{disc}_{2}(\epsilon_{2}(k),1/k)$
(such partitions exist by Lemma 2.24). Define the decomposition $\mathcal{Q}$
of $V^{\prime}=X^{\prime}\cup Y^{\prime}\cup\bigcup_{i=1}^{k}Z_{i}^{\prime}$
with
$\mathcal{Q}_{vert}=\\{X^{\prime},Y^{\prime},Z_{1}^{\prime},\ldots,Z_{k}^{\prime}\\}$
and $\mathcal{Q}_{edge}=\\{Q_{XY}^{\alpha}:\alpha\leq
k\\}\cup\\{Q^{\alpha}_{YZ_{m}},P_{XZ_{m}}^{\alpha}:m\in[k],\alpha\leq k\\}$.
By construction, $\mathcal{Q}$ is a
$(2+k,k,\epsilon_{1},\epsilon_{2}(k))$-decomposition $V^{\prime}$. Let
$H^{\prime}=H[V^{\prime}]$. Clearly there is an encoding of $H(k)$ in
$(H^{\prime},\mathcal{Q})$, namely $(f,g)$, where $f:a_{i}\mapsto P_{XY}^{i}$
and $g:b_{j}\mapsto P_{XZ_{j}}^{1}\cup P_{XZ_{j}}^{1}$. We have now shown (1)
holds, as desired. ∎

We will now prove the analogous result for $U(k)$ and $\operatorname{IP}_{2}$.

######  Proposition 5.10.

Suppose $\mathcal{H}$ is a hereditary $3$-graph property. Then the following
are equivalent.

  1. (1)

$U(k)$ is binary encoded in $\mathcal{H}$ for all $k\geq 1$,

  2. (2)

$\mathcal{H}$ has $k$-$\operatorname{IP}_{2}$ for all $k\geq 1$.

###### Proof.

That (1) implies (2) follows immediately from Proposition 5.6 and Definition
5.4. Conversely, assume $\mathcal{H}$ has $m-\operatorname{IP}_{2}$ for all
$m\geq 1$. Fix $\epsilon_{1}>$, $\epsilon_{2}:\mathbb{N}\rightarrow(0,1]$, and
set $\ell=2^{k}$ and $t=2^{k}+2$. Choose $N$ as in Lemma 2.24 for
$\epsilon=\delta=\epsilon_{2}(\ell)$ and $\ell$. Suppose $n\geq N$, and $B$,
$C$, and $A_{1},\ldots,A_{\ell}$ are sets of size $n$. By Lemma 2.24, there
exists a partition $K_{2}[B,C]=\bigcup_{S\subseteq[k]}P_{BC}^{S}$ so that each
$P_{BC}^{S}$ has $\textnormal{disc}_{2}(\epsilon_{2}(\ell),1/\ell)$. Let
$H=(V,E)$ be the $3$-partite $3$-graph with vertex set $A_{1}\cup\ldots\cup
A_{\ell}\cup B\cup C$, and edge set $\bigcup_{S\subseteq[k]}\bigcup_{i\in
S}\\{u_{i}bc:bc\in P_{BC}^{S}\\}$.

By Fact 2.30, there is $H^{\prime}=(V^{\prime},E^{\prime})\in\mathcal{H}$ be a
clean copy of $H$. We may assume $V^{\prime}=X_{1}\cup\ldots\cup X_{\ell}\cup
Y\cup Z$ where $Y=\\{y_{b}:b\in B\\}$, $Z=\\{z_{c}:c\in C\\}$, for each
$i\in[\ell]$, $X_{i}=\\{x_{a}:a\in A_{i}\\}$ and so that $x_{a}y_{b}z_{c}\in
E^{\prime}$ if and only if $abc\in E$. Use Lemma 2.24 to choose partitions
$K_{2}[A_{i},B]=\bigcup_{\alpha\leq\ell}Q_{A_{i}B}^{\alpha}$ and
$K_{2}[A_{i},B]=\bigcup_{\alpha\leq\ell}P_{A_{i}C}^{\alpha}$ so that each
$Q_{A_{i}B}^{\alpha}$, $Q_{A_{i}C}^{\alpha}$ satisfies
$\textnormal{disc}_{2}(\epsilon_{2}(\ell),1/\ell)$. For each $S\subseteq[k]$,
let $Q_{BC}^{\alpha}=\\{y_{b}z_{c}:bc\in P_{BC}^{S}\\}$. Let $\mathcal{Q}$ be
the decomposition of $V^{\prime}$ with
$\mathcal{Q}_{vert}=\\{A_{1},\ldots,A_{\ell},B,C\\}$ and

$\mathcal{Q}_{edge}=\\{Q_{A_{i}B}^{\alpha}:i\in[k],\alpha\leq\ell\\}\cup\\{Q_{A_{i}C}^{\alpha}:i\in[k],\alpha\leq\ell\\}\cup\\{Q_{BC}^{S}:S\subseteq[k]\\}.$

By construction, $\mathcal{Q}$ is a
$(t,\ell,\epsilon_{1},\epsilon_{2}(\ell))$-decomposition of $V^{\prime}$.
Clearly $U(k)$ is encoded in $(H^{\prime},\mathcal{Q})$ via $f:a_{i}\mapsto
Q_{A_{i}B}^{1}Q_{A_{i}C}^{1}$ and $g:c_{S}\mapsto Q_{BC}^{S}$. This shows
$U(k)$ is encoded in $\mathcal{H}$, so (1) holds. ∎

###  5.2. Removal in almost stable bipartite graphs

In this section, we prove a removal type result, which roughly says the
following. If a bipartite graph $G=(U\cup W,E)$ contains few $d$-trees with
leaves in $W$, then it is close to a graph in which ${\mathrm{rk}}(W)\leq d$.
We begin with a definition which will help us keep tabs on the locations of
the leaves and nodes of a $d$-tree.

######  Definition 5.11.

Suppose $d\geq 1$, $G=(V,E)$ is a bipartite graph, and $A,B\subseteq V$. An
$(A,B,d)$-tree in $G$ is a $d$-tree in $G$ with leaves in $B$ and nodes in
$A$.

We now define a notion of closeness tailored to the bipartite setting.

######  Definition 5.12.

Suppose $\delta>0$ and $G=(U\cup W,E)$, $G^{\prime}=(U\cup W,E^{\prime})$ are
bipartite graphs. Then $G$ and $G^{\prime}$ are _uniformly
$(U,W,\delta)$-close_ if for all $u\in U$, $|N_{G}(u)\Delta
N_{G^{\prime}}(u)|\leq\delta|W|$.

Definition 5.12 is clearly stronger than the notion of $\delta$-closeness
(recall $G$ and $G^{\prime}$ on the same vertex set are $\delta$-close if
$|E(G)\Delta E(G^{\prime})|\leq\delta|V(G)|^{2}$). We will need this extra
strength in our proof of Theorem 1.56. We can now state our removal lemma.

######  Theorem 5.13.

For all $d\geq 1$ and $0<\epsilon<1/9$, there is $\delta_{0}(\epsilon,d)$ such
that for all $0<\delta<\delta_{0}$ there is $\rho=\rho(\epsilon,d,\delta)>0$
and $N=N(\epsilon,d,\rho)$ such that the following holds.

Suppose $G=(U\cup W,E)$ is a bipartite graph with $|U|,|W|\geq N$ and the
number of $(U,W,d)$-trees in $G$ is at most $\rho|U|^{2^{d}-1}|W|^{2^{d}}$.
Then there is $U_{0}\subseteq U$ and $W_{0}\subseteq W$ such that
$|U_{0}|\leq\delta|U|$, $|W_{0}|\leq\epsilon|W|$, and a bipartite graph
$G^{\prime}=((U\setminus U_{0})\cup(W\setminus W_{0}),E^{\prime})$ and so that
$G[U\setminus U_{0},W\setminus W_{0}]$ is uniformly $(U\setminus
U_{0},W\setminus W_{0},\delta)$-close to $G^{\prime}$, and so that
$G^{\prime}$ contains no $(U\setminus U_{0},W\setminus W_{0},d)$-trees.

In the proof of Theorem 1.56, we will apply Theorem 5.13 to a graph $G=(U\cup
W,E)$ containing few $(U,W,d)$-trees and where $|W|\ll|U|$. This imbalance in
the size of the parts is another reason we require Theorem 5.13, and cannot
use an off-the-shelf removal lemma, such as Lemma 2.7.

We begin with a lemma which shows that if a bipartite graph $G=(U\cup W,E)$
contains few $(U,W,d)$-trees, then $W$ can be almost partitioned into almost
good sets. This can be thought of as a version of Theorem 4.15 with a weaker
conclusion, but which has the advantage of more general hypotheses. In
particular, Lemma 5.14 applies when there are few $(U,W,d)$-trees (rather than
none, as required in Theorem 4.15).

######  Lemma 5.14.

For all $d\geq 1$, there is $C=C(d)>0$ such that for all $0<\epsilon<1/9$,
there is $\mu_{0}(\epsilon,d)>0$, such that for all $0<\mu<\mu_{0}$, there are
$M=M(\epsilon,d,\mu)$ and $N=N(\epsilon,d,\mu)$ such that the following holds.

Suppose $G=(U\cup W,E)$ is a bipartite graph with $|U|,|W|\geq N$ and such
that the number of $(U,W,d)$-trees in $G$ is at most
$\mu^{C}|U|^{2^{d}-1}|W|^{2^{d}}$. Then there is $m\leq M$,
$U^{\prime}\subseteq U$ of size at most $\mu|U|$, and a partition $W_{0}\cup
W_{1}\cup\ldots\cup W_{m}$ such that $|W_{0}|\leq\epsilon|W|$, and such that
for each $1\leq i\leq m$, $|W_{i}|\geq|W|/M$ and $W_{i}$ is $\mu$-good with
respect to all $u\in U\setminus U^{\prime}$.

###### Proof.

We proceed by induction on $d$. Suppose first $d=1$. In this case, set $C=4$.
Given $0<\epsilon<1/4$, set $N=M=1$ and let $\mu_{0}=\epsilon$.

Now assume $0<\mu<\mu_{0}$, and $G=(U\cup W,E)$ is a bipartite graph
containing at most $\mu^{C}|U||W|^{2}$ many $(U,W,1)$-trees. Note that for all
$u\in U$, if $uw_{1}\in E$ and $uw_{0}\notin E$, then $(u,w_{0},w_{1})$ is a
$(U,W,1)$-tree. Thus, for all $u\in U$, there are at $|N(u)\cap W||\neg
N(u)\cap W|$ many $(U,W,1)$-trees in $G$ with $a_{<>}=u$. Consequently there
must be a set $U^{\prime}\subseteq U$ of size at most $\mu^{C/2}|U|$, such
that for all $u\in U\setminus U^{\prime}$, $|N(u)\cap W||\neg N(u)\cap
W|\leq\mu^{C/2}|W|^{2}$ (since otherwise, $G$ would contain more than
$\mu^{C}|U||W|^{2}$ many $(U,W,1)$-trees). This means that for all $u\in
U\setminus U^{\prime}$, we must have that $\min\\{|N(u)\cap W|,|\neg N(u)\cap
W|\\}\leq\mu^{C/4}|W|=\mu|W|$. This shows that $W$ itself is $\mu$-good with
respect to all $u\in U\setminus U^{\prime}$. This finishes the case $d=1$.

Suppose now $d>1$, and assume that for all $1\leq d^{\prime}<d$, we have
defined $C(d^{\prime})$, $\mu_{0}(d^{\prime},\epsilon^{\prime})$,
$N(d^{\prime},\epsilon^{\prime},\mu)$, and
$M(d^{\prime},\epsilon^{\prime},\mu)$, for all all $0<\epsilon^{\prime}<1/4$
and all $0<\mu<\mu_{0}(d^{\prime},\epsilon^{\prime})$. Set
$C^{\prime}=C(d-1)$, and define $C(d)=8C^{\prime}+2^{d}+2$. Fix
$0<\epsilon<1/4$. Define
$\mu_{0}(d,\epsilon)=\epsilon^{2^{d+1}}\mu_{0}(\epsilon,d-1)/4$. Given
$0<\mu<\mu_{0}$, let $N^{\prime}=N(d-1,\epsilon^{5},\mu^{4})$ and
$M^{\prime}=M(d-1,\epsilon^{5},\mu^{4})$. Finally, we define
$M=M(d,\epsilon):=\epsilon^{-100}M^{\prime}$ and
$N=N(d,\epsilon):=\epsilon^{-100}N^{\prime}M^{\prime}$.

Suppose $G=(U\cup W,E)$ is a bipartite graph with $|U|,|W|\geq N$, and assume
there are at most $\mu^{C}|U|^{2^{d}-1}|W|^{2^{d}}$ many $(U,W,d)$-trees in
$G$. We define an integer $s$ and a sequence $W_{0},\ldots,W_{s}$ and
$Z_{0},\ldots,Z_{s}$ as follows.

Step 0: Let $W_{0}=\emptyset$ and $Z_{0}=W$.

Step $i+1$: Suppose we have defined $W_{0},\ldots,W_{i}$, $Z_{0},\ldots,Z_{i}$
so that for each $0\leq i^{\prime}\leq i$,
$Z_{i^{\prime}}=W\setminus(\bigcup_{u=0}^{i^{\prime}}W_{u})$, and for all
$1\leq i^{\prime}\leq i$, there are at most
$\mu^{4C^{\prime}}|U|^{2^{d-1}-1}|W_{i^{\prime}}|^{2^{d-1}}$ many
$(U,W_{i^{\prime}},d-1)$-trees in $G$, and
$|W_{i^{\prime}}|\geq\epsilon^{2}\mu|W|$. Let

$U_{i+1}=\\{u\in U:\min\\{|N(u)\cap Z_{i}|,|\neg N(u)\cap
Z_{i}|\\}\geq\mu|Z_{i}|\\}.$

If either $|Z_{i}|\leq\epsilon^{2}|W|$ or $|U_{i+1}|\leq\mu|U|$, define $s=i$
and end the construction.

Otherwise, for each $u\in U_{i+1}$ set $W_{i,1}(u)=N(u)\cap Z_{i}$ and
$W_{i,0}(u)=\neg N(u)\cap Z_{i}$. By definition of $U_{i+1}$ and by assumption
on the size of $Z_{i}$, we know that for all $u\in U_{i+1}$, both $W_{i,1}(u)$
and $W_{i,0}(u)$ have size at least $\mu|Z_{i}|\geq\mu\epsilon^{2}|W|$.

Let $U_{i+1}^{\prime}$ be the set of $u\in U_{i+1}$ for which there more than
$\mu^{4C^{\prime}}|U|^{2^{d-1}-1}|W_{i,1}(u)|^{2^{d-1}}$ many
$(U,W_{i,1}(u),d-1)$-trees and more than
$\mu^{4C^{\prime}}|U|^{2^{d-1}-1}|W_{i,0}(u)|^{2^{d-1}}$ many
$(U,W_{i,0}(u),d-1)$-tree in $G$. We claim that $U_{i+1}\setminus
U_{i+1}^{\prime}\neq\emptyset$. Indeed, suppose not. Then we construct many
copies of $T(d)$ as follows.

  * •

Choose $u\in U_{i+1}^{\prime}$ and set $u_{<>}=u$. There are
$|U^{\prime}_{i+1}|=|U_{i+1}|>\mu|U|$ choices.

  * •

Choose $(u^{1}_{\sigma})_{\sigma\in 2^{<d-1}}(w^{1}_{\rho})_{\rho\in 2^{d-1}}$
a $(U,W_{i,1}(u),d-1)$-tree in $G$, and for each $\sigma\in 2^{<d-1}$ and
$\rho\in 2^{d-1}$, set $u_{1\wedge\sigma}=u_{\sigma}^{1}$ and
$w_{1\wedge\rho}=w_{\rho}^{1}$. By assumption, there more than

$\mu^{4C^{\prime}}|U|^{2^{d-1}-1}|W_{i,1}(u)|^{2^{d-1}}\geq\mu^{4C^{\prime}}|U|^{2^{d-1}-1}(\mu\epsilon^{2}|W|)^{2^{d-1}}$

ways to do this, where the inequality is because $u\in U_{i+1}$.

  * •

Choose $(u^{0}_{\sigma})_{\sigma\in 2^{<d-1}}(w^{0}_{\rho})_{\rho\in 2^{d-1}}$
a $(U,W_{i,0}(u),d-1)$-tree in $G$, and for each $\sigma\in 2^{<d-1}$ and
$\rho\in 2^{d-1}$, set $u_{0\wedge\sigma}=u_{\sigma}^{1}$ and
$w_{0\wedge\rho}=w_{\rho}^{1}$. By assumption, there are more than

$\mu^{4C^{\prime}}|U|^{2^{d-1}-1}|W_{i,1}(u)|^{2^{d-1}}\geq\mu^{4C^{\prime}}|U|^{2^{d-1}-1}(\mu\epsilon^{2}|W|)^{2^{d-1}}$

ways to do this, where the inequality is because $u\in U_{i+1}$.

Every such construction produces a distinct tuple $(u_{\sigma})_{\sigma\in
2^{<d}}(w_{\rho})_{\rho\in 2^{d}}$ which is a $(U,W,d)$-tree in $G$. But this
means the number of $(U,W,d)$-trees in $G$ is at least the following,

$(\mu|U|)(\mu^{4C^{\prime}}|U|^{2^{d-1}-1}(\mu\epsilon^{2}|W|)^{2^{d-1}})^{2}=\epsilon^{2^{d+1}}\mu^{8C^{\prime}+2^{d}}|U|^{2^{d}-1}|W|^{2^{d}}>\mu^{C}|U|^{2^{d}-1}|W|^{2^{d}},$

where the inequality uses that $\mu<\mu_{0}$ and the definition of $C$. This
is a contradiction, so we must have that $U_{i+1}\setminus
U_{i+1}^{\prime}\neq\emptyset$.

Thus we may choose some $u\in U_{i+1}\setminus U_{i+1}^{\prime}$. By
definition of $U^{\prime}_{i+1}$, there is some
$W_{i+1}\in\\{W_{i,1}(u),W_{i,0}(u)\\}$ with the property that there are at
most $\mu^{4C^{\prime}}|U|^{2^{d-1}-1}|W_{i+1}|^{2^{d-1}}$ many
$(U,W_{i+1},d-1)$-trees in $G$. Set
$Z_{i+1}=W\setminus(\bigcup_{j=1}^{i+1}W_{j})$. This ends step $i+1$.

Clearly this construction will end in some $s\leq\epsilon^{-2}\mu^{-1}$ steps
(since otherwise $|\bigcup_{i=1}^{s}W_{i}|>|W|$). At the end, we will have a
partition $W=W_{1}\cup\ldots\cup W_{s}\cup Z_{s}$, where
$|Z_{s}|\leq\epsilon^{2}|W|$, and where for each $1\leq i\leq s$, there are at
most $\mu^{4C^{\prime}}|U|^{2^{<d-1}}|W_{i}|^{2^{d-1}}$ many
$(U,W_{i},d-1)$-trees in $G$ and $|W_{i}|\geq\mu\epsilon^{2}|W|\geq
N^{\prime}=N(\epsilon^{2},d-1,\mu^{4})$. For each $i\in[s]$, the inductive
hypothesis applied to $G[U\cup W_{i}]$ implies there is some $s_{i}\leq
M^{\prime}=M(\epsilon^{2},d-1,\mu^{4})$, a partition $W_{i}=W_{i,0}\cup
W_{i,1}\cup\ldots\cup W_{i,s_{i}}$, and $U_{i}\subseteq U$ such that
$|U_{i}|\leq\mu^{4}|U|$, $|W_{i,0}|\leq\epsilon^{2}|W_{i}|$, and such that for
each $j\in[s_{i}]$, $W_{i,j}$ is $\mu^{4}$-good in $G[U\cup W_{i}]$ with
respect to every $u\in U\setminus U_{i}$. Clearly this implies each $W_{i,j}$
is $\mu^{4}$-good with respect to every $u\in U\setminus U_{i}$ in $G$ as
well. Observe that each $|W_{i,j}|\geq\mu\epsilon^{2}|W|/M^{\prime}\geq|W|/M$.

Set $U_{0}=\bigcup_{i=1}^{s}U_{i}$ and
$W_{0}=Z_{s}\cup\bigcup_{i=1}^{s}W_{i,0}$. Since $s\leq\epsilon^{-2}\mu^{-1}$,
$|U_{0}|\leq\mu^{4}\epsilon^{-2}\mu^{-1}|U|<\mu^{2}|U|$. Further,

$|W_{0}|\leq\epsilon^{2}|W|+\epsilon^{2}\sum_{i=1}^{s}|W_{i}|\leq
2\epsilon^{2}|W|\leq\epsilon|W|.$

Let $W_{1}^{\prime},\ldots,W_{m^{\prime}}$ enumerate $\\{W_{i,j}:1\leq i\leq
s,1\leq j\leq s_{i}\\}$. Note

$m^{\prime}=\sum_{i=1}^{s}s_{i}\leq
sM^{\prime}\leq\epsilon^{-2}\mu^{-1}M^{\prime}\leq M.$

Thus we have a partition $W=W_{0}\cup W_{1}^{\prime}\cup\ldots\cup
W_{m^{\prime}}$, where $m^{\prime}\leq M$, $|W_{0}|\leq\epsilon|W|$, and such
that for each $1\leq u\leq m^{\prime}$, $W_{u}^{\prime}$ is $\mu$-good to
every $u\in U\setminus U_{0}$ and satisfies $|W_{u}^{\prime}|\geq\mu|W|/M$.
This finishes the proof. ∎

The last remaining ingredient is a bipartite counting lemma (for a proof, see
Appendix E of [54]).

######  Lemma 5.15.

For all $k\geq 1$ and $\epsilon>0$ there are $\eta>0$ and $N$ such that the
following hold. Suppose $F=(U\cup W,R)$ is a bipartite graph with $|U|+|W|=k$.
Assume $G=(V,E)$ is a graph, and $V=\bigcup_{u\in U}V_{u}\cup\bigcup_{w\in
W}V_{w}$ is a partition of $V$ into parts of size at least $N$. Suppose that
for each $uw\in R$, $|E\cap K_{2}[V_{u},V_{w}]|\geq(1-\eta)|V_{u}||V_{w}|$,
and for each $uw\notin R$, $|E\cap K_{2}[V_{u},V_{w}]|\leq\eta|V_{u}||V_{w}|$.
Then there are at least $(1-\epsilon)\prod_{x\in U\cup W}|V_{x}|$ many tuples
$(v_{u})_{u\in U}(v_{w})_{w\in W}\in\prod_{u\in U}V_{u}\times\prod_{w\in
W}V_{w}$ such that $v_{u}v_{w}\in E$ if and only if $uw\in R$.

Proof of Theorem 5.13: Fix $d\geq 1$ and $0<\epsilon<1/9$. Let
$\eta=\eta(2^{d}+2^{d}-1,1/2)$ and $N_{2}=N_{2}(2^{d}+2^{d}-1,1/2)$ be from
Lemma 5.15. Let $C=C(d)$ and $\mu_{0}(\epsilon,d)$ be from Lemma 5.14. Set
$\delta_{0}=\min\\{\mu_{0}(\epsilon,d),\eta\\}$. Given $0<\delta<\delta_{0}$,
let $M=M(\epsilon,\delta,d)$, $N_{1}=N_{1}(\epsilon,\delta,d)$ be from Lemma
5.14. Then define $\rho=\frac{1}{4}(\delta/M2^{M})^{C}$ and let
$N=2^{M}\mu^{-1}\max\\{N_{1},N_{2}\\}$.

Suppose $G=(U\cup W,E)$ is a bipartite graph with $|U|,|W|\geq N$ such that
the number of $(U,W,d)$-trees in $G$ is at most
$\rho|U|^{2^{d}-1}|W|^{2^{d}}$. Since $\rho<\delta^{C}$, Lemma 5.14 implies
there exist $m\leq M$, $U_{0}\subseteq U$ of size at most $\delta|U|$, a
partition $W_{0}\cup W_{1}\cup\ldots\cup W_{m}$ such that
$|W_{0}|\leq\epsilon|W|$, and such that for each $1\leq i\leq m$,
$|W_{i}|\geq|W|/M\geq N_{2}$ and $W_{i}$ is $\delta$-good with respect to all
$u\in U\setminus U_{0}$.

For each $1\leq i\leq m$ and $u\in U\setminus U_{0}$, let $\xi(u,W_{i})$ be
such that $|N^{\xi(u,W_{i})}(u)\cap W_{i}|\geq(1-\delta)|W_{i}|$. Partition
$U\setminus U_{0}$ into a minimal number of parts $U_{1}\cup\ldots\cup U_{t}$
so that if $u$ and $u^{\prime}$ are in the same part, then
$\xi(u,W_{j})=\xi(u^{\prime},W_{j})$ for all $j\in[m]$. Clearly $t\leq 2^{m}$.
Then define $I=\\{i\in[t]:|U_{i}|<\mu|U|/2^{t}\\}$, and set
$U_{0}^{\prime}=U_{0}\cup\bigcup_{i\in I}U_{i}$. Clearly $|U_{0}^{\prime}|\leq
2\delta|U|$. Let $U_{1}^{\prime},\ldots,U^{\prime}_{t^{\prime}}$ be a
reindexing of $\\{U_{i}:i\in[t]\setminus I\\}$. For each $i\in[t^{\prime}]$,
let $\xi(U^{\prime}_{i},W_{j})$ be such that
$\xi(u,W_{j})=\xi(U^{\prime}_{i},W_{j})$ for all $u\in U^{\prime}_{i}$.

Set $\mathbf{U}=\\{U^{\prime}_{1},\ldots,U^{\prime}_{t^{\prime}}\\}$ and
$\mathbf{W}=\\{W_{1},\ldots,W_{m}\\}$, and define the bipartite graph

$\mathbf{R}=(\mathbf{U}\cup\mathbf{W},\\{U^{\prime}_{i}W_{j}:\xi(U_{i}^{\prime},W_{j})=1\\}).$

Note that each $|W_{i}|\geq|W|/M\geq N/M\geq N_{2}$, and each
$|U_{i}^{\prime}|\geq\delta|U|/2^{t}\geq\delta N/2^{t}\geq N_{2}$. We claim
there are no $(\mathbf{U},\mathbf{W},d)$-trees in $\mathbf{R}$.

Suppose towards a contradiction there exists $(U_{\sigma})_{\sigma\in
2^{<d}}(W_{\lambda})_{\lambda\in 2^{d}}$ a $(\mathbf{U},\mathbf{W},d)$-tree in
$\mathbf{R}$. Then for each $\sigma\in 2^{<d}$ and $\lambda\in 2^{d}$, $|E\cap
K_{2}[U_{\sigma},W_{\lambda}]|/K_{2}[U_{\sigma},W_{\lambda}]|\in[0,\delta)\cup(1-\delta,1]$.
By Lemma 5.15, the number of $(U,W,d)$-trees $(u_{\sigma})\in
2^{<d}(w_{\lambda})_{\lambda\in 2^{d}}\in\prod_{\sigma\in
2^{<d}}U_{\sigma}\times\prod_{\lambda\in 2^{d}}W_{\lambda}$ is at least

$\frac{1}{2}\prod_{\sigma\in 2^{<d}}|U_{\sigma}|\prod_{\lambda\in
2^{d}}|W_{\lambda}|\geq\frac{1}{2}(\delta|U|/2^{t})^{2^{d}-1}(|W|/M)^{2^{d}}>\rho|U|^{2^{d}-1}|W|^{2^{d}},$

a contradiction. Thus there exist no $(\mathbf{U},\mathbf{W},d)$-trees in
$\mathbf{R}$. Define

$G^{\prime}=((U\setminus U_{0}^{\prime})\cup(W\setminus W_{0}),\cup
E^{\prime})\text{ where }E^{\prime}=\bigcup_{U_{i}W_{j}\in
E(\mathbf{R})}K_{2}[U_{i},W_{j}].$

We claim that $G^{\prime}$ contains no $(U\setminus U_{0}^{\prime},W\setminus
W_{0}^{\prime},d)$-trees. Suppose towards a contradiction there exists some
$(u_{\sigma})_{\sigma\in 2^{<d}}(w_{\lambda})_{\lambda\in 2^{d}}$ which is a
$(U\setminus U_{0}^{\prime},W\setminus W_{0}^{\prime},d)$-tree in
$G^{\prime}$. By the definition of $G^{\prime}$ and the fact that there are no
there are no $(\mathbf{U},\mathbf{W},d)$-trees in $\mathbf{R}$, we know there
must be some $\lambda_{1}\neq\lambda_{2}$ in $2^{d}$ and a
$W_{i}\in\mathbf{W}$ with $w_{\lambda_{1}},w_{\lambda_{2}}\in W_{i}$. Since
$\lambda_{1}\neq\lambda_{1}$, there is some $\tau\in 2^{<d}$ such that
$\tau\wedge 0\trianglelefteq\lambda_{1}$ and $\tau\wedge
1\trianglelefteq\lambda_{2}$, or vice versa. Without loss of generality,
assume $\tau\wedge 0\trianglelefteq\lambda_{1}$ and $\tau\wedge
1\trianglelefteq\lambda_{2}$. Thus there is $u_{\tau}\in U\setminus
U_{0}^{\prime}$ so that $u_{\tau}w_{\lambda_{1}}\in E$ and
$u_{\tau}w_{\lambda_{2}}\notin E$. But there is some
$U_{j}^{\prime}\in\mathbf{U}$ with $u_{\tau}\in U_{j}^{\prime}$. But by
definition, since $w_{\lambda_{1}},w_{\lambda_{2}}\in W_{i}$, we have that
$u_{\tau}w_{\lambda_{1}}$ and $u_{\tau}w_{\lambda_{2}}$ are both in
$E^{\delta(U_{j}^{\prime},W_{i})}$, a contradiction. This finishes our
verification that $G^{\prime}$ contains no $(U\setminus
U_{0}^{\prime},W\setminus W_{0}^{\prime},d)$-trees.

It is easy to see that for all $u\in U\setminus U_{0}^{\prime}$,

$|(N_{G^{\prime}}(u)\Delta N_{G}(u))\cap(W\setminus
W_{0}^{\prime}))|\leq\sum_{W_{j}\in\mathbf{W}}|(N_{G^{\prime}}(u)\Delta
N_{G}(u))\cap
W_{j}|\leq\sum_{W_{j}\in\mathbf{W}}\delta|W_{j}|\leq\delta|W\setminus
W_{0}^{\prime}|.$

Thus $G[U\setminus U_{0}^{\prime},W\setminus W_{0}]$ is uniformly $(U\setminus
U_{0}^{\prime},W\setminus W_{0},\delta)$-close to $G^{\prime}$. ∎

###  5.3. A property admits $\textnormal{disc}_{2,3}$-error if and only if it
is $\operatorname{NFOP}_{2}$

In this subsection we prove our main result about $\operatorname{NFOP}_{2}$
properties, which is that they are exactly the properties admitting linear
$\textnormal{disc}_{2,3}$-error. The harder direction is Theorem 1.56, which
implies that an $\operatorname{NFOP}_{2}$ property admits linear
$\textnormal{disc}_{2,3}$-error. The proof will apply Theorem 5.13 along with
a refinement of Theorem 4.15 to auxiliary graph structures like the ones
defined in Section 5.1 (see Definition 5.2).

Before we start the proof of Theorem 1.56, we prove two additional lemmas. The
first is a refinement of Theorem 4.15 which has additional equitability
requirements.

######  Theorem 5.16.

Suppose $d\geq 0$. For all $\epsilon>0$ and non-increasing functions
$f:\mathbb{N}\rightarrow(0,1]$ with $\lim_{n\rightarrow\infty}f(n)=0$, there
is $M\geq 1$ such that the following hold.

Suppose $G=(U\cup W,E)$ is a bipartite graph, and $W=W_{1}\cup\ldots\cup
W_{m}$ is a partition satisfying $|W_{1}|=\ldots=|W_{m}|$, and such that for
each $i\in[m]$, $G$ contains no $(U,W_{i},d)$-trees.

Then there are some $m^{\prime}\leq M$, $n^{\prime}\leq|W|$, and a set
$\Omega\subseteq[m]$, such that $|\bigcup_{u\in\Omega}W_{u}|\leq\epsilon|W|$,
and such that for all $u\in[m]\setminus\Omega$, there is a partition

$W_{u}=W_{u,0}\cup W_{u,1}\cup\ldots\cup W_{u,m^{\prime}},$

so that $|W_{u,0}|\leq\epsilon|W_{u}|$, and so that for each $1\leq i\leq
m^{\prime}$, $W_{u,i}$ is $f(m^{\prime})$-good in $G$ and
$|W_{i,u}|=n^{\prime}$.

The difference between the above and Theorem 4.15 is that we begin with an
equipartition, and end up refining each $W_{i}$ into the same number of parts,
all of which are of the same size.

Proof of Theorem 5.16: Fix $d\geq 0$, $\epsilon>0$, and a non-increasing
function $f:\mathbb{N}\rightarrow(0,1]$ with
$\lim_{n\rightarrow\infty}f(n)=0$. Define
$\psi(x)=\epsilon^{4}f(\epsilon^{-4}x)/x^{2}$. Let $M_{1}$ be as in Theorem
4.15 for $d$, $\epsilon^{8}$, and $\psi$. Then define
$M=\epsilon^{-2}(M_{1})^{2}$.

Suppose $G=(U\cup W,E)$ is a bipartite graph, and $W=W_{1}\cup\ldots\cup
W_{m}$ is a partition so that $|W_{1}|=\ldots=|W_{m}|$, and so that $G$
contains no $(U,W_{i},d)$-trees for each $i\in[m]$.

By Theorem 4.15, there is some $m_{1}\leq M_{1}$ and a set
$\Omega\subseteq[m]$, such that
$|\bigcup_{u\in\Omega}W_{u}|\leq\epsilon^{8}|W|$ and so that for each
$u\in[m]\setminus\Omega$, there are $s_{u}\leq m_{1}$ and a partition

$W_{u}=W_{u,0}\cup W_{u,1}\cup\ldots\cup W_{u,s_{u}},$

so that $|W_{u,0}|\leq\epsilon^{8}|W_{u}|$, and so that for each $1\leq i\leq
s_{u}$, $W_{u,i}$ is $\psi(m_{1})$-good. By reindexing if necessary, we may
assume that for each $u\in[m]\setminus\Omega$,
$|W_{u,1}|\geq\ldots\geq|W_{u,s_{u}}|$. Set
$K=\lceil\epsilon^{2}|W|/m_{1}\rceil$, and let
$\Omega^{\prime}=\Omega\cup\\{u\in[m]\setminus\Omega:|W_{u,1}|<K\\}$.

For each $u\in[m]\setminus\Omega^{\prime}$, let $p_{u}$ be maximal so that
$|W_{u,p_{u}}|\geq K$, and for each $1\leq v\leq p_{u}$, choose a partition

$W_{u,v}=W_{u,v,0}\cup W_{u,v,1}\cup\ldots\cup W_{u,v,s_{u,v}},$

with the property that $|W_{u,v,0}|<K$ and for each $1\leq w\leq s_{u,v}$,
$|W_{u,v,w}|=K$. Then set $q_{u}=\sum_{v\in[p_{u}]}s_{u,v}$, and fix an
enumeration

$\\{W_{u,v,w}:v\in[p_{u}],w\in[s_{u,v}]\\}=\\{X_{u,1},\ldots,X_{u,q_{u}}\\}\text{
so that }|X_{u,1}|\geq\ldots\geq|X_{u,q_{u}}|.$

Then observe that

$\displaystyle|W_{u}\setminus\Big{(}\bigcup_{v=1}^{q_{u}}X_{u,v}\Big{)}|\leq|W_{u,0}|+|\bigcup_{v=p_{u}+1}^{r_{u}}W_{u,v}|+K$
$\displaystyle\leq\epsilon^{2}|W_{u}|+\frac{\epsilon^{2}|W_{u}|r_{u}}{m_{1}}+\frac{\epsilon^{2}|W_{u}|}{m_{1}}\leq
4\epsilon^{2}|W_{u}|.$

Note that for all $u\in[m]\setminus\Omega^{\prime}$,
$|(\bigcup_{v=1}^{q_{u}}X_{u,v})|=q_{u}K\geq(1-4\epsilon^{2})|W_{u}|=(1-4\epsilon^{2})|W_{1}|$.
Therefore, setting $q=\min\\{q_{u}:u\in[m]\\}$, we know $|W_{1}|\geq
qK\geq(1-4\epsilon^{2})|W_{1}|$. For each $u\in[m]\setminus\Omega^{\prime}$,
define

$X_{u,0}=W_{u,0}\cup\Big{(}\bigcup_{v=p_{u}+1}^{r_{u}}W_{u,v}\Big{)}\cup\Big{(}\bigcup_{v=1}^{p_{u}}W_{u,v,0}\Big{)}\cup\Big{(}\bigcup_{q<q^{\prime}\leq
q_{u}}X_{u,v}\Big{)}.$

Then we note that

$\displaystyle|X_{u,0}|\leq\epsilon^{2}|W_{u}|+\frac{2(r_{u}-p_{u})\epsilon^{2}|W_{u}|}{m_{1}}+\frac{2p_{u}\epsilon^{4}|W_{u}|}{m_{1}}+(|W_{u}|-qK_{2})$
$\displaystyle\leq 5\epsilon^{2}|W_{u}|+4\epsilon^{2}|W_{1}|$
$\displaystyle=9\epsilon^{2}|W_{u}|$ $\displaystyle<\epsilon|W_{u}|,$

where the last inequality is because $\epsilon<1/4$. For all
$u\in[m]\setminus\Omega^{\prime}$, we now have a new partition of $W_{u}$,
namely

$W_{u}=X_{u,0}\cup X_{u,1}\cup\ldots\cup X_{u,q}.$

where $|X_{u,0}|\leq\epsilon|W_{u}|$ and for each $1\leq v\leq q$,
$|X_{u,v}|=K$. Further, note that since $qK\leq|W_{1}|$,
$q\leq\epsilon^{-4}m_{1}\leq M$.

We now show that for all $u\in[m]\setminus\Omega^{\prime}$ and
$q^{\prime}\in[q]$, $X_{u,q^{\prime}}$ is $f(q)$-good. Fix
$u\in[m]\setminus\Omega^{\prime}$ and $1\leq q^{\prime}\leq q$. By
construction, there is some $v\in[p_{u}]$ and $w\in[s_{u,v}]$ so that
$X_{u,q^{\prime}}=W_{u,v,w}$, where $W_{u,v,w}$ has size $K$, and is contained
in $W_{u,v}$, a set which is $\psi(m_{1})$-good. Thus for all $u\in U$ there
is some $\delta\in\\{0,1\\}$ so that $|N^{\delta}(u)\cap
W_{u,v}|\leq\psi(m_{1})|W_{u,v}|$. By definition of $\psi$ and $K$, we have
that

$\displaystyle|N^{\delta}(u)\cap
W_{u,v,w}|\leq\psi(m_{1})|W_{u,v}|\leq\frac{\psi(m_{1})|W_{u}|}{K}|W_{u,v,w}|$
$\displaystyle\leq\psi(m_{1})\epsilon^{-4}m_{1}|W_{u,v,w}|$ $\displaystyle\leq
f(q)|W_{u,v,w}|.$

This shows $X_{u,q^{\prime}}$ is $f(q)$-good, which finishes the proof. ∎

Our second lemma, Lemma 5.17 below, allow us to ensure certain divisibility
requirements hold in regular decompositions.

######  Lemma 5.17.

For all $\epsilon_{1}>0$, $\epsilon_{2}:\mathbb{N}\rightarrow(0,1]$, and
$k\geq 1$, there are $\mu_{1}>0$ and $\mu_{2}:\mathbb{N}\rightarrow(0,1]$,
such that for all $L,T\geq 1$, there is $N\geq 1$ such that the following
holds.

Suppose $H=(V,E)$ is a $3$-graph and $|V|=n\geq N$. Suppose $1\leq t\leq T$,
$1\leq\ell\leq L$, and $\mathcal{P}$ is an $(\mu_{1},\mu_{2}(\ell),t,\ell)$
decomposition of $V$ which is $(\mu_{1},\mu_{2}(\ell),t,\ell)$-regular and
$\mu_{1}$-homogeneous with respect to $H$. Then there exists
$\mathcal{P}^{\prime}$ is an
$(\epsilon_{1},\epsilon_{2}(\ell^{\prime}),t,\ell^{\prime})$, decomposition of
$V$, such that $\ell^{\prime}=k\ell$, and so that $\mathcal{P}^{\prime}$ is
$(\epsilon_{1},\epsilon_{2}(\ell^{\prime}),t,\ell^{\prime})$-regular and
$\epsilon_{1}$-homogeneous with respect to $H$.

###### Proof.

Choose $\mu^{\prime}_{1},\mu^{\prime}_{2}$ as in Lemma 2.28 for $\epsilon_{1}$
and $\epsilon_{2}$. Define $\mu_{2}:\mathbb{N}\rightarrow(0,1]$ by choosing
$\mu_{2}(x)\ll_{k}\mu_{2}^{\prime}(x)$ for all $x$. Given $T,L\geq 1$, choose
$N\gg N_{1},T,L,\epsilon_{2}(L)^{-1}$.

Now suppose $H=(V,E)$ is a $3$-graph with $|V|\geq N$. Suppose $1\leq t\leq
T$, $1\leq\ell\leq L$, and $\mathcal{P}$ is an
$(\mu^{\prime}_{1},\mu_{2}(\ell),t,\ell)$ decomposition of $V$ which is
$(\mu^{\prime}_{1},\mu_{2}(\ell),t,\ell)$-regular and
$\mu^{\prime}_{1}$-homogeneous with respect to $H$. For each
$P_{ij}^{\alpha}\in\mathcal{P}_{edge}$ satisfying
$\textnormal{disc}_{2}(\mu_{2}(\ell),1/\ell)$, apply Lemma 2.24 with
$\epsilon=\delta=\mu_{2}(\ell)$ to obtain a partition
$P_{ij}^{\alpha}=P_{ij}^{\alpha,1}\cup\ldots\cup P_{ij}^{\alpha,\ell k}$, so
that each $P_{ij}^{\alpha,u}$ satisfies $\textnormal{disc}_{2}(\mu_{2}(\ell))$
and has density $(1\pm 2\mu_{2}(\ell))\frac{1}{k\ell}$. By our choice of
$\mu_{2}$, each such $P_{ij}^{\alpha,\beta}$ satisfies
$\textnormal{disc}_{2}(\mu_{2}^{\prime}(k\ell),1/k\ell)$. Let
$\mathcal{P}^{\prime}$ have $\mathcal{P}^{\prime}_{vert}=\mathcal{P}_{vert}$
and

$\mathcal{P}^{\prime}_{edge}=\\{P_{ij}^{\alpha,\beta}:P_{ij}^{\alpha}\text{
satisfies }\textnormal{disc}_{2}(\mu_{2}(\ell),1/\ell),1\leq\beta\leq
k\\}\cup\\{P_{ij}^{\alpha}:P_{ij}^{\alpha}\text{ fails
}\textnormal{disc}_{2}(\mu_{2}(\ell),1/\ell)\\}.$

Then $\mathcal{P}^{\prime}$ is a
$(\mu^{\prime}_{1},\mu^{\prime}_{2}(\ell^{\prime}),t,\ell^{\prime})$,
decomposition of $V$, where $t^{\prime}=t$ and $\ell^{\prime}=\ell k$. It is
straightforward to see that $\mathcal{P}^{\prime}$ is a $(0,0)$-approximate
refinement of $\mathcal{P}$ (see Definition 2.26). By Lemma 2.28,
$\mathcal{P}^{\prime}$ is a
$(t,\ell^{\prime},\epsilon_{1},\epsilon_{2}(\ell^{\prime}))$-decomposition of
$V$ which is $(\epsilon_{1},\epsilon_{2}(\ell^{\prime}))$-regular and
$\epsilon_{1}$-homogeneous with respect to $H$. ∎

We are now ready to prove Theorem 1.56.

Proof of Theorem 1.56: Fix $k\geq 1$, $\epsilon_{1}>0$,
$\epsilon_{2}:\mathbb{N}\rightarrow(0,1]$, and $\ell_{0},t_{0}\geq 1$. Choose
$0<\epsilon\ll\epsilon_{1}$, and let $d=d(k)$ as in part (2) in Theorem 4.12.

Choose $\epsilon^{*}_{1}>0$ and $\epsilon^{*}_{2}:\mathbb{N}\rightarrow(0,1]$
as in Proposition 5.7 for $k$ and $\epsilon$. Define a function
$\psi:\mathbb{N}\rightarrow(0,1]$ by setting $\psi(x)=\epsilon^{100}/x^{3}$
for each $x\geq 1$. Then let $M_{1}=M_{1}(d,\epsilon^{100},f)$ and
$N_{1}=N_{1}(d,\epsilon^{100},f)$ be as in Theorem 5.16, where
$f:\mathbb{N}\rightarrow(0,1]$ is defined by
$f(x)=\epsilon^{100}\psi(2\epsilon^{-100}x(x+1))/(3x(x+1))$. Let
$M\gg\epsilon^{-100}M_{1}$, and choose $\epsilon_{0}\ll\epsilon/(M!)^{3}$. Let
$\delta_{0}=\delta_{0}(d,\epsilon_{0})$ and $N_{2}=N_{2}(d,\epsilon_{0})$ be
as in Theorem 5.13. Then choose

$\epsilon_{1}^{\prime}\ll\delta\ll
f((M!)^{3})/(M!)^{3},\epsilon_{1}^{*},\epsilon_{1},\delta_{0},\epsilon^{5},d^{-1}.$

Define $\epsilon^{\prime}_{2}:\mathbb{N}\rightarrow(0,1]$ by choosing
$\epsilon^{\prime}_{2}(x)\ll\epsilon_{1}^{\prime}\epsilon_{2}(x)/xM!$. Set
$t_{0}^{\prime}=t_{0}$ and $\ell_{0}^{\prime}=\ell_{0}N_{3}\delta^{-1}$.

Now choose
$\epsilon_{1}^{\prime\prime}=\epsilon_{1}^{\prime\prime}(\epsilon_{1}^{\prime},\epsilon_{2}^{\prime})$
and
$\epsilon_{2}^{\prime\prime}=\epsilon_{2}^{\prime\prime}(\epsilon_{1}^{\prime},\epsilon_{2}^{\prime})$
as in Lemma 2.25. Let
$\mu_{1}\ll\epsilon_{1}^{\prime\prime\prime}\ll\epsilon_{1}^{\prime\prime}$,
and define
$\mu_{2},\epsilon^{\prime\prime\prime}_{2}:\mathbb{N}\rightarrow(0,1]$ by
choosing
$\mu_{2}(x)\ll\epsilon_{2}^{\prime\prime\prime}(x)\ll\epsilon_{2}^{\prime\prime}(x)$
for all $x$. Then choose $\mu^{\prime}_{1}$ and $\mu^{\prime}_{2}$ be as in
Lemma 5.17 for $\mu_{1},\mu_{2}$ and $(M!)^{3}$. Finally, choose $T$, $L$, and
$N_{3}$ as in Theorem 1.30 for $t_{0}^{\prime}$, $\ell_{0}^{\prime}$,
$\mu^{\prime}_{1}$ and $\mu^{\prime}_{2}$, and let $N\gg
N_{1}N_{2}N_{3},T,M!,(\mu^{\prime}_{1})^{-1},(\mu^{\prime}_{2}(M!L))^{-1},\delta^{-1}$.

Suppose $H=(V,E)$ is a $3$-graph with $|V|\geq N$ which does not have
$k$-$\operatorname{FOP}_{2}$. Since $H$ has $\textnormal{VC}_{2}$-dimension
less than $k$ (see Fact 1.29), Theorem 1.30 implies there exist
$\ell^{\prime}_{0}\leq\ell_{1}\leq L$, $t_{0}^{\prime}\leq t\leq T$, and
$\mathcal{P}_{1}$ a
$(t,\ell_{1},\mu^{\prime}_{1},\mu^{\prime}_{2}(\ell_{1}))$-decomposition of
$V$ which is $(\mu^{\prime}_{1},\mu^{\prime}_{2}(\ell_{1}))$-regular and
$\mu^{\prime}_{1}$-homogeneous with respect to $H$. By Lemma 5.17, there is
$\mathcal{P}_{2}$ a $(t,\ell,\mu_{1},\mu_{2}(\ell))$-decomposition of $V$,
where $\ell=(M!)^{3}\ell_{1}$, and so that $\mathcal{P}_{2}$ is
$(\mu_{1},\mu_{2}(\ell))$-regular and $\mu_{1}$-homogeneous with respect to
$H$. By Lemma 2.25, there is $\mathcal{P}$ a
$(t,\ell,\epsilon_{1}^{\prime\prime\prime},\epsilon_{2}^{\prime\prime\prime}(\ell))$-decomposition
of $V$, so that $\mathcal{P}$ is
$(\epsilon^{\prime\prime\prime}_{1},\epsilon^{\prime\prime\prime}_{2}(\ell))$-regular
and $\epsilon_{1}^{\prime\prime\prime}$-homogeneous with respect to $H$, and
so that $\mathcal{P}$ has no $\textnormal{disc}_{2}$-irregular triads. Say
$\mathcal{P}_{vert}=\\{V_{1},\ldots,V_{t}\\}$ and
$\mathcal{P}_{edge}=\\{P_{ij}^{\alpha}:ij\in{[t]\choose
2},\alpha\in[\ell]\\}$.

Given $ijs\in{[t]\choose 3}$ and $1\leq\alpha,\beta,\gamma\leq\ell$, set
$G_{ijs}^{\alpha,\beta,\gamma}=(V_{i}\cup V_{j}\cup V_{s},P_{ij}^{\alpha}\cup
P_{js}^{\beta}\cup P_{is}^{\gamma})$,
$H_{ijs}^{\alpha,\beta,\gamma}=(V_{i}\cup V_{j}\cup V_{s},E\cap
K_{3}^{(2)}(G_{ijs}^{\alpha,\beta,\gamma}))$ and let
$d_{ijs}^{\alpha,\beta,\gamma}$ be such that $|E\cap
K_{3}^{(2)}(G_{ijs}^{\alpha,\beta,\gamma})|=d_{ijs}^{\alpha,\beta,\gamma}|K_{3}^{(2)}(G_{ijs}^{\alpha,\beta,\gamma})|$.
We will use throughout that since
$\epsilon_{2}^{\prime\prime}(x)\ll\epsilon_{2}^{\prime\prime\prime}(x)$,
Corollary 2.6 implies that for all $ijs\in{[t]\choose 3}$ and
$\alpha,\beta,\gamma\in[\ell]$,

(5)
$\displaystyle|K_{3}^{(2)}(G_{ijs}^{\alpha,\beta,\gamma})|=(1\pm\epsilon^{\prime\prime}_{2}(\ell))(n/\ell
t)^{3}.$

We will use $\mathcal{P}$ to construct a different decomposition, of $V$,
which will be called $\mathcal{Q}$, and which will have the same vertex
partition as $\mathcal{P}$, but different edge partitions.

We begin defining several sets which will help us control the location of the
error triads of $\mathcal{P}$. First, set

$\displaystyle\Gamma_{err}$
$\displaystyle=\\{G_{ijs}^{\alpha,\beta,\gamma}\in\operatorname{Triads}(\mathcal{P}):(H_{ijs}^{\alpha,\beta,\gamma},G_{ijs}^{\alpha,\beta,\gamma})\text{
fails
}\textnormal{disc}_{2,3}(\epsilon_{1}^{\prime\prime},\epsilon^{\prime\prime}_{2}(\ell))\\}$
$\displaystyle\mathbf{E}_{1}$
$\displaystyle=\\{G_{ijs}^{\alpha,\beta,\gamma}\in\operatorname{Triads}(\mathcal{P})\setminus\Gamma_{err}:d_{ijs}^{\alpha,\beta,\gamma}\geq
1-\epsilon_{1}^{\prime\prime}\\},\text{ and }$ $\displaystyle\mathbf{E}_{0}$
$\displaystyle=\\{G_{ijs}^{\alpha,\beta,\gamma}\in\operatorname{Triads}(\mathcal{P})\setminus\Gamma_{err}:d_{ijs}^{\alpha,\beta,\gamma}\leq\epsilon_{1}^{\prime\prime}\\}.$

By assumption,
$\operatorname{Triads}(\mathcal{P})=\Gamma_{err}\sqcup\mathbf{E}_{1}\sqcup\mathbf{E}_{0}$,
and at most $\epsilon_{1}^{\prime\prime\prime}n^{3}$ triples $xyz\in{V\choose
3}$ are in an element of $\Gamma_{err}$. By (5), this implies
$|\Gamma_{err}|\leq\epsilon^{\prime\prime\prime}_{1}n^{3}/((n^{3}/t^{3}\ell^{3})(1-\epsilon_{2}^{\prime\prime}(\ell))\leq\epsilon_{1}^{\prime}t^{3}\ell^{3}$.
We now define the set of triples from $\mathcal{P}_{vert}$ which have non-
trivial intersection with $\Gamma_{err}$.

$\displaystyle\Sigma_{0}$ $\displaystyle=\\{V_{i}V_{j}V_{s}:ijs\in{[t]\choose
3}\text{ and
}|\\{(\alpha,\beta,\gamma)\in[\ell]^{3}:G_{ijk}^{\alpha,\beta,\gamma}\in\Gamma_{err}\\}|\geq
2(\epsilon_{1}^{\prime})^{1/2}\ell^{3}\\}.$

From (5), we have that $|\Sigma_{0}|\leq(\epsilon_{1}^{\prime})^{1/2}t^{3}$.
We next define the set of pairs $V_{i}V_{j}$ contained in a non-trivial number
of triples from $\Sigma_{0}$.

$\displaystyle\Psi$
$\displaystyle=\\{V_{i}V_{j}:|\\{s\in[t]:V_{i}V_{j}V_{s}\in\Sigma_{0}\\}|\geq(\epsilon_{1}^{\prime})^{1/4}t\\}.$

Since $|\Sigma_{0}|\leq 2(\epsilon_{1}^{\prime})^{1/2}t^{3}$, we have that
$|\Psi|\leq(\epsilon_{1}^{\prime})^{1/4}t^{2}$. We now define, for each
$V_{i}V_{j}\notin\Psi$, an auxiliary graph $H_{ij}=(U_{ij}\cup
W_{ij},E_{ij})$, where

$\displaystyle W_{ij}$
$\displaystyle=\\{P_{ij}^{\alpha}:\alpha\leq\ell\\}\text{ and
}U_{ij}=\\{P_{is}^{\beta}P_{js}^{\gamma}:s\in[t]\setminus\\{i,j\\},\alpha,\beta\in[\ell]\\},\text{
and }$ $\displaystyle E_{ij}$
$\displaystyle=\\{(P_{ij}^{\alpha},P_{is}^{\beta}P_{js}^{\gamma}):G_{ijk}^{\alpha,\beta,\gamma}\in\mathbf{E}_{1}\text{
and }V_{i}V_{j}V_{s}\notin\Sigma_{0}\\}.$

Note $H_{ij}$ is bipartite with parts $U_{ij},W_{ij}$ where $|W_{ij}|=\ell$
and $|U_{ij}|=(t-2)\ell^{2}$. Our next step is to prove Claim 5.18 below,
which shows that for all $V_{i}V_{j}\notin\Psi$, there is a large subset
$U^{*}_{ij}\cup W_{ij}^{*}$ of $V(H_{ij})$, on which $H_{ij}$ is uniformly
$\delta$-closet to some $H_{ij}^{*}$ which contains no $d$-trees with leaves
in $W^{*}_{ij}$. The idea behind the proof is as follows. First, by
Proposition 5.7, we know there are no encodings of $H(k)$ in
$(H,\mathcal{P})$. Using Theorem 4.12, we will show that this implies that any
$(U_{ij},W_{ij},d)$-tree in $H_{ij}$ must involve some triad
$G_{ijs}^{\alpha,\beta,\gamma}\in\Gamma_{err}$ where
$V_{i}V_{j}V_{s}\notin\Sigma_{0}$. If $V_{i}V_{j}\notin\Psi$, then there are
few such triads, so there will be few such $(U_{ij},W_{ij},d)$-trees in
$H_{ij}$. We then apply Theorem 5.16 to obtain the desired $H_{ij}^{*}$.

######  Claim 5.18.

Suppose $V_{i}V_{j}\notin\Psi$. Then there are $U_{ij}^{bad}\subseteq U_{ij}$
and $W_{ij}^{bad}\subseteq W_{ij}$ such that the following hold, where
$U_{ij}^{*}=U_{ij}\setminus U_{ij}^{bad}$ and $W_{ij}^{*}=W_{ij}\setminus
W_{ij}^{bad}$.

  * •

$|W_{ij}^{bad}|\leq\epsilon_{0}|W_{ij}|$ and
$|U^{bad}_{ij}|\leq\delta|U_{ij}|$,

  * •

$H_{ij}[U_{ij}^{*},W^{*}_{ij}]$ is uniformly
$(U_{ij}^{*},W_{ij}^{*},\delta)$-close to a bipartite graph
$H_{ij}^{*}=(U_{ij}^{*}\cup W_{ij}^{*},E_{ij}^{*})$ containing no
$(U_{ij}^{*},W^{*}_{ij},d)$-trees.

Proof of Claim 5.18: Fix $V_{i}V_{j}\notin\Psi$. We first show there are at
most $(\epsilon_{1}^{\prime})^{1/4}|U_{ij}|^{2^{<d}}|W_{ij}|^{2^{d}}$ many
$(W_{ij},U_{ij},d)$-trees in $H_{ij}$. Define
$\Omega_{ij}=\\{G_{ijs}^{\alpha,\beta,\gamma}\in\Gamma_{err}:V_{i}V_{j}V_{s}\notin\Sigma_{0}\\}$.
Note that if $V_{s}$ satisfies $V_{i}V_{j}V_{s}\notin\Sigma_{0}$, then by
definition of $\Sigma_{0}$,
$|\\{(\alpha,\beta,\gamma)\in[\ell]^{3}:G_{ijs}^{\alpha,\beta,\gamma}\in\Gamma_{err}\\}|\leq
2(\epsilon_{1}^{\prime})^{1/2}\ell^{3}$. Therefore, since
$V_{i}V_{j}\notin\Psi$,

$\displaystyle|\Omega_{ij}|$
$\displaystyle\leq(\epsilon_{1}^{\prime})^{1/4}t\ell^{3}+2(\epsilon_{1}^{\prime})^{1/2}t\ell^{3}\leq
3(\epsilon_{1}^{\prime})^{1/4}t\ell^{3}.$

We now make some observations about any $(U_{ij},W_{ij},d)$-tree in $H_{ij}$.
Suppose

$(P_{is_{\sigma}}^{\alpha_{\sigma}}P_{js_{\sigma}}^{\beta_{\sigma}})_{\sigma\in
2^{<d}}(P_{ij}^{\gamma_{\rho}})_{\rho\in 2^{d}}$

is a $(U_{ij},W_{ij},d)$-tree in $H_{ij}$. Note that for all $\sigma\in
2^{<d}$, there is $\rho\in 2^{d}$ so that $\sigma\wedge 1\trianglelefteq\rho$,
and for this $\rho$,
$P_{is_{\sigma}}^{\alpha_{\sigma}}P_{js_{\sigma}}^{\beta_{\sigma}}P_{ij}^{\gamma_{\rho}}\in
E_{ij}$. By definition of $E_{ij}$, this implies
$V_{i}V_{j}V_{s_{\sigma}}\notin\Sigma_{0}$. Thus for all $\sigma\in 2^{<d}$,
$V_{i}V_{j}V_{s_{\sigma}}\notin\Sigma_{0}$.

By part (1) of Theorem 4.12, there are $\\{P_{ij}^{\gamma^{\prime}_{u}}:u\leq
k\\}\subseteq\\{P_{ij}^{\gamma_{\rho}}:\rho\in 2^{d+1}\\}$ and
$\\{P_{is^{\prime}_{u}}^{\alpha^{\prime}_{u}}P_{js_{u}^{\prime}}^{\beta_{u}^{\prime}}\\}\subseteq\\{P_{is_{\sigma}}^{\alpha_{\sigma}}P_{js_{\sigma}}^{\beta_{\sigma}}:\sigma\in
2^{<d}\\}$ so that
$P_{is^{\prime}_{u}}^{\alpha^{\prime}_{u}}P_{js_{u}^{\prime}}^{\beta_{u}^{\prime}}P_{ij}^{\gamma^{\prime}_{v}}\in
E_{ij}$ if and only if $u\leq v$. Translating, this means that for all $u\leq
v$,
$G_{ijs_{u}^{\prime}}^{\alpha_{u}^{\prime}\beta_{u}^{\prime}\gamma_{v}^{\prime}}\in\mathbf{E}_{1}$
and for all $v<u$,
$G_{ijs_{u}^{\prime}}^{\alpha_{u}^{\prime}\beta_{u}^{\prime}\gamma_{v}^{\prime}}\notin\mathbf{E}_{1}$
(i.e.
$G_{ijs_{u}^{\prime}}^{\alpha_{u}^{\prime}\beta_{u}^{\prime}\gamma_{v}^{\prime}}\in\Gamma_{err}\cup\mathbf{E}_{0}$).
By above, for all $u\in[k]$, $V_{i}V_{j}V_{s_{u}^{\prime}}\notin\Sigma_{0}$,
so for all $v<u$, we have that
$G_{ijs_{u}^{\prime}}^{\alpha_{u}^{\prime}\beta_{u}^{\prime}\gamma_{v}^{\prime}}\in\Omega_{ij}\cup\mathbf{E}_{0}$.
If it were true that
$G_{ijs_{u}^{\prime}}^{\alpha_{u}^{\prime}\beta_{u}^{\prime}\gamma_{v}^{\prime}}\in\mathbf{E}_{0}$
for all $v<u$, then we would have an encoding of $H(k)$ in $(H,\mathcal{P})$
via $f:a_{u}\mapsto P_{ij}^{\gamma^{\prime}_{u}}$ and $g:b_{v}\mapsto
P_{is^{\prime}_{v}}^{\alpha^{\prime}_{v}}P_{js^{\prime}_{v}}^{\beta^{\prime}_{v}}$.
By Proposition 5.7, this would imply $H$ has $k$-$\operatorname{FOP}_{2}$, a
contradiction. Thus there is some $v<u$ so that
$G_{ijs_{u}^{\prime}}^{\alpha_{u}^{\prime}\beta_{u}^{\prime}\gamma_{v}^{\prime}}\in\Omega_{ij}$.

The argument above shows that for every $(U_{ij},W_{ij},d)$-tree
$(P_{is_{\sigma}}^{\alpha_{\sigma}}P_{js_{\sigma}}^{\beta_{\sigma}})_{\sigma\in
2^{<d}}(P_{ij}^{\gamma_{\rho}})_{\rho\in 2^{d}}$ in $H_{ij}$, there is some
$\sigma\in 2^{<d}$ and $\rho\in 2^{d}$ such that
$P_{ijs_{\sigma}}^{\alpha_{\sigma},\beta_{\sigma},\gamma_{\rho}}\in\Omega_{ij}$.
Thus, any $(U_{ij},W_{ij},d)$-tree in $H_{ij}$ will be constructed in the
following process.

  1. (1)

Choose some $\sigma\in 2^{<d}$ and $\rho\in 2^{d}$. There are $(2^{d}-1)2^{d}$
choices.

  2. (2)

Choose an element $G_{ijs}^{\alpha,\beta,\gamma}\in\Omega_{ij}$, and set
$P_{is_{\sigma}}^{\alpha_{\sigma}}P_{js_{\sigma}}^{\beta_{\sigma}}=P_{is}^{\alpha}P_{js}^{\beta}$
and $P_{ij}^{\gamma_{\rho}}=P_{ij}^{\gamma}$. There are at most
$|\Omega_{ij}|\leq 2(\epsilon_{1}^{\prime})^{1/2}t\ell^{3}$ ways to do this.

  3. (3)

For all $\sigma^{\prime}\in 2^{<d}\setminus\\{\sigma\\}$ and $\rho^{\prime}\in
2^{d}\setminus\\{\rho\\}$, choose any
$P_{is_{\sigma^{\prime}}}^{\alpha_{\sigma^{\prime}}}P_{js_{\sigma^{\prime}}}^{\beta_{\sigma^{\prime}}}\in
U_{ij}$ and any $P_{ij}^{\gamma_{\rho^{\prime}}}\in W_{ij}$. Then number of
choices is at most

$|U_{ij}|^{2^{d}-2}|W_{ij}|^{2^{d}-1}=((t-2)\ell^{2})^{2^{d}-2}\ell^{2^{d}-1}.$

This yields that the number of $(U_{ij},W_{ij},d)$-trees in $H_{ij}$ is at
most

$(2^{d}-1)2^{d}2(\epsilon_{1}^{\prime})^{1/2}t\ell^{3}((t-2)\ell^{2})^{2^{d}-2}\ell^{2^{d}-1}<(\epsilon_{1}^{\prime})^{1/4}|U_{ij}|^{2^{d}-1}|W_{ij}|^{2^{d}},$

where the inequality is due to our choice of $\epsilon_{1}^{\prime}$. Now,
since $\epsilon_{1}^{\prime}\ll\delta\ll\delta_{0}$, Theorem 5.13 implies that
there is some $W_{ij}^{bad}\subseteq W_{ij}$ of size at most
$\epsilon_{0}|W_{ij}|$, and $U_{ij}^{bad}\subseteq U_{ij}$ of size at most
$\delta|U_{ij}|$ such that, setting $U^{*}_{ij}=U_{ij}\setminus U_{ij}^{bad}$
and $W_{ij}^{*}=W_{ij}\setminus W_{ij}^{bad}$, $H_{ij}[U^{*}_{ij},W^{*}_{ij}]$
is uniformly $(U_{ij}^{*},W_{ij}^{*},\delta)$-close to a bipartite graph
$H_{ij}^{*}=(U_{ij}^{*}\cup W^{*},E_{ij}^{*})$ containing no
$(U_{ij}^{*},W_{ij}^{*},d)$-trees. This finishes the proof of Claim 5.18. ∎

Our next goal is to apply Theorem 5.16. Set
$X=\min\\{|W_{ij}^{*}|:V_{i}V_{j}\notin\Psi\\}$. By Claim 5.18,
$X\geq(1-\epsilon_{0})\ell$. For each $V_{i}V_{j}\notin\Psi$, let
$W_{ij}^{**}$ be any $X$-element subset of $W_{ij}^{*}$. Note that
$H_{ij}^{*}[U^{*}_{ij},W_{ij}^{**}]$ contains no
$(U^{*}_{ij},W_{ij}^{**},d)$-trees. Set
$W=\bigcup_{V_{i}V_{j}\notin\Psi}W_{ij}^{**}$ and
$U=\bigcup_{V_{i}V_{j}\in\Psi}U^{*}_{ij}$, and define

$G^{*}=(U\cup W,\bigcup_{V_{i}V_{j}\notin\Psi}E(H_{ij}^{*}[U\cup W]).$

Note $G^{*}$ comes equipped with an equipartition
$\mathcal{S}=\\{W_{ij}^{**}:V_{i}V_{j}\notin\Psi\\}$ of $W$ such that for all
$W_{ij}^{**}\in\mathcal{S}$, $G^{*}$ contains no $(U,W_{ij}^{**},d)$-trees.
Consequently, by Theorem 4.15, there are $1\leq m_{1}\leq M$, $L_{1}\leq X$,
and a set $\Omega\subseteq\mathcal{S}$ such that
$|\bigcup_{W_{ij}^{**}\in\Omega}W^{**}_{ij}|\leq\epsilon^{100}|W|$, and for
all $W^{**}_{ij}\in\mathcal{S}\setminus\Omega$, there is a partition

$W_{ij}^{**}=B_{ij}^{0}\cup B_{ij}^{1}\cup\ldots\cup B_{ij}^{m_{1}},$

so that $|B_{ij}^{0}|\leq\epsilon^{100}|W_{ij}^{**}|$, and for each
$u\in[m_{1}]$, $|B_{ij}^{u}|=L_{1}$ and $B_{ij}^{u}$ is $f(m_{1})$-good in
$G^{*}$. Set

$\Psi^{\prime}:=\Psi\cup\\{V_{i}V_{j}\in{\mathcal{P}_{vert}\choose
2}\setminus\Psi:W_{ij}^{**}\in\Omega\\}.$

Note
$|\Psi^{\prime}|\leq(\epsilon_{1}^{\prime})^{1/4}t^{2}+\epsilon^{100}t^{2}\leq
2\epsilon^{100}t^{2}$. Set $m=\lceil\epsilon^{-100}m_{1}(m_{1}+1)\rceil$. By
construction, $(1-\epsilon_{0})\frac{\ell}{m_{1}}\leq
L_{1}\leq\frac{\ell}{m_{1}}$, so since $m_{1}\leq M$, our choice of
$\epsilon_{0}$ implies $L_{1}>\frac{\ell}{m}$. Let $r$ be such that
$L_{1}=rm+c$ for some $c<m$. Then for all $V_{i}V_{j}\notin\Psi^{\prime}$, and
each $u\in[m_{1}]$, we can choose a partition $B_{ij}^{u}=B_{ij}^{u,0}\cup
B_{ij}^{u,1}\cup\ldots\cup B_{ij}^{u,r}$ so that
$|B_{ij}^{u,0}|=c<\frac{\ell}{m}$ and for all $1\leq v\leq r$,
$|B_{ij}^{u,v}|=\frac{\ell}{m}$ (recall that $\ell$ is divisible by
$(M!)^{3}$, so we know that $\ell/m\in\mathbb{N}$). Define

$R_{ij}^{0}=B_{ij}^{0}\cup\bigcup_{v=1}^{m_{1}}B_{ij}^{u,0}.$

Note
$|R_{ij}^{0}|\leq\epsilon^{100}\ell+\frac{m_{1}\ell}{m}<2\epsilon^{100}\ell\leq\epsilon^{75}\ell$.
We claim that for all $W_{ij}^{**}\in\mathcal{S}\setminus\Omega$ and all
$u\in[m_{1}]$, and $1\leq v\leq r$, $B_{ij}^{u,v}$ is $\psi(m)$-good in
$H_{ij}$ with respect to every $u\in U^{*}_{ij}$. Fix
$W_{ij}^{**}\in\mathcal{S}\setminus\Omega$, $u\in[m_{1}]$, $1\leq v\leq r$,
and $u\in U_{ij}^{*}$. We know that $B_{ij}^{u}$ is $f(m_{1})$-good in
$G^{*}$, so there is some $\tau\in\\{0,1\\}$ so that

$|N^{\tau}_{G^{*}}(u)\cap B_{ij}^{u}|=|N^{\tau}_{H_{ij}^{*}}(u)\cap
B_{ij}^{u}|\leq f(m_{1})|B_{ij}^{u}|.$

Then since $H_{ij}^{*}$ is uniformly $\delta$-close to
$H_{ij}[U_{ij}^{*},W_{ij}^{*}]$,

$\displaystyle|N^{\tau}_{H_{ij}}(u)\cap B_{ij}^{u,v}|\leq
f(m_{1})|B_{ij}^{u}|+\delta|W_{ij}^{*}|$
$\displaystyle=|B_{ij}^{u,v}|\Big{(}\frac{f(m_{1})|B_{ij}^{u}|}{|B_{ij}^{u,v}|}+\frac{\delta|W_{ij}^{*}|}{|B_{ij}^{u,v}|}\Big{)}$
$\displaystyle\leq|B_{ij}^{u,v}|(f(m)m+\delta m)$
$\displaystyle\leq|B_{ij}^{u,v}|(f(m_{1})+\delta)(2\epsilon^{-100}m_{1}(m_{1}+1))$
$\displaystyle\leq\psi(m)|B_{ij}^{u,v}|,$

where the second inequality is by definition of $m$, since
$|B_{ij}^{u}|=L_{1}$, and since $|B_{ij}^{u,v}|=\ell/m$, and the last
inequality is by definition of $f$, since $m\leq 2\epsilon^{-100}$, and our
choice of $\delta$. We point out to the reader that it is this step (namely
deducing goodness of the $B_{ij}^{u,v}$ in $H_{ij}$ from the goodness of
$W_{ij}^{*}$ in $H_{ij}^{*}$) where it is important to have the degree of
goodness in Theorem 5.16 be small as a function of the number of parts. Now,
give a reindexing

$\\{R_{ij}^{1},\ldots,R_{ij}^{m_{2}}\\}=\\{B_{ij}^{u,v}:u\in[m_{1}],v\in[r]\\},$

where $m_{2}=m_{1}r$. Note $m_{1}r\leq\epsilon^{-100}m_{1}(m_{1}+1)<(M!)^{3}$,
so $\ell$ is divisible by $m_{2}$.

We have now defined, for all $V_{i}V_{j}\notin\Psi^{\prime}$, a partition

$W_{ij}=W_{ij}^{bad}\cup R_{ij}^{0}\cup R_{ij}^{1}\cup\ldots\cup
R_{ij}^{m_{2}}.$

This naturally translates into a new partition of $K_{2}[V_{i},V_{j}]$. In
particular, for each $1\leq u\leq m_{2}$, we let

$\mathbf{R}_{ij}^{u}=\\{xy\in K_{2}[V_{i},V_{j}]:xy\in P_{ij}^{\alpha}\text{
for some }P_{ij}^{\alpha}\in R_{ij}^{u}\\}.$

Setting
$\mathbf{R}_{ij}^{0}=K_{2}[V_{i},V_{j}]\setminus\bigcup_{u=1}^{m_{2}}\mathbf{R}_{ij}^{u}$,
we have a partition
$K_{2}[V_{i},V_{j}]=\mathbf{R}_{ij}^{0}\cup\mathbf{R}_{ij}^{1}\cup\ldots\cup\mathbf{R}_{ij}^{m_{2}}$.
By construction, for each $u\in[m_{2}]$, $\mathbf{R}_{ij}^{u}$ is a union of
$\ell/m$ many $P_{ij}^{\alpha}\in\mathcal{P}_{edge}$, so by Fact 2.23,
$\mathbf{R}_{ij}^{u}$ has
$\textnormal{disc}_{2}((\ell/m)\epsilon_{2}^{\prime\prime\prime}(\ell),(1/\ell)(\ell/m))$.
By our choice of $\epsilon_{2}^{\prime\prime\prime}(\ell)$, we can conclude
$\mathbf{R}_{ij}^{u}$ has
$\textnormal{disc}_{2}(\epsilon^{\prime\prime}_{2}(1/m),1/m)$. By (5), Claim
5.18, and since $\epsilon_{0}\ll\epsilon$, we have the following bound on the
size of $\mathbf{R}_{ij}^{0}$.

$|\mathbf{R}_{ij}^{0}|\leq(1+\epsilon_{2}^{\prime\prime}(\ell))\frac{n^{2}}{t^{2}\ell}(|R_{ij}^{0}|+|W_{ij}^{bad}|)\leq(1+\epsilon_{2}^{\prime\prime}(\ell))\frac{n^{2}}{t^{2}}(\epsilon^{75}+\epsilon_{0})\leq\epsilon^{50}\frac{n^{2}}{t^{2}}.$

Given $ijs\in{[t]\choose 3}$ with
$V_{i}V_{j},V_{j}V_{s},V_{i}V_{s}\notin\Psi^{\prime}$, and
$(u,v,w)\in[m_{2}]^{3}$, we define

$\mathbf{R}_{ijs}^{uvw}:=(V_{i}\cup V_{j}\cup
V_{s},\mathbf{R}^{u}_{ij}\cup\mathbf{R}^{v}_{js}\cup\mathbf{R}^{w}_{is}).$

By Corollary 2.6, for each such $\mathbf{R}_{ijs}^{uvw}$,

(6)
$\displaystyle|K_{3}^{(2)}(\mathbf{R}_{ijs}^{uvw})|=(1\pm\epsilon^{\prime}_{2}(m))\frac{n^{3}}{t^{3}m^{3}}.$

Our next goal is to show most of these $\mathbf{R}_{ijs}^{uvw}$ have density
near $0$ or $1$ with respect to $H$. In order to do this, we will need a few
more sets to help us avoid the error triads. Set

$\displaystyle\Sigma_{1}$
$\displaystyle=\Sigma_{0}\cup\\{V_{i}V_{j}V_{s}:ijs\in{[t]\choose 3}\text{ and
}{\\{V_{i},V_{j},V_{s}\\}\choose 2}\cap\Psi^{\prime}\neq\emptyset\\}.$

By the bounds given above,
$|\Sigma_{1}|\leq(\epsilon_{1}^{\prime})^{1/2}t^{3}+2\epsilon^{100}t^{2}\leq
3\epsilon^{100}t^{3}$. Given $ijs\in{[t]\choose 3}$, we define

$U_{ij}(s):=\\{P_{is}^{\beta}P_{js}^{\gamma}:\beta,\gamma\in[\ell]\\}.$

Note that for all $ij\in{[t]\choose 2}$, $U_{ij}=\bigcup_{s\in[t]}U_{ij}(s)$.
Then define

$\displaystyle\Sigma_{3}=\\{V_{i}V_{j}V_{s}\in{\mathcal{P}_{vert}\choose
3}\setminus\Sigma_{1}:\max\\{|U_{ij}(s)\cap U^{bad}_{ij}|,|U_{js}(i)\cap
U^{bad}_{js}|,|U_{is}(j)\cap U^{bad}_{is}|\geq\delta^{1/2}\ell^{2}\\}.$

Observe that for all $V_{i}V_{j}\notin\Psi^{\prime}$, the number of $V_{s}$
with $V_{i}V_{j}V_{s}\in\Sigma_{3}$ is at most $\delta^{1/2}t$. Consequently,
$|\Sigma_{3}|\leq\delta t^{3}$. We now set $\Sigma=\Sigma_{1}\cup\Sigma_{3}$,
and note that $|\Sigma|\leq 3\epsilon^{100}t^{3}+\delta t^{3}\leq
4\epsilon^{100}t^{3}$. This will end up being the desired $\Sigma$ at the end
of the proof. Our next goal is to show that if $V_{i}V_{j}V_{s}\notin\Sigma$,
then the density of edges on $K_{3}^{(2)}(\mathbf{R}_{ijs}^{uvw})$ is close to
$0$ or $1$ for all $u,v,w\in[m_{2}]$ (see Claim 5.19 below).

First, we need to show a couple things about triples outside $\Sigma$. Given
$V_{i}V_{j}V_{s}\notin\Sigma$, and $u\in[m_{2}]$, define

$\displaystyle U^{1}_{ij}(s)$
$\displaystyle=\\{P_{is}^{\beta}P_{js}^{\gamma}\in
U_{ij}(s):|\\{P_{ij}^{\alpha}\in\mathbf{R}_{ij}^{u}:G_{ijs}^{\alpha\beta\gamma}\in\mathbf{E}_{1}\\}|\geq(1-\psi(m))|\mathbf{R}_{ij}^{u}|\\},\text{
and }$ $\displaystyle U^{0}_{ij}(s)$
$\displaystyle=\\{P_{is}^{\beta}P_{js}^{\gamma}\in
U_{ij}(s):|\\{P_{ij}^{\alpha}\in\mathbf{R}_{ij}^{u}:G_{ijs}^{\alpha\beta\gamma}\notin\mathbf{E}_{1}\\}|\geq(1-\psi(m))|\mathbf{R}_{ij}^{u}|\\}.$

By Claim 5.18, we know that $U_{ij}(s)=U_{ij}^{bad}\cup U^{1}_{ij}(s)\cup
U^{0}_{ij}(s)$. However, we are more interested in the following set, rather
than $U_{ij}^{0}(s)$.

$\displaystyle U^{00}_{ij}(s)$
$\displaystyle=\\{P_{is}^{\beta}P_{js}^{\gamma}\in
U_{ij}(s):|\\{P_{ij}^{\alpha}\in\mathbf{R}_{ij}^{u}:G_{ijs}^{\alpha\beta\gamma}\in\mathbf{E}_{0}\\}|\geq(1-\psi(m)^{1/2})|\mathbf{R}_{ij}^{u}|\\}.$

Setting $U_{ij}^{err}(s)=U_{ij}(s)\setminus(U^{1}_{ij}(s)\cup
U^{00}_{ij}(s))$, we wish to show that
$|U_{ij}^{err}(s)|\leq\epsilon^{9}|U_{ij}(s)|$. Observe that

$|K_{2}[U_{ij}(s),W_{ij}]\cap\Gamma_{err}|\geq(\psi(m)^{1/2}-\psi(m))|U^{0}_{ij}(s)\setminus
U^{00}_{ij}(s)|\mathbf{R}_{ij}^{u}|\geq\psi(m)|U^{0}_{ij}(s)\setminus
U^{00}_{ij}(s)|\ell/m,$

where the last inequality uses the fact that $|\mathbf{R}_{ij}^{u}|=\ell/m$
and $\psi(m)<\epsilon<1/4$. Because $ijs\notin\Sigma_{1}$,
$|K_{2}[U_{ij}(s),W_{ij}]\cap\Gamma_{err}|\leq
2(\epsilon_{1}^{\prime})^{1/2}\ell^{3}$. Consequently, this implies

$\displaystyle|U^{0}_{ij}(s)\setminus U^{00}_{ij}(s)|\leq
2(\epsilon_{1}^{\prime})^{1/2}\ell^{3}\psi(m)^{-1}\frac{m}{\ell}=2(\epsilon_{1}^{\prime})^{1/2}m\psi(m)^{-1}\ell^{2}\leq(\epsilon_{1}^{\prime})^{1/4}\ell^{2},$

where the last inequality is because
$\epsilon_{1}^{\prime}\ll\psi((M!)^{3})/(M!)^{3}$. Further, since
$ijs\notin\Sigma_{3}$, $|U_{ij}(s)\cap U_{ij}^{bad}|\leq\delta^{1/2}\ell^{2}$,
so

$\displaystyle|U^{1}_{ij}(s)\cup
U^{00}_{ij}(s)|\geq|U_{ij}(s)|-|U^{0}_{ij}(s)\setminus
U^{00}_{ij}(s)|-|U_{ij}^{bad}(s)|$
$\displaystyle\geq(1-\delta^{1/2})\ell^{2}-(\epsilon_{1}^{\prime})^{1/4}\ell^{2}$
$\displaystyle\geq\ell^{2}(1-\epsilon^{50}),$

where the last inequality is because
$\epsilon^{\prime}_{1}\ll\delta\ll\epsilon$. This shows
$|U_{ij}^{err}(s)|\leq\epsilon^{50}|U_{ij}(s)|$. We will use this below.

######  Claim 5.19.

For all $ijs\in{[t]\choose 3}$ with $V_{i}V_{j}V_{s}\notin\Sigma$, and all
$(u,v,w)\in[m_{2}]^{3}$,

$\frac{|E\cap
K_{3}^{(2)}(\mathbf{R}_{ijs}^{uvw})|}{|K_{3}^{(2)}(\mathbf{R}_{ijs}^{uvw})|}\in[0,\epsilon)\cup(1-\epsilon,1].$

###### Proof.

Fix $ijs\in{[t]\choose 3}$ with $V_{i}V_{j}V_{s}\notin\Sigma$, and
$(u,v,w)\in[m_{2}]^{3}$. Suppose towards a contradiction that

(7) $\displaystyle\frac{|E\cap
K_{3}^{(2)}(\mathbf{R}_{ijs}^{uvw})|}{|K_{3}^{(2)}(\mathbf{R}_{ijs}^{uvw})|}\in[\epsilon,1-\epsilon].$

To ease notation, define $A=\mathbf{R}_{is}^{w}$, $B=\mathbf{R}_{js}^{v}$,
$C=\mathbf{R}_{ij}^{u}$, and let

$\displaystyle\mathbf{F}_{0}$ $\displaystyle=K_{2}[A,B]\cap
U_{ij}^{00}(s)\text{ and }\mathbf{F}_{1}=K_{2}[A,B]\cap U_{ij}^{1}(s).$

Then let $\mathbf{F}_{err}=K_{2}[A,B]\cap U_{ij}^{err}(s)$. Note
$|A|=|B|=|C|=\ell/m$, and our observations above show that
$|\mathbf{F}_{err}|\leq\epsilon^{50}|A||B|$. We claim that

(8)
$\displaystyle\min\\{|\mathbf{F}_{1}|,|K_{2}[A,B]\setminus\mathbf{F}_{1}|\\}\geq\epsilon^{3}|A||B|.$

Suppose towards a contradiction that (8) is false. Then either
$|\mathbf{F}_{1}|<\epsilon^{3}|A||B|$ or
$|K_{2}[A,B]\setminus\mathbf{F}_{1}|<\epsilon^{3}|A||B|$. Assume first that
$|\mathbf{F}_{1}|<\epsilon^{3}|A||B|$. Combining this with the above, we have
that

$|K_{2}[A,B]\setminus\mathbf{F}_{0}|\leq(\epsilon^{9}+\epsilon^{3})|A||B|\leq
2\epsilon^{3}|A||B|.$

Therefore, using (5),

$\displaystyle\sum_{\\{P_{is}^{\alpha}P_{js}^{\beta}\in
K_{2}[A,B]\setminus\mathbf{F}_{0}\\}}\sum_{P_{ij}^{\gamma}\in
C}|K_{3}(G_{ijk}^{\alpha,\beta,\gamma})|$
$\displaystyle\leq(1+\epsilon^{\prime\prime}_{2}(\ell))\frac{2\epsilon^{3}n^{3}}{t^{3}\ell^{3}}|A||B||C|\leq
3\epsilon^{3}\frac{n^{3}}{t^{3}m^{3}}.$

Note that if $P_{is}^{\alpha}P_{js}^{\beta}\in\mathbf{F}_{0}$, then at least a
$(1-\psi(m)^{1/2})|C|$ many elements in $P_{ij}^{\gamma}\in C$ are such that
$G_{ijs}^{\alpha,\beta,\gamma}\in\mathbf{E}_{0}$. Consequently,

$\displaystyle\sum_{P_{ij}^{\gamma}\in C}|E\cap
K_{3}(G_{ijk}^{\alpha,\beta,\gamma})|$
$\displaystyle\leq\sum_{\\{P_{ij}^{\gamma}:G_{ijs}^{\alpha,\beta,\gamma}\in\mathbf{E}_{0}\\}}\epsilon_{1}^{\prime\prime}|K_{3}(G_{ijk}^{\alpha,\beta,\gamma})|+\sum_{\\{P_{ij}^{\gamma}:G_{ijs}^{\alpha,\beta,\gamma}\notin\mathbf{E}_{0}\\}}|K_{3}(G_{ijk}^{\alpha,\beta,\gamma})|$
$\displaystyle\leq(1+\epsilon_{2}(\ell))\frac{n^{3}}{t^{3}\ell^{3}}(\epsilon_{1}^{\prime\prime}|C|(1-\psi(m)^{1/2})+\psi(m)^{1/2}|C|)$
$\displaystyle\leq\epsilon^{5}\frac{n^{2}}{t^{3}m\ell^{2}},$

where the last inequality uses that $|C|=\ell/m$ and that
$\psi(m),\epsilon_{1}^{\prime}(\ell),\epsilon_{1}^{\prime\prime}\ll\epsilon$.
So we have that

$\displaystyle|E\cap K_{3}^{(2)}(\mathbf{R}_{ijs}^{uvw})|$ $\displaystyle\leq
2\epsilon^{3}\frac{n^{3}}{t^{3}m^{3}}+\epsilon^{5}|A||B|\frac{n^{3}}{t^{3}m\ell^{2}}\leq
3\epsilon^{3}\Big{(}\frac{n}{t}\Big{)}^{3}\frac{1}{m^{3}}.$

By (6), this shows that $|E\cap
K_{3}^{(2)}(\mathbf{R}_{ijs}^{uvw})|<\epsilon|K_{3}^{(2)}(\mathbf{R}_{ijs}^{uvw})|$,
contradicting (7). Thus we must have that
$|K_{2}[A,B]\setminus\mathbf{F}_{1}|<\epsilon^{3}K_{2}[A,B]$. In this case,

$|\mathbf{F}_{0}\cup\mathbf{F}_{err}|\leq\epsilon^{3}|A||B|=\epsilon^{3}\frac{\ell^{2}}{m^{2}}.$

Consequently, using (5),

$\sum_{\\{P_{is}^{\alpha}P_{js}^{\beta}\in\mathbf{F}_{0}\cup\mathbf{F}_{err}\\}}\sum_{P_{ij}^{\gamma}\in
C}|K_{3}(G_{ijk}^{\alpha,\beta,\gamma})|\leq(1+\epsilon^{\prime\prime}_{2}(\ell))\frac{\epsilon^{3}n^{3}}{t^{2}m^{3}}\leq\frac{2\epsilon^{3}n^{3}}{t^{3}m^{3}}.$

On the other hand, for each $P_{is}^{\alpha}P_{js}^{\beta}\in\mathbf{F}_{1}$,
we know that at least $(1-\psi(m))|C|$ many elements in $P_{ij}^{\gamma}\in C$
are such that $G_{isj}^{\alpha,\beta,\gamma}\in\mathbf{E}_{1}$. Consequently,

$\displaystyle\sum_{\\{P_{is}^{\alpha}P_{js}^{\beta}\in\mathbf{F}_{0}\\}}\sum_{P_{ij}^{\gamma}\in
C}|K_{3}(G_{ijk}^{\alpha,\beta,\gamma})\setminus E|$
$\displaystyle\leq(1+\epsilon_{2}^{\prime\prime}(\ell))\Big{(}\frac{n}{t\ell}\Big{)}^{3}|A||B|(\psi(m)|C|+(1-\psi(m))\epsilon_{1}^{\prime\prime}|C|)$
$\displaystyle\leq\epsilon^{5}\Big{(}\frac{n}{t}\Big{)}^{3}\frac{1}{m^{3}},$

where the last inequality uses that $|C|=\ell/m$ and that
$\psi(m),\epsilon_{1}^{\prime}(\ell),\epsilon_{1}^{\prime\prime}\ll\epsilon$.
Combining these, we obtain the that

$\displaystyle|K_{3}^{(2)}(\mathbf{R}_{ijs}^{uvw})\setminus E|$
$\displaystyle\leq\frac{2\epsilon^{3}n^{3}}{m^{3}}+\epsilon^{5}\frac{n^{3}}{t^{3}m^{3}}\leq
3\epsilon^{3}\Big{(}\frac{n}{t}\Big{)}^{3}\frac{1}{m^{3}}.$

By (6), this shows that $|K_{3}^{(2)}(\mathbf{R}_{ijs}^{uvw})\setminus
E|<|K_{3}^{(2)}(\mathbf{R}_{ijs}^{uvw})|$, contradicting (7). Thus we must
have that $|K_{2}[A,B]\setminus\mathbf{F}_{1}|<\epsilon^{3}|A||B|$, and
therefore (8) is false.

Consider the bipartite graph $G_{AB}=(A\cup B,\mathbf{F}_{1})$. Since (8) is
false, Lemma 4.9 implies one of the following holds.

  1. (1)

There is a set $S\subseteq B$ of size at least $\epsilon^{6}|B|/2$ such that
for all $b\in S$

$\min\\{|N_{G_{AB}}(b)|,|\neg N_{G_{AB}}(b)|\\}\geq\epsilon^{6}|A|/2.$

  2. (2)

There is a set $S\subseteq A$ of size at least $\epsilon^{6}|A|/2$ such that
for all $a\in S$

$\min\\{|N_{G_{AB}}(a)|,|\neg N_{G_{AB}}(a)|\\}\geq\epsilon^{6}|B|/2.$

Let us assume (1) holds (case (2) is similar). So there is some $S\subseteq B$
of size at least $\epsilon^{6}|B|/2$ such that for all $b\in S$

$\min\\{|N_{G_{AB}}(b)|,|\neg N_{G_{AB}}(b)|\\}\geq\epsilon^{6}|A|/2.$

Recall we showed $|\mathbf{F}_{err}|\leq\epsilon^{50}|A||B|$, so if we let

$S^{\prime}=\\{b\in S:|\\{a\in
A:ab\in\mathbf{F}_{err}\\}|\leq\epsilon^{25}|A|\\},$

then
$|S^{\prime}|\geq|S|-\epsilon^{25}|B|\geq\epsilon^{6}|B|/2-\epsilon^{25}|B|\geq\epsilon^{6}|B|/4$,
where the inequality is because $\epsilon<1/4$. For each $b\in S^{\prime}$,
set

$A_{0}(b)=\\{a\in A:ab\in\mathbf{F}_{0}\\}\text{ and }A_{1}(b)=\\{a\in
A:ab\in\mathbf{F}_{1}\\}.$

By definition of $S^{\prime}$, $|A_{1}(b)|\geq\epsilon^{6}|A|/2$, and
$|A_{0}(b)|\geq\epsilon^{6}|A|/2-\epsilon^{25}|A|\geq\epsilon^{6}|A|/4$. Now
consider the bipartite graphs $G_{0}(b)=(A_{0}(b)\cup C,E_{0}(b))$ and
$G_{0}(b)=(A_{1}(b)\cup C,E_{1}(b))$, where

$\displaystyle E_{0}(b)$ $\displaystyle=\\{ca\in
K_{2}[C,A_{0}(b)]:G_{ijs}^{\alpha,\beta,\gamma}\in\mathbf{E}_{0}\text{ where
}c=P_{ij}^{\alpha},a=P_{is}^{\beta},\text{ and }b=P_{js}^{\gamma}\\}$
$\displaystyle E_{1}(b)$ $\displaystyle=\\{ca\in
K_{2}[C,A_{1}(b)]:G_{ijs}^{\alpha,\beta,\gamma}\in\mathbf{E}_{1}\text{ where
}c=P_{ij}^{\alpha},a=P_{is}^{\beta},\text{ and }b=P_{js}^{\gamma}\\}.$

We claim that for all $b\in S^{\prime}$ and $a\in A_{0}(b)$,
$|N_{G_{0}(b)}(a)|\geq(1-\psi(m)^{1/2})|C|$. Say $b=P_{js}^{\gamma}\in
S^{\prime}$ and $a=P_{is}^{\beta}\in A_{0}(b)$. Since $ab\in\mathbf{F}_{0}$,
we know that $P_{js}^{\gamma}P_{is}^{\beta}\in W_{ij}^{00}(s)$. By definition,
this means that

$|N_{G_{0}(b)}(a)|=|\\{c=P_{ij}^{\alpha}\in
C:G_{ijs}^{\alpha,\beta,\gamma}\in\mathbf{E}_{0}\\}|\geq(1-\psi(m)^{1/2})|C|,$

as desired. Consequently, $|E_{0}(b)|\geq(1-\psi(m)^{1/2})|C||A_{0}(b)|$.
Standard arguments show that this implies there is a set $C_{0}(b)\subseteq C$
with $|C_{0}(b)|\geq(1-\psi(m)^{1/4})|C|$ so that for all $c\in C_{0}(b)$,

$|N_{G_{0}(b)}(c)|\geq(1-\psi(m)^{1/4})|A_{0}(b)|\geq(1-\psi(m)^{1/4})\epsilon^{6}|A|/2\geq\epsilon^{6}|A|/4.$

A similar argument shows that for all $b\in S^{\prime}$ and $a\in A_{1}(b)$,
$|N_{G_{1}(b)}(a)|\geq(1-\psi(m)^{1/2})|C|$, so
$|E_{1}(b)|\geq(1-\psi(m)^{1/4})|C||A_{1}(b)|$. Thus there exists a set
$C_{1}(b)\subseteq C$ with $|C_{1}(b)|\geq(1-\psi(m)^{1/4})|C|$ so that for
all $c\in C_{1}(b)$,

$|N_{G_{1}(b)}(c)|\geq(1-\psi(m)^{1/4})|A_{1}(b)|\geq(1-\psi(m)^{1/4})\epsilon^{6}|A|/2\geq\epsilon^{6}|A|/4.$

Combining these, we have that for all $b\in S^{\prime}$, there is a set
$C(b)=C_{0}(b)\cap C_{1}(b)\subseteq C$, with size
$|C(b)|\geq(1-2\psi(m)^{1/4})|C|$, such that for all $c\in C(b)$,

$\min\\{|N_{G_{0}(b)}(c)|,|N_{G_{1}(b)}(c)|\\}\geq\epsilon^{6}|A|/4.$

We claim that for all $b\in S^{\prime}$ and $c\in C(b)$, $bc\in U_{is}^{bad}$.
To this end, fix $b\in S^{\prime}$ and $c\in C(b)$. Then $b=P_{js}^{\beta}$
and $c=P_{ij}^{\alpha}$ for some $\beta,\alpha\in[\ell]$. By above and the
definition of $H_{is}$,

$\displaystyle\epsilon^{6}|A|/4$
$\displaystyle\leq\min\\{|N_{G_{0}(b)}(c)|,|N_{G_{1}(b)}(c)|\\}$
$\displaystyle=\min\\{|P_{is}^{\gamma}\in
A:G_{ijs}^{\alpha,\beta,\gamma}\in\mathbf{E}_{0}\\}|,\\{|P_{is}^{\gamma}\in
A:G_{ijs}^{\alpha,\beta,\gamma}\in\mathbf{E}_{1}\\}|\\}$
$\displaystyle\leq\min\\{|N_{H_{is}}(P_{js}^{\beta}P_{ij}^{\alpha})\cap
A|,|\neg N_{H_{is}}(P_{js}^{\beta}P_{ij}^{\alpha})\cap A|\\}$

This shows $A=\mathbf{R}_{is}^{w}$ is not $\epsilon^{6}/4$-good in $H_{is}$
with respect to $bc$. Since $V_{i}V_{j}V_{s}\notin\Sigma$, we know that
$\mathbf{R}_{is}^{w}$ is $\psi(m)$-good with respect to every $u\in
U_{is}\setminus U_{is}^{bad}$, so since $\psi(m)\ll\epsilon$, this implies
that $bc\in U_{is}^{bad}$. Thus we have shown that for all $b\in S^{\prime}$
and $c\in C(b)$, $bc\in U_{is}^{bad}$. Combining this with the bounds above,
we have that

$|U_{is}^{bad}|\geq|S^{\prime}|(1-2\psi(m)^{1/4})|C|\geq\epsilon^{6}|B||C|/4=\epsilon^{6}\ell^{2}/4m^{2}.$

However, by Claim 5.18,
$|U_{is}^{bad}|\leq\delta\ell^{2}<\epsilon^{6}\ell^{2}/4m^{2}$, where the last
inequality is since $\delta\ll\epsilon/M$ and $m\leq M^{3}$. Thus, we have
arrived at a contradiction, which finishes the proof of Claim 5.19. ∎

We are nearly done. The last main task is to redistribute
$\mathbf{R}_{ij}^{0}$ for each $V_{i}V_{j}\notin\Psi^{\prime}$. Fix
$V_{i}V_{j}\notin\Psi^{\prime}$. Recall that $|W_{ij}|=\ell$, and
$|R_{ij}^{0}|=|W_{ij}|-|B_{ij}^{1}\cup\ldots\cup B_{ij}^{m_{2}}|=\ell-\ell
m_{2}/m$. Since $m_{2}\leq M$, and $(M!)^{3}$ divides $\ell$, we know $m_{2}$
divides $\ell$, say $\ell=m_{3}m_{2}$. Note this implies
$|R_{ij}^{0}|=m_{2}m_{3}-m_{2}\ell/m$. Similarly, since $m\leq(M!)^{3}$, $m$
also divides $\ell$, so we can choose a partition
$R_{ij}^{0}=S_{ij}^{1}\cup\ldots\cup S_{ij}^{m_{2}}$ into sets of size
$(m_{2}m_{3}-m_{2}\ell/m)/m_{2}=m_{3}-\ell/m$. For each $u\in[m_{2}]$, define

$\mathbf{S}^{u}_{ij}=\\{xy\in K_{2}[V_{i},V_{j}]:xy\in P_{ij}^{\alpha}\text{
for some }P_{ij}^{\alpha}\in S_{ij}^{u}\\}.$

By Fact 2.23, $\mathbf{S}_{ij}^{u}$ has
$\textnormal{disc}_{2}(m\epsilon_{2}^{\prime\prime\prime}(\ell))$. By our
choice of $\epsilon_{2}^{\prime\prime}$, this implies $\mathbf{S}_{ij}^{u}$
has $\textnormal{disc}_{2}(\epsilon_{2}^{\prime}(\ell))$. Now set
$\mathbf{P}_{ij}^{u}=\mathbf{R}_{ij}^{u}\cup\mathbf{S}_{ij}^{u}$ for each
$u\in[m_{2}]$. Note each $\mathbf{P}_{ij}^{u}$ is a union of
$m_{3}-\ell/m+\ell/m=m_{3}$ elements of $\mathcal{P}_{edge}$, so by Fact 2.23,
$\mathbf{P}_{ij}^{u}$ satisfies
$\textnormal{disc}_{2}(m\epsilon^{\prime\prime}_{2}(\ell))$ and has size
$m_{3}\frac{n^{2}}{\ell}(1\pm m_{3}\epsilon_{2}^{\prime}(\ell))$. Combining
this with our choice of $\epsilon_{2}^{\prime\prime}$ and the fact that
$m_{3}/\ell=1/m_{2}$, we have that each $\mathbf{P}_{ij}^{u}$ satisfies
$\textnormal{disc}_{2}(\epsilon_{2}(m_{2}),1/m_{2})$. By construction, we know
that each $|S_{ij}^{u}|\leq|R_{ij}^{0}|/m_{2}\leq\epsilon^{75}\ell/m_{2}$.
Therefore,
$|\mathbf{S}_{ij}^{u}|\leq\epsilon^{25}\frac{n^{2}}{t^{2}m_{2}^{2}}\leq\epsilon^{10}|\mathbf{P}_{ij}^{u}|$.

Now for each $V_{i}V_{j}\in\Psi^{\prime}$, choose an arbitrary partition
$K_{2}[V_{i},V_{j}]=\bigcup_{\alpha\leq m_{2}}\mathbf{P}_{ij}^{\alpha}$. Since
$|\Psi^{\prime}|\leq 3\epsilon^{100}t^{2}$, and every $\mathbf{P}_{ij}^{u}$
satisfies $\textnormal{disc}_{2}(\epsilon_{2}(m_{2}),1/m_{2})$, we have a
$(t,m_{2},\epsilon^{50},\epsilon_{2}(m_{2}))$-decomposition $\mathcal{Q}$ with
$\mathcal{Q}_{vert}=\\{V_{1},\ldots,V_{t}\\}$ and

$\mathcal{Q}_{edge}=\\{\mathbf{P}_{ij}^{u}:ij\in{[t]\choose
2},u\in\\{1,\ldots,m_{2}\\}\\}.$

We claim that for all $V_{i}V_{j}V_{s}\notin\Sigma$,
$\mathbf{P}_{ijs}^{\alpha,\beta,\gamma}$ is $2\epsilon$-homogeneous with
respect to $H$.

Fix $V_{i}V_{j}V_{s}\notin\Sigma$, and $\alpha,\beta,\gamma\in[m_{2}]$. By
construction, there are $u,v,w\in[m_{2}]$ so that

$\displaystyle\mathbf{P}_{ij}^{\alpha}=\mathbf{R}_{ij}^{u}\cup\mathbf{S}_{ij}^{u},\text{
}\mathbf{P}_{is}^{\beta}=\mathbf{R}_{is}^{v}\cup\mathbf{S}_{is}^{v},\text{ and
}\mathbf{P}_{is}^{\gamma}=\mathbf{R}_{js}^{w}\cup\mathbf{S}_{js}^{w}.$

By Claim 5.19, there is $\tau\in\\{0,1\\}$ such that $|E^{\tau}\cap
K_{3}^{(2)}(\mathbf{R}_{ijs}^{u,v,w})|\leq\epsilon\frac{n^{3}}{t^{3}m_{2}^{3}}$.
Define

$\displaystyle G_{is}$ $\displaystyle=(V_{i}\cup V_{j}\cup
V_{s},\mathbf{P}_{ij}^{\alpha}\cup\mathbf{S}_{is}^{v}\cup\mathbf{P}_{is}^{\gamma})$
$\displaystyle G_{ij}$ $\displaystyle=(V_{i}\cup V_{j}\cup
V_{s},\mathbf{S}_{ij}^{u}\cup\mathbf{P}_{is}^{\beta}\cup\mathbf{P}_{is}),\text{
and }$ $\displaystyle G_{js}$ $\displaystyle=(V_{i}\cup V_{j}\cup
V_{s},\mathbf{P}_{ij}^{\alpha}\cup\mathbf{P}_{is}^{\beta}\cup\mathbf{S}_{js}^{w}).$

By Corollary 2.6, and the bound above on the size of each
$\mathbf{S}_{ij}^{u},\mathbf{S}_{is}^{v},\mathbf{S}_{js}^{w}$, we have that

$\max\\{|K_{3}^{(2)}(G_{ij})|,|K_{3}^{(2)}(G_{ij})|,|K_{3}^{(2)}(G_{ij})|\\}\leq\epsilon^{10}\frac{n^{3}}{t^{3}m_{2}^{3}}\leq\epsilon^{5}|K_{3}^{(2)}(\mathbf{P}_{ijs}^{\alpha,\beta,\gamma})|,$

where the last inequality uses Corollary 2.6. Thus we have that

$\displaystyle|E^{\tau}\cap
K_{3}^{(2)}(\mathbf{P}_{ijs}^{\alpha,\beta,\gamma})|$
$\displaystyle\leq\epsilon\frac{n^{3}}{t^{3}m_{2}^{3}}+\epsilon^{10}|K_{3}^{(2)}(\mathbf{P}_{ijs}^{\alpha,\beta,\gamma})|\leq
2\epsilon|K_{3}^{(2)}(\mathbf{P}_{ijs}^{\alpha,\beta,\gamma})|.$

Since $\epsilon\ll\epsilon_{1}$, this implies that
$\mathbf{P}_{ijs}^{\alpha,\beta,\gamma}$ is $\epsilon_{1}$-homogeneous with
respect to $H$ and moreover. By Proposition 2.22, satisfies
$\textnormal{disc}_{2,3}(\epsilon_{1},\epsilon_{2}(m_{2}))$ with respect to
$H$. This finishes the proof of Theorem 1.56. ∎

We now prove Theorem 1.57, which says a hereditary $3$-graph property admits
linear $\textnormal{disc}_{2,3}$-error if and only if it is
$\operatorname{NFOP}_{2}$.

Proof of Theorem 1.57: Suppose $\mathcal{H}$ is an $\operatorname{NFOP}_{2}$,
hereditary $3$-graph property. That $\mathcal{H}$ admits linear
$\textnormal{disc}_{2,3}$-error follows immediately from Theorem 1.56.

Conversely, suppose that $\mathcal{H}$ has $\operatorname{FOP}_{2}$. We show
that it requires non-linear $\textnormal{disc}_{2,3}$-error. Choose
$0<\epsilon_{1}^{\prime}\ll\epsilon_{1}\ll 1$, and choose
$\epsilon_{2},\epsilon_{2}^{\prime}:\mathbb{N}\rightarrow(0,1]$ so that for
all $x\in\mathbb{N}$, $0<\epsilon_{2}^{\prime}(x)\ll\epsilon_{2}(x)\leq 1/4x$.
Fix $T,L,N\geq 1$. We show that there is some $H\in\mathcal{H}$ with
$|V(H)|\geq N$ so that there exists no
$(t,\ell,\epsilon_{1}^{\prime},\epsilon_{2}^{\prime}(\ell))$-decomposition
$\mathcal{P}$ of $V(H)$ which is $\textnormal{disc}_{2,3}$-regular with
respect to $H$ with linear error.

Choose $m\gg
L,T,N,(\epsilon_{1}^{\prime})^{-1},(\epsilon_{2}^{\prime}(L))^{-1}$ and $N\gg
m$. By Lemma 2.24, there exist sets $B=\\{b_{i}:i\in[n]\\}$ and
$C=\\{c_{i}:i\in[n]\\}$ and $\gamma_{1},\ldots,\gamma_{m}\subseteq K_{2}[B,C]$
so that for each $i\in[m]$, $\gamma_{i}$ has
$\textnormal{disc}_{2}(\epsilon_{2}(m)/T^{2},1/m)$. Let
$A=\\{a_{i}:i\in[n]\\}$ be a set of size $n$.

By Lemma 5.8, there exists $H=(V,E)\in\mathcal{H}$ with $V=A\cup B\cup C$,
such that for all $i,j,s\in[n]$, $a_{i}b_{j}c_{s}\in E$ if and only if
$b_{j}c_{s}\in\gamma_{u}$ for some $u\geq\lfloor in/\ell\rfloor$. We show that
there does not exist $1\leq\ell\leq L$, $1\leq t\leq T$ and a
$(t,\ell,\epsilon^{\prime}_{1},\epsilon^{\prime}_{2})$-decomposition of $V$
which is $(\epsilon^{\prime}_{1},\epsilon^{\prime}_{2}(\ell))$-regular with
respect to $H$ with linear $\textnormal{disc}_{2,3}$-error.

Suppose towards a contradiction that there exists some $1\leq\ell\leq L$,
$1\leq t\leq T$ and a
$(t,\ell,\epsilon^{\prime}_{1},\epsilon^{\prime}_{2})$-decomposition
$\mathcal{P}$ of $V$ which is
$(\epsilon^{\prime}_{1},\epsilon^{\prime}_{2}(\ell))$-regular with respect to
$H$, and a set $\Sigma\subseteq{[t]\choose 3}$ with
$|\Sigma|\leq\epsilon_{1}^{\prime}t^{3}$ so that if
$G\in\operatorname{Triads}(\mathcal{P})$ fails
$\textnormal{disc}_{2,3}(\epsilon_{1}^{\prime},\epsilon_{2}^{\prime}(\ell))$
with respect to $(H,\mathcal{P})$, then $V(G)\subseteq V_{i}\cup V_{j}\cup
V_{k}$ for some $ijk\in\Sigma$. Say $\mathcal{P}_{vert}=\\{V_{i}:i\in[t]\\}$
and $\mathcal{P}_{edge}=\\{P_{ij}^{\alpha}:ij\in{[t]\choose
2},\alpha\leq\ell\\}$.

For each $i\in[T]$, and $X\in\\{A,B,C\\}$, set $X_{i}=X\cap V_{i}$. For each
$X\neq Y$, $i\neq j$, and $\alpha\in[\ell]$ we let
$P_{X_{i}Y_{j}}^{\alpha}=P_{ij}^{\alpha}\cap K_{2}[X_{i},Y_{j}]$.

Given $i\in[t]$ and $X\in\\{A,B,C\\}$, we say that $X_{i}$ is _trivial_ if
$|X_{i}|<\epsilon_{1}|V_{i}|$, and that a vertex $x\in V$ is trivial if $x\in
X_{i}$ for some trivial $X_{i}$. For each $i\in[t]$, at most two elements of
$\\{A_{i},B_{i},C_{i}\\}$ are trivial, and therefore, $V_{i}$ contains at most
$2\epsilon_{1}|V_{i}|$ many trivial vertices. Thus, at most
$2\epsilon_{1}(3n)$ vertices are trivial. For each $X\in\\{A,B,C\\}$, let
$\mathcal{I}_{X}$ be the set of $i\in[T]$ such that $X_{i}$ is non-trivial.
Then for each $X\in\\{A,B,C\\}$, we have
$|X\cap(\bigcup_{i\in\mathcal{I}_{X}}X_{i})|\geq(1-12\epsilon_{1})|X|$, and
consequently

$|\mathcal{I}_{X}|\geq(1-12\epsilon_{1})|X|/(3n/t)=(1-12\epsilon_{1})t/3.$

Now define

$\mathcal{S}_{1}=\\{X_{i}Y_{j}:X\neq Y\in\\{A,B,C\\}\text{ and either
}i=j,\text{ or }i\in\mathcal{I}_{X}\text{ or }j\in\mathcal{I}_{Y}\\}.$

By the above, $|\mathcal{S}_{1}|\leq 3t+3(12\epsilon_{1})t^{2}/3\leq
40\epsilon_{1}t^{2}$. Now let

$\mathcal{S}_{2}=\\{X_{i}Y_{j}:X\neq
Y\in\\{A,B,C\\},ij\notin\mathcal{S}_{1}\text{ and
}|\\{Z_{s}:X_{i}Y_{j}Z_{s}\in\Sigma\\}|\geq\sqrt{\epsilon^{\prime}_{1}}t\\}.$

Since $|\Sigma|\leq\epsilon_{1}^{\prime}t^{3}$,
$|\mathcal{S}_{2}|\leq\sqrt{\epsilon_{1}^{\prime}}t^{2}$. Now let
$\mathcal{S}=\mathcal{S}_{1}\cup\mathcal{S}_{2}$. Then $|\mathcal{S}|\leq
2\sqrt{\epsilon_{1}}t^{2}$ (recall $\epsilon_{1}^{\prime}\ll\epsilon_{1}\ll
1$). By above,
$|\mathcal{I}_{B}||\mathcal{I}_{C}|\geq(1-12\epsilon_{1})^{2}t^{2}/3$, so
there must exist some $B_{j}C_{s}\notin\mathcal{S}$ with
$B_{j}\in\mathcal{I}_{B}$ and $C_{s}\in\mathcal{I}_{C}$. Define
$\mathcal{I}_{A}^{\prime}=\\{i\in\mathcal{I}_{A}:A_{i}B_{j}C_{s}\notin\Sigma\\}$,
and set $A^{\prime}=\bigcup_{i\in\mathcal{I}_{A}^{\prime}}A_{i}$. By
construction, and since $\epsilon_{1}^{\prime}\ll\epsilon_{1}$,

$|A^{\prime}|\geq(1-12\epsilon_{1})|A|-\sqrt{\epsilon_{1}^{\prime}}t(3n/t)\geq(1-13\epsilon_{1})|A|.$

Given $\alpha\in[\ell]$, define

$\displaystyle
I^{\alpha}_{B_{j}C_{s}}=\\{u\in[\ell]:|P^{\alpha}_{B_{j}C_{s}}\cap\gamma_{u}|\geq\epsilon_{1}|P^{\alpha}_{B_{j}C_{s}}|/\ell\\},$

and set $R^{\alpha}_{B_{j}C_{s}}=\bigcup_{u\in
I^{\alpha}_{B_{j}C_{s}}}(P^{\alpha}_{B_{j}C_{s}}\cap\gamma_{u})$. Note

$|P^{\alpha}_{B_{j}C_{s}}\setminus
R^{\alpha}_{B_{j}C_{s}}|\leq\ell(\epsilon_{1}|P^{\alpha}_{B_{j}C_{s}}|/\ell)<\epsilon_{1}|P^{\alpha}_{B_{j}C_{s}}|.$

Given $v\in[m]$, let $\gamma_{v}^{+}=\bigcup_{u>v}\gamma_{u}$ and
$\gamma_{v}^{-}=\bigcup_{v<u}\gamma_{u}$. Then define

$\displaystyle I^{\alpha}_{B_{j}C_{s}}(\epsilon_{1})$ $\displaystyle=\\{u\in
I^{\alpha}_{B_{j}C_{s}}:\min\\{|P^{\alpha}_{B_{j}C_{s}}\cap\gamma_{u}^{+}|,|P^{\alpha}_{B_{j}C_{s}}\cap\gamma_{u}^{-}|\\}\geq\epsilon_{1}|P^{\alpha}_{B_{j}C_{s}}|\\}.$

Clearly $I^{\alpha}_{B_{j}C_{s}}(\epsilon_{1})$ is an interval, say
$I^{\alpha}_{B_{j}C_{s}}(\epsilon_{1})=[u_{1},u_{2}]$. Define

$R^{\alpha}_{B_{j}C_{s}}(\epsilon_{1})=\bigcup_{u\in
I^{\alpha}_{B_{j}C_{s}}(\epsilon_{1})}(P^{\alpha}_{B_{j}C_{s}}\cap\gamma_{u}).$

This implies that

$\displaystyle|P^{\alpha}_{B_{j}C_{s}}\setminus
R^{\alpha}_{B_{j}C_{s}}(\epsilon)|\leq|P^{\alpha}_{B_{j}C_{s}}\setminus
R^{\alpha}_{B_{j}C_{s}}|+|R^{\alpha}_{B_{j}C_{s}}\cap[u_{2}+1,n]|+|P^{\alpha}_{B_{j}C_{s}}\cap[1,u_{1}-1]|\leq
3\epsilon_{1}|P^{\alpha}_{B_{j}C_{s}}|.$

Consequently,

$\displaystyle|\bigcup_{\alpha\in[\ell]}R^{\alpha}_{B_{j}C_{s}}(\epsilon_{1})|\geq(1-3\epsilon_{1})|B_{j}||C_{s}|,$

which implies that
$|\bigcup_{\alpha\in[\ell]}I^{\alpha}_{B_{j}C_{s}}(\epsilon_{1})|\geq(1-3\epsilon_{1})|B_{j}||C_{s}|/(|B_{j}||C_{s}|/\ell)\geq(1-3\epsilon_{1})\ell$.

Given $u\in[\ell]$, let $u^{+}=[\lceil(u-1)n/\ell\rceil,n]$,
$u^{-}=[1,\lfloor(u+1)n/\ell\rfloor]$, and set

$u^{*}=[\lfloor(u+1)n/\ell\rfloor,\lceil(u-1)n/\ell\rceil].$

Given $i\in[t]$, we then define

$I_{i}=\\{u\in[\ell]:|A_{i}\cap u^{*}|\geq\epsilon_{1}|A_{i}|\\},$

and we set $I_{i}(\epsilon)=\\{u\in[\ell]:\min\\{|A_{i}\cap u^{+}|,|A_{i}\cap
u^{-}|\\}\geq\epsilon_{1}|A_{i}|\\}$. Clearly $I_{i}(\epsilon_{1})$ is an
interval, say $I_{i}(\epsilon_{1})=[v_{1},v_{2}]$. Set
$A_{i}(\epsilon_{1})=\bigcup_{u\in I_{i}(\epsilon_{1})}(A_{i}\cap u^{*})$, and
observe that

$|A_{i}\setminus A_{i}(\epsilon_{1})|\leq|A_{i}\cap v_{1}^{-}|+|A_{i}\cap
v_{2}^{+}|\leq 2\epsilon_{1}|A_{i}|.$

Consequently,
$|\bigcup_{i\in\mathcal{I}^{\prime}_{A}}A_{i}(\epsilon_{1})|\geq(1-2\epsilon_{1})|A^{\prime}|$,
which implies that

$|\bigcup_{i\in\mathcal{I}_{A}^{\prime}}I_{i}(\epsilon_{1})|\geq(1-2\epsilon_{1})|A^{\prime}|/(n/\ell)\geq(1-2\epsilon_{1})^{2}\ell(1-13\epsilon_{1})\ell\geq(1-20\epsilon_{1})\ell.$

This implies, with the above, that

$\displaystyle|\Big{(}\bigcup_{i\in\mathcal{I}_{A}^{\prime}}I_{i}(\epsilon_{1})\Big{)}\cap\Big{(}\bigcup_{\alpha\in[\ell]}I^{\alpha}_{B_{j}C_{s}}(\epsilon_{1})\Big{)}|$
$\displaystyle\geq(1-23\epsilon_{1})\ell>0.$

Choose any
$u\in(\bigcup_{i\in\mathcal{I}_{A}^{\prime}}I_{i}(\epsilon_{1})\Big{)}\cap\Big{(}\bigcup_{\alpha\in[\ell]}I^{\alpha}_{B_{j}C_{s}}(\epsilon_{1}))$
and define

$\displaystyle G_{1}$ $\displaystyle=((A_{i}\cap u^{+})\cup B_{j}\cup
C_{S},(P_{B_{j}C_{s}}^{\alpha}\cap\gamma_{u}^{-})\cup
P_{A_{i}C_{s}}^{\beta}\cup P_{B_{j}A_{i}}^{\gamma})$ $\displaystyle G_{0}$
$\displaystyle=((A_{i}\cap u^{-})\cup B_{j}\cup
C_{S},(P_{B_{j}C_{s}}^{\alpha}\cap\gamma_{u}^{+})\cup
P_{A_{i}C_{s}}^{\beta}\cup P_{B_{j}A_{i}}^{\gamma})$

By construction, $K_{3}^{(2)}(G_{1})\subseteq E$ and $K_{3}^{(2)}(G_{0})\cap
E\neq\emptyset$. On the other hand, since $V_{i}V_{j}V_{s}\notin\Sigma$, we
must have that $(H_{ijs}^{\alpha,\beta,\gamma},G_{ijs}^{\alpha,\beta,\gamma})$
satisfies
$\textnormal{disc}_{2,3}(\epsilon_{1}^{\prime},\epsilon_{2}^{\prime}(\ell))$.
Let $d\in[0,1]$ be such that $|E\cap
K_{3}^{(2)}(G_{ijs}^{\alpha,\beta,\gamma})|=d|K_{3}^{(2)}(G_{ijs}^{\alpha,\beta,\gamma})|$.
Without loss of generality, say $d\leq 1/2$ (the other case is similar). By
above, and by definition of
$\textnormal{disc}_{2,3}(\epsilon_{1}^{\prime},\epsilon_{2}^{\prime}(\ell))$,

$\frac{1}{2}|K_{3}^{(2)}(G_{1})|\leq|K_{3}^{(2)}(G_{1})|(1-d)=\Big{|}|E\cap
K_{3}^{(2)}(G_{1})|-d|K_{3}^{(2)}(G_{1})|\Big{|}\leq\epsilon^{\prime}_{1}\frac{n^{3}}{\ell^{3}t^{3}}.$

Thus $|K_{3}^{(2)}(G_{1})|\leq
2\epsilon_{1}^{\prime}\frac{n^{3}}{\ell^{3}t^{3}}$.

Given $b\in B_{j}$, let $X_{b}^{-}=\\{a\in A_{i}\cap u^{-}:ab\in
P_{ij}^{\gamma}\\}$. Because $P_{ij}^{\gamma}$ satisfies
$\textnormal{disc}_{2}(\epsilon_{2}^{\prime}(\ell),1/\ell)$, Lemma 2.18
implies $P_{A_{i}B_{j}}^{\gamma}[A_{i}\cap u^{-},B_{j}]$ satisfies
$\textnormal{disc}_{2}(\epsilon_{2}(\ell),1/\ell)$. Therefore, a standard
argument shows that there is a set $B_{j}^{\prime}\subseteq V_{j}$ of size at
least $(1-\sqrt{\epsilon_{2}(\ell)})|B_{j}|$ such that for all $b\in
B_{j}^{\prime}$,

$|X_{b}^{-}|=\frac{|A_{i}\cap
u^{-}|}{\ell}(1\pm\sqrt{\epsilon_{2}^{\prime}(\ell)})\geq\frac{|A_{i}\cap
u^{-}|}{2\ell}\geq\epsilon_{1}|V_{i}|/2\ell.$

Similarly, let $Y_{b}^{+}=\\{c\in C_{s}:vw\in
P_{B_{j}C_{s}}^{\alpha}\cap\gamma_{u}^{+}\\}$. Because $P_{js}^{\alpha}$
satisfies $\textnormal{disc}_{2}(\epsilon_{2}^{\prime}(\ell),1/\ell)$, Lemma
2.18 implies that $P_{B_{j}C_{s}}^{\gamma}$ satisfies
$\textnormal{disc}_{2}(\epsilon_{2}(\ell),1/\ell)$. Thus, there is a set
$B^{\prime\prime}_{j}\subseteq B_{j}$ of size at least
$(1-\sqrt{\epsilon_{2}(\ell)})|B_{j}|$ so that for all $v\in
B_{j}^{\prime\prime}$,
$|Y_{b}^{+}|=\frac{|C_{s}|}{\ell}(1\pm\sqrt{\epsilon_{2}(\ell)})\geq\epsilon_{1}|V_{s}|/2\ell$.
Combining the above with the fact that $B_{j}$ is non-trivial, we have

$|B_{j}^{\prime\prime}\cap
B_{j}^{\prime}|\geq(1-2\sqrt{\epsilon_{2}(\ell)})|B_{j}|\geq\epsilon_{1}^{2}|V_{j}|/2.$

Now given $b\in B_{j}^{\prime}\cap B_{j}^{\prime\prime}$, since
$|X^{-}_{b}|\geq\frac{1}{2\ell}|A_{i}|\geq\frac{\epsilon_{1}}{2\ell}|V_{i}|$
and
$|Y^{+}_{b}|\geq\frac{\epsilon_{1}^{2}}{2\ell}|C_{s}|\geq\frac{\epsilon_{1}^{3}}{2\ell}|V_{s}|$,
and since $P_{is}^{\beta}$ satisfies
$\textnormal{disc}_{2}(\epsilon_{2}^{\prime}(\ell),1/\ell)$, we must have that
$P_{is}^{\beta}[X^{-}_{b},Y^{+}_{b}]\geq\frac{|X_{b}||Y_{b}|}{2\ell}$. Note
that for all $ac\in P_{is}^{\beta}[X_{b},Y_{b}]$, $bac\in K_{3}^{(2)}(G_{1})$.
Thus we have shown

$|K_{3}^{(2)}(G_{1})|\geq|B_{j}^{\prime}\cap
B_{j}^{\prime\prime}|\frac{\epsilon_{1}|V_{s}|}{2\ell}\frac{\epsilon_{1}|V_{i}|}{2\ell}\geq\epsilon_{1}^{4}|V_{i}||V_{j}||V_{s}|/4\ell^{2}.$

Since $\epsilon_{1}^{\prime}\ll\epsilon_{1}$, this contradicts that
$|K_{3}^{(2)}(G_{1})|\leq 2\epsilon_{1}^{\prime}\frac{n^{3}}{\ell^{3}t^{3}}$.
This finishes the proof. ∎

##  6\. Binary $\textnormal{disc}_{2,3}$-error

In this section, we switch gears and consider binary error. First, in Section
6.1, we will give several examples of properties which admit binary
$\textnormal{disc}_{2,3}$-error but contain $\overline{U}(k)$ for all $k$.
These examples will be used to prove Proposition 1.65, which says that there
exist properties which are far from WNIP but which admit
$\textnormal{disc}_{2,3}$-error. We will also show in Section 6.2, that both
$\mathcal{H}_{\textnormal{HP}}$ and $\mathcal{H}_{\textnormal{GS}_{p}}$ have
finite VC-dimension. This implies, by Proposition 1.51, that to show
$\mathcal{H}_{\textnormal{HP}}$ and $\mathcal{H}_{\textnormal{GS}_{p}}$
require non-binary $\textnormal{disc}_{2,3}$-error, it suffices to show that
they both require non-binary $\textnormal{vdisc}_{3}$-error.

The rest of the section will then be concerned with showing that
$\mathcal{H}_{\textnormal{HP}}$ and $\mathcal{H}_{\textnormal{GS}_{p}}$
require non-binary $\textnormal{vdisc}_{3}$-error. There are two ways one
could do this. The most straightforward option is to present separate proofs
for each. However, the proofs are so similar that this becomes quite
repetitive. The second option is to isolate the important commonalities
between the two examples, and then give a unified proof for both at once.
Although it is a bit more work, we have chosen the second option, as we think
it is of independent interest to know this can be done. Thus, in Section 6.3
we make a general definition, namely that of a
$(p,\mu,\tau,\alpha,\rho)$-special $3$-graph (see Definition 6.25). Roughly
speaking, this is a $3$-partite $3$-graph equipped with a metric on each of
its parts, and which satisfies certain axioms relating the edge relation and
the metric structure. We will show that both $\textnormal{HP}(N)$ and
$\textnormal{GS}_{p}(n)$ are $(p,\mu,\tau,\alpha,\rho)$-special, for
appropriately chosen parameters.

In Section 6.4, we show that any $\textnormal{vdisc}_{3}$-regular partition of
a sufficiently large $(p,\mu,\tau,\alpha,\rho)$-special $3$-graph requires
non-binary $\textnormal{vdisc}_{3}$-error (see Theorem 6.28). From this we
will deduce Theorems 1.60 and 1.63. We will end the section with a proof of
Theorem 1.22.

###  6.1. Admitting binary $\textnormal{disc}_{2,3}$-error is distinct from
admitting zero $\textnormal{vdisc}_{3}$-error

In this section we give a class of examples admitting binary
$\textnormal{disc}_{2,3}$-error. We will use these examples to show that
admitting binary $\textnormal{disc}_{2,3}$-error is distinct from admitting
zero $\textnormal{vdisc}_{3}$-error, and that there exist properties far from
WNIP which still admit binary $\textnormal{disc}_{2,3}$-error. The idea behind
these examples is that if a property is “essentially binary” (in the sense of
Definition 6.1 below), then it admits binary $\textnormal{disc}_{2,3}$-error.

######  Definition 6.1.

Suppose $G=(V\cup U\cup W,E)$ is a finite $3$-partite, $3$-graph. We say that
$G$ is _$\ell$ -binary_ if the following holds. There are partitions
$\mathcal{P}_{UV}$ of $K_{2}(U,V)$, $\mathcal{P}_{UW}$ of $K_{2}(U,W)$, and
$\mathcal{P}_{VW}$ of $K_{2}(V,W)$, such that

  * •

$|\mathcal{P}_{UV}|,|\mathcal{P}_{UW}|,|\mathcal{P}_{VW}|\leq\ell$,

  * •

for all
$(\alpha,\beta,\gamma)\in\mathcal{P}_{UV}\times\mathcal{P}_{UW}\times\mathcal{P}_{VW}$,
if $G_{\alpha,\beta,\gamma}=(V\cup U\cup W,\alpha\cup\beta\cup\gamma)$, then
either $K_{3}^{(2)}(G_{\alpha,\beta,\gamma})\subseteq E$ or
$K_{3}^{(2)}(G_{\alpha,\beta,\gamma})\cap E=\emptyset$.

Here are some examples of $\ell$-binary $3$-graphs.

  * •

Given $n$, let $A_{n}=\\{a_{1},\ldots,a_{n}\\}$,
$B_{n}=\\{b_{1},\ldots,b_{n}\\}$, and $C_{n}=\\{c_{1},\ldots,c_{n}\\}$. Then
$G=(A_{n}\cup B_{n}\cup C_{n},\\{a_{i}b_{j}c_{k}:i<j<k\\})$ is $2$-binary.
Indeed, set

$\mathcal{P}_{AB}=\\{\\{a_{i}b_{j}:i<j\\},\\{a_{i}b_{j}:i\geq j\\}\\},$

and define $\mathcal{P}_{BC}$ and $\mathcal{P}_{AC}$ analogously.

  * •

For any $3$-partite graph $G=(V\cup U\cup W,E)$, the hypergraph with vertex
set $V\cup U\cup W$ and edge set $\\{(x,y,z)\in VUW:xyz\text{ is a triangle in
$G$}\\}$ is $2$-binary. Indeed, define

$\mathcal{P}_{UV}=\\{E\cap K_{2}(U,V),K_{2}(U,V)\setminus E\\},$

and define $\mathcal{P}_{UW}$ and $\mathcal{P}_{VW}$ analogously.

We now show that $\ell$-binary hypergraphs admit
$\textnormal{disc}_{2,3}$-regular decompositions with binary
$\textnormal{disc}_{2,3}$-error.

######  Proposition 6.2.

For all $\epsilon_{1}>0$, $\epsilon_{2}:\mathbb{N}\rightarrow(0,1]$ and
$\ell\geq 1$, there is $n_{0}$ and $T,L,N$ such that the following holds. If
$G=(V\cup U\cup W,E)$ is an $\ell$-binary, $3$-partite, $3$-uniform hypergraph
with $|U\cup V\cup W|=n\geq N$, then there is $t_{0}\leq t\leq T$ and
$\ell^{\prime}\leq L$ such that $G$ has an
$(\epsilon_{1},\epsilon_{2}(\ell^{\prime}))$-regular
$(t,\ell,\epsilon_{2}(\ell^{\prime}),\epsilon_{1})$-decomposition with binary
$\textnormal{disc}_{2,3}$-error.

###### Proof.

Fix $\epsilon_{1}>0$, $\epsilon_{2}:\mathbb{N}\rightarrow(0,1]$ and $\ell\geq
1$. Choose $\epsilon_{1}^{\prime}\ll\mu_{1}\ll\epsilon_{1}$, and
$\epsilon_{2}^{\prime},\mu:\mathbb{N}\rightarrow(0,1]$ with the property that
$\epsilon_{2}^{\prime}(x)\ll\mu_{2}(x)\ll\epsilon_{2}(x)$ for all $x\geq 1$.
Choose $f$ and $g$ as in Lemma 2.27 for $\epsilon_{1}^{\prime}$ and
$\epsilon_{2}^{\prime}$. Then set $L=f(3,\ell,3,1)$, $T=f(3,\ell,3,1)$, and
let $N_{1}=N_{1}(3,\ell,3,1)$ from Lemma 2.27. Finally, choose some $N\gg
N_{1},(\epsilon_{1}^{\prime})^{-1},\epsilon_{2}^{\prime}(L)^{-1}$.

Now suppose $H=(V\cup U\cup W,E)$ is a $3$-partite $3$-graph which is
$\ell$-binary, and where $|U\cup W\cup V|=n\geq N$. Choose partitions
$K_{2}[U,V]=\bigcup_{\alpha\leq\ell_{UV}}P^{UV}_{\alpha}$,
$K_{2}[U,W]=\bigcup_{\alpha\leq\ell_{UW}}P^{UW}_{\alpha}$, and
$K_{2}[V,W]=\bigcup_{\alpha\leq\ell_{VW}}P^{VW}_{\alpha}$, with
$\ell_{UV},\ell_{UW},\ell_{VW}\leq\ell$ witnessing that $G$ is $\ell$-binary.
Note that each triple $(P^{UV}_{\alpha},P^{UW}_{\beta},P^{VW}_{\gamma})$ comes
equipped with a $\delta=\delta(\alpha,\beta,\gamma)\in\\{0,1\\}$ so that
$K_{3}^{(2)}(U\cup V\cup W,P^{UV}_{\alpha}\cup P^{UW}_{\beta}\cup
P^{VW}_{\gamma})\subseteq E^{\delta}$.

Let $\mathcal{P}$ be the $(3,\ell)$-decomposition of $V$ with
$\mathcal{P}_{vert}=\\{U,V,W\\}$ and
$P_{edge}=\\{P^{XY}_{\alpha}:XY\in\\{UV,UW,VW\\},\alpha\leq\ell_{XY}\\}$. Let
$\mathcal{Q}$ be the $(3,1)$ decomposition of $V$ consisting of
$\mathcal{Q}_{vert}=\\{U,V,W\\}$ and
$\mathcal{Q}_{edge}=\\{K_{2}[U,V],K_{2}[V,W],K_{2}[U,W]\\}$. Apply Lemma 2.27
to $\mathcal{P}$ and $\mathcal{Q}$ to obtain $\ell^{\prime}\leq L$, $t\leq T$,
and a
$(t,\ell^{\prime},\epsilon_{1}^{\prime},\epsilon^{\prime}_{2}(\ell^{\prime}))$-decomposition
$\mathcal{R}$ of $V$, which has no $\textnormal{disc}_{2}$-irregular triads
and which is an
$(\epsilon_{1}^{\prime},\epsilon_{2}^{\prime}(\ell^{\prime}))$-approximate
refinement of $\mathcal{P}$. Let $\Sigma\subseteq{\mathcal{R}_{vert}\choose
2}$ be as in the definition of an
$(\epsilon_{1}^{\prime},\epsilon_{2}^{\prime}(\ell^{\prime}))$-approximate
refinement of $\mathcal{P}$. Let $\mathcal{R}_{vert}=\\{V_{1},\ldots,V_{t}\\}$
and $\mathcal{R}_{edge}=\\{R_{ij}^{\alpha}:ij\in{[t]\choose
2},\alpha\leq\ell^{\prime}\\}$.

Suppose $R^{\alpha}_{ij},R^{\beta}_{ik},R^{\gamma}_{jk}\in\mathcal{R}_{edge}$
are such that $V_{i}V_{j},V_{j}V_{k},V_{i}V_{k}\notin\Sigma$. Let
$R_{ijk}^{\alpha,\beta,\gamma}$ denote the triad $(V_{i}\cup V_{j}\cup
V_{k},R^{\alpha}_{ij}\cup R^{\beta}_{ik}\cup R^{\gamma}_{jk})$. By definition
of an $(\epsilon_{1}^{\prime},\epsilon_{2}^{\prime}(\ell^{\prime}))$
refinement, there are $X,Y,Z\in\\{U,V,W\\}$ with $|V_{i}\setminus
X|<\epsilon_{1}^{\prime}|V_{i}|$, $|V_{j}\setminus
Y|<\epsilon_{1}^{\prime}|V_{j}|$, and $|V_{k}\setminus
Z|<\epsilon_{1}^{\prime}|V_{k}|$. If $X=Y$, $X=Z$, or $Y=Z$, then $|E\cap
K_{3}^{(2)}(R_{ijk}^{\alpha,\beta,\gamma})|=0$. By Proposition 2.22,
$R_{ijk}^{\alpha,\beta,\gamma}$ satisfies
$\textnormal{disc}_{2,3}(\epsilon_{1},\epsilon_{2}(\ell^{\prime}))$ with
respect to $H$.

Assume now that $X,Y,Z$ are pairwise distinct. Then by definition of an
$(\epsilon_{1}^{\prime},\epsilon_{2}^{\prime}(\ell^{\prime}))$-approximate
refinement, there are $\alpha^{\prime},\beta^{\prime},\gamma^{\prime}$ so that
the following hold (possibly after relabeling),

$|R^{\alpha}_{ij}\setminus
P_{\alpha^{\prime}}^{UV}|<\epsilon^{\prime}_{1}|R^{\alpha}_{ij}|,\text{
}|R^{\beta}_{ik}\setminus
P_{\beta^{\prime}}^{UW}|<\epsilon^{\prime}_{1}|R^{\beta}_{ik}|,\text{ and
}|R^{\gamma}_{jk}\setminus
P_{\gamma^{\prime}}^{VW}|<\epsilon_{1}^{\prime}|R^{\gamma}_{jk}|,$

and further, each of $R^{\alpha}_{ij}\setminus P_{\alpha^{\prime}}^{UV}$,
$R^{\beta}_{ik}\setminus P_{\beta^{\prime}}^{UW}$, and
$R^{\gamma}_{jk}\setminus P_{\gamma^{\prime}}^{VW}$ have
$\textnormal{disc}_{2}(\epsilon^{\prime}_{2}(\ell^{\prime}))$. By Corollary
2.6,
$K_{3}^{(2)}(R_{ijk}^{\alpha,\beta,\gamma})=(1\pm\mu_{2}(\ell^{\prime}))\frac{|V_{i}||V_{j}||V_{k}|}{(\ell^{\prime})^{3}}$,
and the number of triples in $K_{3}^{(2)}(R_{ijk}^{\alpha,\beta,\gamma})$
involving a pair from one of $R^{\alpha}_{ij}\setminus
P_{\alpha^{\prime}}^{UV}$, $R^{\beta}_{ik}\setminus P_{\beta^{\prime}}^{UW}$,
or $R^{\gamma}_{jk}\setminus P_{\gamma^{\prime}}^{VW}$ is at most

$3\epsilon_{1}^{\prime}(1+\mu_{2}(\ell^{\prime}))\frac{1}{(\ell^{\prime})^{3}}|V_{i}||V_{j}||V_{k}|\leq
4\mu_{1}|K_{3}^{(2)}(R_{ijk}^{\alpha,\beta,\gamma})|.$

Thus, if $\delta=\delta(\alpha^{\prime},\beta^{\prime},\gamma^{\prime})$, then

$|E^{\delta}\cap
K_{3}^{(2)}(R_{ijk}^{\alpha,\beta,\gamma})|\geq(1-4\mu_{1})|K_{3}^{(2)}(R_{ijk}^{\alpha,\beta,\gamma})|.$

By Proposition 2.22, this shows $R_{ijk}^{\alpha,\beta,\gamma}$ has
$\textnormal{disc}_{2,3}(\epsilon_{1},\epsilon_{2}(\ell^{\prime}))$ with
respect to $H$. By definition, this shows that $\mathcal{R}$ has binary
$\textnormal{disc}_{2,3}$-error with respect to $H$. ∎

As a consequence we can now show that many examples admit binary
$\textnormal{disc}_{2,3}$-error. In particular, we can now prove Propopistion
1.65, which shows that there is a property containing $\overline{U}(k)$ for
every $k$ and which admits binary $\textnormal{disc}_{2,3}$-error. Recall that
given an infinite $3$-graph $H$, $\text{age}(H)$ denotes the class of all
finite $3$-graphs which are isomorphic to an induced sub-$3$-graph of $H$. It
is easy to see that $\text{age}(H)$ is always a hereditary $3$-graph property.

######  Definition 6.3.

Define $\mathcal{W}$ to be the $3$-graph

$\mathcal{W}=(\\{a_{i},b_{i}:i\in\mathbb{N}\\}\cup\\{c_{S}:S\subseteq\mathbb{N}\\},\\{(a_{i},b_{j},c_{S}):j\in
S\\}).$

Let $\mathcal{H}_{\mathcal{W}}:=\text{age}(\mathcal{W})$.

Proof of Proposition 1.65: Clearly every element in
$\mathcal{H}_{\mathcal{W}}$ is $2$-binary. Consequently, by Proposition 6.2,
$\mathcal{H}_{\mathcal{W}}$ admits binary $\textnormal{disc}_{2,3}$-error. On
the other hand, $\mathcal{H}_{\mathcal{W}}$ contains
$\overline{U}(k)\in\mathcal{W}$ for all $k$ by definition. ∎

We can use $\mathcal{H}_{\mathcal{W}}$ as an example to demonstrate several
other distinctions among the definitions from the introduction. Recall that in
Corollary 1.52, we showed that a property $\mathcal{H}$ admitting binary
$\textnormal{vdisc}_{3}$-error must be $\textnormal{vdisc}_{3}$-homogeneous.
For a property $\mathcal{H}$ to be $\textnormal{vdisc}_{3}$-homogeneous, by
Theorem 1.35, there must be a $k\geq 1$ such that
$\overline{U}(k)\notin\text{Trip}(\mathcal{H})$. Consequently,
$\mathcal{H}_{\mathcal{W}}$ does not admit binary
$\textnormal{vdisc}_{3}$-error, but does admit binary
$\textnormal{disc}_{2,3}$-error. Moreover, $\mathcal{H}_{\mathcal{W}}$ has
unbounded weak VC-dimension (which implies unbounded VC-dimension) and is not
weakly stable (and thus not stable). Thus $\mathcal{H}_{\mathcal{W}}$ shows
that admitting binary $\textnormal{disc}_{2,3}$-error is distinct from
admitting binary $\textnormal{vdisc}_{3}$-error, from NIP, from WNIP, from
stability and from weak stability.

###  6.2. Proof of Proposition 1.64

In this section, we show that both $\mathcal{H}_{\textnormal{HP}}$ and
$\mathcal{H}_{\textnormal{GS}_{p}}$ have bounded VC-dimension, which will
allow us to apply Proposition 1.51 to both. We recall some terminology from
the study of VC-dimension.

Suppose $X$ is a set. A _set system_ is a pair $(X,\mathcal{F})$ where
$\mathcal{F}\subseteq\mathcal{P}(X)$. Given $Y\subseteq X$, define
$\mathcal{F}\cap Y:=\\{Y\cap F:F\in\mathcal{F}\\}$. We then say that
$\mathcal{F}$ _shatters $Y$_ if $|\mathcal{F}\cap Y|=2^{|Y|}$.

######  Definition 6.4.

The _VC-dimension of $(X,\mathcal{F})$_, $\textnormal{VC}(X,\mathcal{F})$, is
the largest size of a shattered subset of $X$.

Note that given a $3$-graph $H=(V,E)$, by definition,

$\displaystyle\textnormal{VC}(H)=\max\Big{\\{}\textnormal{VC}\Big{(}V,\Big{\\{}N_{H}(ab):ab\in{V\choose
2}\Big{\\}}\Big{)},\textnormal{VC}\Big{(}{V\choose 2},\\{N_{H}(a):a\in
V\\}\Big{)}\Big{\\}}.$

We will now show that $\mathcal{H}_{\textnormal{GS}_{p}}$ has bounded VC-
dimension. The key ingredient is a fact proved in [54].

######  Theorem 6.5.

For all $p\geq 3$, the set system
$\mathcal{F}_{\textnormal{GS}_{p}}=(\mathbb{F}_{p}^{n},\\{A(p,n)-g:g\in\mathbb{F}_{p}^{n}\\})$
has VC-dimension $3$.

######  Corollary 6.6.

For all $p\geq 3$, $\mathcal{H}_{\textnormal{GS}_{p}}$ has VC-dimension $3$.

###### Proof.

Fix $p\geq 3$. We show $\mathcal{H}_{\textnormal{GS}_{p}}$ has VC-dimension at
most $3$. Suppose towards a contradiction there is
$G=(V,E)\in\mathcal{H}_{\textnormal{GS}_{p}}$ with VC-dimension at least $4$.
By definition of $\mathcal{H}_{\textnormal{GS}_{p}}$ there is $n\geq 1$ such
that $G$ is isomorphic to an induced sub-$3$-graph of
$\textnormal{GS}_{p}(n)$. Thus, $\textnormal{GS}_{p}(n)$ also has VC-dimension
at least $4$. Let $A=\\{a_{g}:g\in\mathbb{F}_{p}^{n}\\}$,
$B=\\{b_{g}:g\in\mathbb{F}_{p}^{n}\\}$,
$C=\\{c_{g}:g\in\mathbb{F}_{p}^{n}\\}$. Then $\textnormal{GS}_{p}(n)$ has
vertex set $V^{\prime}=A\cup B\cup C$ and edge set
$E^{\prime}=\\{a_{g}b_{g^{\prime}}c_{g^{\prime\prime}}:g+g^{\prime}+g^{\prime\prime}\in
A(n,p)\\}$. Since $\textnormal{VC}(\textnormal{GS}_{p}(n))\geq 4$, by
definition, one of the following hold.

  1. (1)

There is $X\subseteq V^{\prime}$ a set of size $4$, and for each $Y\subseteq
X$, $e_{Y}\in{V^{\prime}\choose 2}$ such that for all $x\in X$, $\\{x\\}\cup
e_{Y}\in E^{\prime}$ holds if and only if $x\in Y$.

  2. (2)

There is $X\subseteq{V^{\prime}\choose 2}$ of size $4$ and for each
$Y\subseteq X$, $v_{Y}\in A\cup B\cup C$ such that for all $e\in X$,
$\\{v_{Y}\\}\cup e\in E^{\prime}$ if and only if $e\in Y$.

Suppose first we are in case (1). Because there exists $e\in{V^{\prime}\choose
2}$ with $X=N(e)\cap X$, we must have that either $X\subseteq A$, $X\subseteq
B$, or $X\subseteq C$. Without loss of generality, let us assume $X\subseteq
A$. Say $X=\\{a_{x},a_{y},a_{z},a_{w}\\}$. By definition of
$\textnormal{GS}_{p}(n)$, for any $\emptyset\neq Y\subseteq X$, since
$N(e_{Y})\cap X\neq\emptyset$, must have that $e_{Y}=b_{g_{Y}}c_{h_{Y}}$ for
some $g_{Y},h_{Y}\in\mathbb{F}_{p}^{n}$. But then $\\{x,y,z,w\\}$ is shattered
by $\mathcal{F}_{\textnormal{GS}_{p}}$, contradicting Theorem 6.5.

Suppose now we are in case (2). Because there is some $v\in V$ such that
$X\cap N(v)=X$, we must have that either $X\subseteq AB$, $X\subseteq AC$ or
$X\subseteq BC$. Without loss of generality, assume $X\subseteq AB$, say
$X=\\{a_{g_{1}}b_{h_{1}},\ldots,a_{g_{4}}b_{h_{4}}\\}$. Note that for any
$\emptyset\neq Y\subseteq X$, since $N(e_{Y})\cap X^{\prime}\neq\emptyset$, we
must have that $v_{Y}=c_{\nu_{Y}}$ for some $\nu_{Y}\in\mathbb{F}_{p}^{n}$.
Again, we see that $\\{g_{1}+h_{1},\ldots,g_{4}+h_{4}\\}$ is shattered by
$\mathcal{F}_{\textnormal{GS}_{p}}$, contradicting Theorem 6.5.

On the other hand, by Theorem 6.5, there is set $X\subseteq\mathbb{F}_{p}^{n}$
of size $4$ shattered by $\mathcal{F}_{\textnormal{GS}_{p}}$. Say
$X=\\{g_{1},\ldots,g_{4}\\}$. It is easy to see
$\\{b_{0}c_{g_{1}},\ldots,b_{0}c_{g_{4}}\\}$ is shattered in
$(V,\\{N_{\textnormal{GS}_{p}(n)}(a):a\in A\\})$, and thus
$\mathcal{H}_{\textnormal{GS}_{p}(n)}$ has VC-dimension at least $3$. ∎

We now turn to showing that $\mathcal{H}_{\textnormal{HP}}$ has bounded VC-
dimension. This will be clear to the model theorist, as the edge relation of
$\mathcal{H}_{\textnormal{HP}}$ is uniformly definable in Presburger
arithmetic, for instance. On the other hand, this fact will also be known to
many combinatorialists, as the $3$-graphs of $\mathcal{H}_{\textnormal{HP}}$
are examples of semialgebraic hypergraphs (see e.g. [4]), which are well known
to have bounded VC-dimension. However, we include a proof here for the sake of
completeness.

######  Fact 6.7.

$\mathcal{H}_{\textnormal{HP}}$ has VC-dimension $1$.

###### Proof.

By definition of $\mathcal{H}_{\textnormal{HP}}$, it suffices to show that
$\textnormal{VC}(\textnormal{HP}(N))\leq 1$ for all $N$. Fix $N\geq 1$, and
consider the $3$-graph $\textnormal{HP}(N)=(V,E)$ where $V=A\cup B\cup C$,
$A=\\{a_{i}:i\in[N]\\}$, $B=\\{b_{i}:i\in[N]\\}$, $C=\\{c_{i}:i\in[N]\\}$, and
$E=\\{a_{i}b_{j}c_{k}:i+j+k\geq N+2\\}$. Suppose towards a contradiction that
$\textnormal{HP}(N)$ has VC-dimension as least $2$. This means there is either
a set $X\subseteq V$ of size $2$ shattered in $(V,\mathcal{F}_{1})$ where
$\mathcal{F}_{1}=\\{N_{\textnormal{HP}(N)}(uv):uv\in{V\choose 2}\\}$, or a
there is a set $X\subseteq{V\choose 2}$ of size $2$ shattered $({V\choose
2},\mathcal{F}_{2})$, where $\mathcal{F}_{2}=\\{N_{\textnormal{HP}(N)}(u):u\in
V\\}$.

Suppose first there is $X\subseteq{V\choose 2}$ of size $2$ shattered in
$({V\choose 2},\mathcal{F}_{1})$. Arguing as in in the proof of Corollary 6.6,
it is not difficult to show that because $\textnormal{HP}(N)$ is $3$-partite,
$X\subseteq K_{2}[A,B]$, or $X\subseteq K_{2}[A,C]$, or $X\subseteq
K_{2}[B,C]$. Since $A$, $B$, and $C$ behave symmetrically in
$\textnormal{HP}(N)$, let us assume that $X\subseteq K_{2}[A,B]$. Say
$X=\\{a_{i_{1}}b_{j_{1}},a_{i_{2}}b_{j_{2}}\\}$. By relabeling if necessary,
assume $i_{1}+j_{1}\leq i_{2}+j_{2}$. It is not difficult to see that because
$X$ is shattered in $\textnormal{HP}(N)$, there is some $c_{k}\in C$ so that
$c_{k}a_{i_{1}}b_{j_{1}}\in E$ but $c_{k}a_{i_{2}}b_{i_{2}}\notin E$. But this
means that $i_{1}+j_{1}+k\geq N+2$ while $i_{2}+j_{2}+k<N+2$, which is not
possible, as $i_{1}+j_{1}\leq i_{2}+j_{2}$.

Suppose now that there is $X\subseteq V$ of size $2$ shattered
$(V,\mathcal{F}_{2})$. Again, it is not hard to see that since
$\textnormal{HP}(N)$ is $3$-partite, we must have $X\subseteq A$, $X\subseteq
B$, or $X\subseteq C$. As the roles of $A,B,C$ are symmetric, we may assume,
say, $X=\\{a_{i_{1}},a_{i_{2}}\\}\subseteq A$, where $i_{1}\leq i_{2}$. Since
$X$ is shattered, there is some $b_{j}c_{k}$ so that $b_{j}c_{k}a_{i_{1}}\in
E$ but $b_{j}c_{k}a_{i_{2}}\notin A$. But this means $j+k+i_{1}\geq N+2$ while
$j+k+i_{2}<N+2$, which is not possible, as $i_{1}\leq i_{2}$. ∎

###  6.3. Special $3$-graphs and the proof Theorems 1.60 and 1.63

In this subsection we define $(p,\mu,\tau,\alpha,\rho)$-special $3$-graphs
(see Definition 6.25). The purpose of Definition 6.25 is to isolate common
properties our main examples, $\textnormal{GS}_{p}(n)$ and
$\textnormal{HP}(n)$, specifically those which are required to prove both
examples require non-binary $\textnormal{vdisc}_{3}$-error. The main idea is
that both examples come equipped with natural metrics on their set of
vertices, which interact nicely with their edge sets. As Definition 6.25 is
quite technical, we will begin by examining each of the two examples in turn
by way of motivation. We will begin with $\textnormal{GS}_{p}(n)$, where the
picture is somewhat simpler.

####  6.3.1. Special properties of $\textnormal{GS}_{p}(n)$

In this section we will go through the main properties of
$\textnormal{GS}_{p}(n)$ used in the proof that it requires non-binary
$\textnormal{vdisc}_{3}$-error. We first recall the definition of
$\textnormal{GS}_{p}(n)$, and prove some basic facts about it. Given
$x\in\mathbb{F}_{p}^{n}$ and $i\in[n]$, $x_{i}$ denotes the $i$th coordinate
of $x$. Given $1\leq i\leq n$, we let $H_{i}$ denote the subspace of
$\mathbb{F}_{p}^{n}$ with the property that for all $x\in H_{i}$, $x_{j}=0$
for all $1\leq j\leq i$. By convention, we set $H_{0}=\mathbb{F}_{p}^{n}$.

Recall that $A(p,n)=\bigcup_{i=1}^{n}H_{i}+e^{i}$, where $e^{i}$ is the $i$th
standard basis vector in $\mathbb{F}_{p}^{n}$. In other words, a vector
$x\in\mathbb{F}_{p}^{n}$ is in $A(p,n)$ if the first non-zero coordinate in
$x$ is $1$. Then $\textnormal{GS}_{p}(n)$ is defined as follows.

$\textnormal{GS}_{p}(n)=(\\{a_{g},b_{g},c_{g}:g\in\mathbb{F}_{p}^{n}\\},\\{a_{g}b_{g^{\prime}}c_{g^{\prime\prime}}:g+g^{\prime}+g^{\prime\prime}\in
A(p,n)\\}).$

To ease notation, while in Section 6.3.1, we will let
$A=\\{a_{g}:g\in\mathbb{F}_{p}^{n}\\}$,
$B=\\{b_{g}:g\in\mathbb{F}_{p}^{n}\\}$,
$C=\\{c_{g}:g\in\mathbb{F}_{p}^{n}\\}$, $E=E(\textnormal{GS}_{p}(n))$, and
$N=p^{n}$. Give $x,y\in\mathbb{F}_{p}^{n}$ we set

$\lambda(x,y)=\max\\{i\in\\{0,\ldots,n\\}:\text{ $x$ and $y$ are in the same
coset of $H_{i}$}\\}.$

Note that by definition, $x_{\lambda(x,y)+1}\neq y_{\lambda(x,y)+1}$ and for
all $1\leq j\leq\lambda(x,y)$, $y_{j}=x_{j}$.

######  Lemma 6.8.

Given $x,y\in\mathbb{F}_{p}^{n}$, set $d(x,y)=0$ if $x=y$ and set
$d(x,y)=p^{-\lambda(x,y)}$ if $x\neq y$. Then $d$ is an ultra metric on
$\mathbb{F}_{p}^{n}$, with distances in $[0,1]$, and for all
$x\in\mathbb{F}_{p}^{n}$, $B_{p^{-i}}(x)$ is the coset of $H_{i+2}$ containing
$x$.

###### Proof.

If $x\neq y$, then $x$ and $y$ are in different cosets of $H_{n}$, so
$d(x,y)\geq p^{-n}>0$. Given $x\in\mathbb{F}_{p}^{n}$, it is clear that
$d(x,y)=p^{-i}$ if and only $y$ is in the same coset of $H_{i}$ as $x$, but
not the same coset of $H_{i+1}$. Thus
$B_{p^{-i}}(x)=\\{y\in\mathbb{F}_{p}^{n}:d(x,y)<p^{-i}\\}$ is the coset of
$H_{i+2}$ containing $x$. This shows that $d(x,y)=d(y,x)$ for all
$x,y\in\mathbb{F}_{p}^{n}$ and $d(x,y)=0$ if and only if $x=y$.

Consider $x,y,z\in\mathbb{F}_{p}^{n}$. Suppose $d(x,y)=p^{-i}$, so $x$, $y$
are in the same coset of $H_{i}$, say $H_{i}+g$, but not the same coset of
$H_{i+1}$, say $x\in H_{i+1}+g+g^{\prime}$ and $y\in
H_{i+1}+g+g^{\prime\prime}$. If $z\notin H_{i}+g$, then
$d(x,z)=d(y,z)=p^{-i-1}=pd(x,y)$. If $z\in H_{i}+g$, then it cannot be in both
$H_{i+1}+g+g^{\prime}$ and $H_{i+1}+g+g^{\prime}$, so
$\max\\{d(z,x),d(z,y)\\}=p^{-i}=d(\bar{x},\bar{y})$. This shows
$d(x,y)\leq\max\\{d(x,z),d(y,z)\\}$, and thus $d$ is an ultrametric. ∎

The fact that $d$ is an ultrametric on $\mathbb{F}_{p}^{n}$ makes things
particularly easy to analyze in $\textnormal{GS}_{p}(n)$. For example, for any
$r\in(0,1]$ and $x\in\mathbb{F}_{p}^{n}$, $|B_{r}(x)|=|H_{m+1}|=p^{-m-1}N$,
where $m=\max\\{i\leq n:r\leq p^{-i}\\}=\lceil\log_{p}(r^{-1})\rceil$. Thus
every ball of radius $r$ contains the same number of points, and
$p^{-1}rN\leq|B_{r}(x)|\leq prN$. It is also very simple to partition balls
into smaller ones, as our next claim shows.

######  Claim 6.9 (Balls can be partitioned).

For any $x\in\mathbb{F}_{p}^{n}$ and $0<r_{1}<r_{2}\leq 1$, there is a
partition of $B_{r_{2}}(x)$ into at most $pr_{2}r_{1}^{-1}$ disjoint open
balls of radius $r_{1}$, one of which is centered at $x$.

###### Proof.

Let $m_{1}=\lceil\log_{p}(r_{1}^{-1})\rceil$,
$m_{2}=\lceil\log_{p}(r_{2}^{-1})\rceil$. Then $B_{r_{2}}(x)$ is the coset
$H_{m_{2}+2}+g$ which contains $x$. We then partition $H_{m_{2}+2}+g$ into
cosets of $H_{m_{1}+2}$. All of these cosets are balls of radius $r_{1}$, and
one of them must contain $x$. We can easily compute that the number of balls
in this partition is $p^{m_{1}-m_{2}}\leq pr_{2}r_{1}^{-1}$. ∎

Another nice feature of $\textnormal{GS}_{p}(n)$ is that it is vertex regular
(i.e. all of its vertices have the same degree).

######  Claim 6.10 ($\textnormal{GS}_{p}(n)$ is vertex regular).

For all $u,v\in A\cup B\cup C$, $|N(v)|=|N(u)|=N^{2}(\frac{1}{p-1}\pm
p^{-n})$.

###### Proof.

Given $a_{g},b_{g^{\prime}}\in\textnormal{GS}_{p}(n)$, the neighborhood of
$a_{g}b_{g^{\prime}}$ is

$N(a_{g}b_{g^{\prime}})=\\{c_{g^{\prime\prime}}:g^{\prime\prime}\in
A(p,n)-g-g^{\prime}\\}.$

Clearly $|N(a_{g}b_{g^{\prime}})|=|A(n,p)|$. Observe that

$|A(p,n)|=\sum_{i=1}^{n}|H_{i}|=\sum_{i=1}^{n}p^{n-i}=N\sum_{i=1}^{n}p^{-i}=N(\frac{1}{p-1}-\frac{p^{-n}}{p-1})\geq\frac{1}{p-1}p^{n}-\frac{1}{p-1}.$

Thus
$\frac{1}{p-1}p^{n}-1\leq|A(n,p)|=|N(a_{g}b_{g^{\prime}})|\leq\frac{1}{p-1}p^{n}$.
Then for any $a_{g}$, we compute the size of its neighborhood as
$|N(a_{g})|=\sum_{g^{\prime}\in\mathbb{F}_{p}^{n}}N(a_{g}b_{g^{\prime}})=p^{n}|A(n,p)|$.
Clearly any $b_{g}$ or $c_{g}$ has the same degree. ∎

It is also important to note that we showed in Claim 6.10 that the degree of
every vertex has the form $\alpha N^{2}$ for some $\alpha$ bounded away from
$0$ and $1$ (e.g. $\alpha=1/2p$ would work). We now consider some important
interactions between the metric and hypergraph structure. Equip each of the
sets $A,B,C$ with the natural metrics coming Lemma 6.8 (i.e. for
$g,g^{\prime}\in\mathbb{F}_{p}^{n}$, set
$d(b_{g},b_{g^{\prime}})=d(c_{g},c_{g^{\prime}})=d(a_{g},a_{g^{\prime}})=d(g,g^{\prime})$).
In our next claim, we use the vertex-regularity in $\textnormal{GS}_{p}(n)$ to
show that given open balls $B_{1}\subseteq A$ and $B_{2}\subseteq B$, there
are many edges and nonedges in $K_{3}[B_{1},B_{2},C]$. This can be thought of
as a beefed-up version of the fact that for every $a_{g}b_{g^{\prime}}$,
$N(a_{g}b_{g^{\prime}})$ and $\neg N(a_{g}b_{g^{\prime}})$ are large (see
Claim 6.10).

######  Claim 6.11.

For all $a_{g}\in A$, $b_{g^{\prime}}\in B$, and $r\in(0,1]$, there are
$f_{0}(r,g,g^{\prime}),f_{1}(r,g,g^{\prime})\in\mathbb{F}_{p}^{n}$ such that

$\displaystyle
K_{3}[B_{r}(a_{g}),B_{r}(b_{g^{\prime}}),B_{r}(c_{f_{1}(r,g,g^{\prime})})]$
$\displaystyle\subseteq E\text{ and
}K_{3}[B_{r}(a_{g}),B_{r}(b_{g^{\prime}}),B_{r}(c_{f_{0}(r,g,g^{\prime})})]\cap
E$ $\displaystyle=\emptyset.$

###### Proof.

Set $m=\lceil\log_{p}(r^{-1})\rceil$, so $B_{r}(a_{g})=B_{p^{-m}}(a_{g})$ and
$B_{r}(b_{g^{\prime}})=B_{p^{-m}}(b_{g}^{\prime})$. Let
$h,h^{\prime}\in\mathbb{F}_{p}^{n}$ be such that in $\mathbb{F}_{p}^{n}$,
$B_{p^{-m}}(g)=H_{m+1}+g$ and $B_{p^{-m}}(g^{\prime})=H_{m+1}+g^{\prime}$.
Define $s=\min\\{m,\lambda(g,g^{\prime})\\}$.

Let
$f_{0}(r,g,g^{\prime})=-\sum_{i=1}^{s+1}(g_{i}+g_{i}^{\prime})e^{i}+2e^{s+1}$
and let
$f_{1}(r,g,g^{\prime})=-\sum_{i=1}^{s+1}(g_{i}+g_{i}^{\prime})e^{i}+e^{s+1}$.
Note $H_{s+1}+g+g^{\prime}+f_{0}(g,g^{\prime})=H_{s+1}+2e^{s+1}$ is disjoint
from $A(p,n)$ and $H_{s+1}+g+g^{\prime}+f_{1}(g,g^{\prime})=H_{s+1}+e^{s+1}$
is contained in $A(p,n)$. Thus
$K_{3}[B_{r}(a_{g}),B_{r}(b_{g^{\prime}}),B_{s}(c_{f_{1}(r,g,g^{\prime})})]\subseteq
E$ and
$K_{3}[B_{r}(a_{g}),B_{r}(b_{g^{\prime}}),B_{s}(c_{f_{0}(r,g,g^{\prime})})]\cap
E=\emptyset$, as desired. Note that by construction,
$d(f_{0}(r,g,g^{\prime}),f_{1}(r,g,g^{\prime}))\geq\max\\{r,d(g,g^{\prime})\\}$.
∎

It will be important for us to know that the $f_{0}(r,g,g^{\prime})$,
$f_{1}(r,g,g^{\prime})$,
$f_{0}(r^{\prime},g^{\prime\prime},g^{\prime\prime\prime})$,
$f_{1}(r^{\prime},g^{\prime\prime},g^{\prime\prime\prime})$ in Claim 6.11 are
far apart for certain choices of
$g,g^{\prime},g^{\prime\prime},g^{\prime\prime\prime},r,r^{\prime}$.

######  Claim 6.12.

If $g^{\prime}\neq g^{\prime\prime}$, then for each $u\in\\{0,1\\}$,
$d(c_{f_{u}(r,g,g^{\prime})}),c_{f_{u}(r,g,g^{\prime\prime})})=d(b_{g^{\prime}},b_{g^{\prime\prime}})$.
Further, if $h\neq h^{\prime}$, $r^{\prime}\geq r$, and
$d(h,h^{\prime})\geq\max\\{d(g,g^{\prime}),r^{\prime}\\}$. Then

$\min\\{d(c_{f_{u}(r,g,h)},c_{f_{v}(r^{\prime},g^{\prime},h^{\prime})}):u,v\in\\{0,1\\}\geq
d(h,h^{\prime}).$

###### Proof.

Note that if $g^{\prime\prime}\neq g^{\prime}$, then

$\displaystyle\lambda(c_{f_{0}(r,g,g^{\prime})},c_{f_{0}(r,g,g^{\prime\prime})})=\lambda(-\sum_{i=1}^{s+1}(g_{i}+g_{i}^{\prime})e^{i}+2e^{s+1},-\sum_{i=1}^{s^{\prime}+1}(g_{i}+g_{i}^{\prime\prime})e^{i}+2e^{s^{\prime}+1})),$

where $s^{\prime}=\min\\{m,\lambda(g,g^{\prime\prime})\\}$. This shows
$d(c_{f_{0}(g,g^{\prime})},c_{f_{0}(g,g^{\prime\prime})})=d(b_{g^{\prime}},b_{g^{\prime\prime}})$.
A similar argument shows that
$d(c_{f_{1}(g,g^{\prime})},c_{f_{1}(g,g^{\prime\prime})})=d(b_{g^{\prime}},b_{g^{\prime\prime}})$.

Suppose now that $g\neq g^{\prime}$, $h\neq h^{\prime}$, $r^{\prime}\geq r$,
and assume $d(h,h^{\prime})\geq\max\\{d(g,g^{\prime}),r^{\prime}\\}$. Set
$m^{\prime}=\lceil\log((r^{\prime})^{-1})\rceil$, $s=\min\\{m,\lambda(g,h)\\}$
and $s^{\prime}=\min\\{m^{\prime},\lambda(g^{\prime},h^{\prime})\\}$. By
assumption,
$\lambda(h,h^{\prime})\leq\min\\{\lambda(g,g^{\prime}),m^{\prime}\\}$. Given
$u\in\\{0,1\\}$ let $u\dotplus 1$ be $2$ if $u=1$ and $1$ if $u=0$. Now fix
$(u,v)\in\\{0,1\\}^{2}$ and consider
$\lambda(f_{u}(r,h,g),f_{v}(r^{\prime},h^{\prime},g^{\prime}))$. This is

$\displaystyle\lambda(-\sum_{i=1}^{s+1}(h_{i}+g_{i})e^{i}+(u\dotplus
1)e^{s+1},-\sum_{i=1}^{s^{\prime}+1}(g^{\prime}_{i}+h_{i}^{\prime})e^{i}+(v\dotplus
1)e^{s^{\prime}+1})$ $\displaystyle=\lambda(-\sum_{i=1}^{s}2h_{i}+(u\dotplus
1-h_{s+1}-g_{s+1})e^{s+1},-\sum_{i=1}^{s^{\prime}}2h^{\prime}_{i}+(v\dotplus
1-h_{s^{\prime}+1}^{\prime}-g_{s^{\prime}+1}^{\prime})e^{s^{\prime}+1})$
$\displaystyle=\lambda(h,h^{\prime}),$

where the last equality is by definition of $s$ and $s^{\prime}$, and because
$\lambda(h,h^{\prime})\leq\min\\{\lambda(g,g^{\prime}),m^{\prime}\\}$. Thus
$d(c_{f_{u}(r,h,g)},c_{f_{v}(r^{\prime},h^{\prime},g^{\prime})})\geq
d(h,h^{\prime})$, as desired. ∎

We now show that the intersections of certain neighbhorhoods and non-
neighborhoods are contained in open balls.

######  Claim 6.13.

Given $a_{g},b_{g^{\prime}},b_{g^{\prime\prime}}\in
V(\textnormal{GS}_{p}(n))$, $N(a_{g},b_{g^{\prime}})\cap\neg
N(a,b_{g^{\prime\prime}})$ is contained in an open ball in $C$ ball of radius
$d(b_{g^{\prime}},b_{g^{\prime\prime}})$.

###### Proof.

Given $a\in\mathbb{F}_{p}^{n}$ and $\alpha\in\mathbb{F}_{p}$, define
$\tau_{i}^{\alpha}(a):=\alpha e^{i}-a$, and note that

$A(p,n)-a=\bigcup_{i=1}^{n}H_{i}+\tau_{i}^{1}(a).$

Fix $a_{g},b_{g^{\prime}},b_{b^{\prime\prime}}$ and consider
$C^{\prime}=N(a_{g},b_{g^{\prime}})\cap\neg N(a,b_{g^{\prime\prime}})$. Let
$h=g+g^{\prime}$ and $f=g+g^{\prime\prime}$. Then let
$C^{\prime}=\\{z_{w}:w\in(A(p,n)-h)\cap(\neg A(p,n)-f)\\}$, and set
$m=\lambda(h,f)$. Note

$(A(p,n)-h)\cap(\neg
A(p,n)-f)=\Big{(}\bigcup_{i=1}^{n}H_{i}+\tau_{i}^{1}(h)\Big{)}\cap\Big{(}\bigcup_{i=1}^{n}H_{i}+\tau_{i}^{0}(f)\Big{)}.$

We prove in [54], than the set above is contained in a single coset $K$ of
$H_{m-1}$ (see Lemma C.1 there). Consequently,
$C^{\prime}\subseteq\\{c_{v}:v\in K\\}$. We are now done since any coset of
$H_{m-1}$ is an open ball of radius
$p^{-m}=p^{-\lambda(h,f)}=d(b_{g^{\prime}},b_{g^{\prime\prime}})$ ∎

Our last lemma shows that sufficiently small balls around distinct points can
be “split apart” using the edge relation in $\textnormal{GS}_{p}(n)$.

######  Claim 6.14.

Suppose $a_{g},a_{g^{\prime}}\in A$, and $d(a_{g},a_{g^{\prime}})=r>0$. Then
for all $b_{g^{\prime\prime}}\in B$, there is $c_{h}\in C$ such that
$K_{3}[B_{r}(c_{h}),B_{r}(b_{g^{\prime\prime}}),B_{r}(a_{g})]\subseteq E$ and
$K_{3}[B_{r}(c_{h}),B_{r}(b_{g^{\prime\prime}}),B_{r^{\prime}}(a_{g^{\prime}})]\cap
E=\emptyset$, or vice versa.

###### Proof.

We begin by defining an element $f(a,b)\in\mathbb{F}_{p}^{n}$ for all distinct
$a,b\in\mathbb{F}_{p}$ with the property that for all $a\neq b$ in
$\mathbb{F}_{p}$,

$\\{a+f(a,b),b+f(a,b)\\}=\\{1,u\\}\text{ for some $u\notin\\{0,1\\}$}.$

Given $0<a<b$, let $f(a,b)=a-1$. Then set $f(0,p-1)=f(p-1,0)=2$, for each
$b\notin\\{0,p-1\\}$, and set $f(0,b)=f(b,0)=1$. Finally, set
$f(1,b)=f(b,1)=0$ for all $b\notin\\{0,1\\}$.

Now suppose $a_{g},a_{g^{\prime}}\in A$, and $d(a_{g},a_{g^{\prime}})=r>0$ and
$b_{g^{\prime\prime}}\in B$. Let $m=\lambda(g,g^{\prime})$, so $r=p^{-m}$.
Note $g_{i}=g_{i}^{\prime}$ for all $i\leq m$, by definition. Set

$\displaystyle
h=(\sum_{i=1}^{m}-g_{i}-g^{\prime\prime}_{i})+f(g_{m+1}+g^{\prime\prime}_{m+1},g^{\prime}_{m+1}+g^{\prime\prime}_{m+1})e^{m+1}.$

Then

$\displaystyle H_{m+1}+g+g^{\prime\prime}+h$
$\displaystyle=H_{m+1}+(f(g_{m+1}+g^{\prime\prime}_{m+1},g^{\prime}_{m+1}+g^{\prime\prime}_{m+1})+g_{m+1}+g^{\prime\prime}_{m+1})e^{d+1}\text{
and }$ $\displaystyle H_{m+1}+g+g^{\prime\prime}+h$
$\displaystyle=H_{m+1}+(f(g_{m+1}+g^{\prime\prime}_{m+1},g^{\prime}_{m+1}+g^{\prime\prime}_{m+1})+g^{\prime}_{m+1}+g^{\prime\prime}_{m+1})e^{d+1}.$

By our definition of $f$, one of these has the form $H_{m+1}+e^{m+1}$ and one
of them has the form $H_{m+1}+ue^{m+1}$ for some $u\notin\\{0,1\\}$. Thus one
is completely contained in $A(p,n)$, and the other is completely disjoint from
$A(p,n)$. Consequently,
$K_{3}[B_{r}(c_{h}),B_{r}(b_{g^{\prime\prime}}),B_{r}(a_{g})]\subseteq E$ and
$K_{3}[B_{r}(c_{h}),B_{r}(b_{g^{\prime\prime}}),B_{r^{\prime}}(a_{g^{\prime}})]\cap
E=\emptyset$, or vice versa. ∎

The existence of a metric which satisfies Claims 6.9, 6.10, 6.11, 6.12, 6.13,
6.14 is sufficient to show that $\textnormal{GS}_{p}(n)$ requires non-binary
$\textnormal{vdisc}_{3}$-error. In the next subsection, we will show very
similar axioms hold in $\textnormal{HP}(N)$, although some weakening will be
required.

####  6.3.2. Special properties of $\textnormal{HP}(N)$

In this subsection we show that $\textnormal{HP}(N)$ satisfies weakened
versions of the properties of the prior subsection. We begin by equipping
$\textnormal{HP}(N)$ with a metric in the obvious way. Recall that

$\textnormal{HP}(N)=(\\{a_{i},b_{i},c_{i}:i\in[N]\\},\\{a_{i}b_{j}c_{k}:i+j+k\geq
N+2\\}).$

To ease notation, in Section 6.3.2, we let $A=\\{a_{i}:i\in[N]\\}$,
$B=\\{b_{i}:i\in[N]\\}$, $C=\\{c_{i}:i\in[N]\\}$, and
$E=E(\textnormal{HP}(N))$.

######  Lemma 6.15.

For each $X\in\\{A,B,C\\}$ and $x_{i},x_{j}\in X$, set
$d(x_{i},x_{j})=\frac{|i-j|}{N}$. This makes each of $A,B,C$ into a metric
space with distances in $[0,1]$.

In an ideal world, we would like to prove all the same facts here for
$\textnormal{HP}(N)$ as we showed held for $\textnormal{GS}_{p}(n)$ in the
previous subsection. Indeed, some of the facts will go through largely
unchanged. For example, the following is a straightforward analogue of Claim
6.13.

######  Claim 6.16.

Given $a_{i}\in A$ and $b_{j},b_{j^{\prime}}\in B$,
$N(a_{i},b_{j^{\prime}})\cap\neg N(a_{i},b_{j^{\prime}})$ is contained in a
closed ball in $C$ ball of radius at most $d(b_{j^{\prime}},b_{j^{\prime}})$.

###### Proof.

Without loss of generality, assume $j^{\prime}<j$. Note that

$N(a_{i},b_{j})\cap\neg
N(a_{i},b_{j^{\prime}})=\\{c_{s}:s\in[N+2-i-j,N]\cap[0,N+2-i-j^{\prime})\\}.$

If this is empty, let $C$ be the ball of radius $0$ centered at $c_{1}$.
Otherwise, the above is equal to

$\\{c_{s}:s\in[N+2-i-j,N+2-i-j^{\prime})\\},$

which has size $|j-j^{\prime}|=d(b_{j},b_{j^{\prime}})N$. This set is clearly
contained in a closed ball of radius $|j-j^{\prime}|/2N$ in $C$. ∎

Other properties from Section 6.3.1 must be tweaked in a more serious way
before they will hold in $\textnormal{HP}(N)$. For instance, in
$\textnormal{HP}(N)$, a ball $B_{r}(a_{i})$ in $A$ is of the form

$\\{a_{j}:j\in(\min\\{i-rN,1\\},\max\\{i+rN,N\\})\\}.$

This could have size about $rN/2$ (e.g. if $i=N$), or it could have size $2rN$
(e.g. if $i=\lfloor N/2\rfloor$, and $r<1/2$). Consequently, not all balls
with the same radius contain the same number of vertices. However, we can
clearly give a range of $\lfloor\frac{r}{2}N\rfloor\leq|B_{r}(a_{i})|\leq
2rN$.

Similarly, not every vertex in $\textnormal{HP}(N)$ has the same degree. For
instance, if $i,j\geq N/2$, then $|N(a_{i}b_{j})|=N$, while if $i=j=1$, then
$|N(a_{i}b_{j})|=1$. However, we can show that most vertices have degree
within a certain non-trivial range, and that many (but not all) pairs of
vertices are in many edges and non-edges.

######  Claim 6.17.

Suppose $0<\tau<1/4$ and $0<3\mu<\tau$. The following hold in
$\textnormal{HP}(N)$.

  1. (1)

For all $i\in(\mu N,2\mu N)$ and $j\in(\tau N,(1-\tau)N)$,
$|N(a_{i}b_{j})|\in[\tau N/2,(1-\tau/2)N]$.

  2. (2)

For all $i\in(\mu N,2\mu N)$, $\min\\{|N(a_{i})|,|\neg N(a_{i})|\\}\geq
N^{2}/4$.

  3. (3)

For all $j\in(\tau N,(1-\tau)N)$, $|N(b_{j})|\in[\mu\tau
N^{2}/4,(1-\mu\tau/4)N^{2}]$.

###### Proof.

Given $i\in(\mu N,2\mu N)$ and $j\in(\tau N,(1-\tau)N)$, note

$N(a_{i}b_{j})=\\{c_{k}:k\in[N+2-i-j,N]\\}.$

Therefore,

$\tau N/2<\mu N+\tau
N-2\leq|N(a_{i}b_{j})|=i+j-2<N(1-\tau+2\mu)-2<N(1-\tau/2).$

This shows (1) holds. Further, for all $j\in(\tau N,(1-\tau)N)$, we have

$|N(b_{j})|\geq|(\mu N,2\mu N)|\tau N/2\geq\mu\tau N^{2}/4,$

and $|N(b_{j})|\leq N^{2}-|(\mu N,2\mu N)|\tau N/2\leq N^{2}-\mu\tau N^{2}/4$,
so (3) holds. For (3), we have that for all $i\in(\mu N,2\mu N)$,

$N^{2}/4\leq\sum_{j=1}^{N}\sum_{k=N+2-j-2\mu
N}k\leq\sum_{j=1}^{N}\sum_{k=N+2-j-i}^{N}k\leq|N(a_{i})|\leq\sum_{j=1}^{N}\sum_{k=1}^{N-j}k\leq
N^{2}/2$

as claimed. ∎

Claim 6.17 shows that almost all vertices (namely those with index in $(\tau
N,(1-\tau)N)$) have degree $\alpha N^{2}$ for some $\alpha$ bounded away from
$0$ and $1$. Further, there are many pairs of vertices with degree $\beta N$
for some $\beta$ bounded away from $0$ and $1$ (namely those where one vertex
has index in $(\mu N,2\mu N)$ and the other has index in $(\tau
N,(1-\tau)N)$).

This lemma, and the observations preceding it, illustrate a general strategy
for how to deal with $\textnormal{HP}(N)$ (as compared to
$\textnormal{GS}_{p}(n)$). In particular, we must make the statements more
approximate, and also relativize some of the quantifications to certain
“special small index sets” (e.g. the vertices with indices in $(\mu N,2\mu
N)$) and “special non-small index sets” (e.g. the vertices with indices in
$(\tau N,(1-\tau)N)$). To ease notation and emphasize this idea, we define,
for $\tau,\mu>0$,

$\displaystyle A_{lg}(\tau)$ $\displaystyle=\\{a_{i}:i\in(\tau
N,(1-\tau)N)\\}\text{ and }$ $\displaystyle A_{sm}(\mu)$
$\displaystyle=\\{a_{i}:i\in(\mu N,2\mu N)\\}.$

We define $B_{lg}(\tau)$, $B_{sm}(\mu)$, $C_{lg}(\tau)$, and $B_{sm}(\mu)$ in
the same way. We will always use these notions with $\mu$ being significantly
smaller than $\tau$, in which case $A_{lg}(\tau)\cap A_{sm}(\mu)=\emptyset$.
Note that Claim 6.17(1) says that every $ab\in A_{sm}(\mu)\times B_{lg}(\tau)$
has degree $\beta N$ for some $\beta$ bounded away from $0$ and $1$, and Claim
6.17(2) says that every $b\in B_{lg}(\tau)\cup B_{sm}(\mu)$ has degree of
$\alpha N^{2}$, for some $\alpha$ bounded away from $0$ and $1$.

When it comes to partitioning open balls into smaller ones (i.e. proving an
analogue of Claim 6.9), things are again more complicated. For instance,
unlike in the ultrametric space $\textnormal{GS}_{p}(n)$, we cannot partition
an open ball $B_{r}(a_{i})$ into disjoint open sub-balls. This is because any
open ball has the form $\\{a_{j}:j\in I\\}$, for some open interval $I$. Any
attempt to partition $I$ into disjoint open intervals will always miss a few
points of $I$, namely the endpoints of the sub-intervals. Problems can also
arise due to divisibility issues near the end points of intervals. The
following lemma will be used to deal with these issues, and says that we can
almost partition an interval into almost evenly sized sub-intervals. Below,
$d_{N}$ denotes the usual metric $d_{N}(i,j)=|i-j|$ on $[N]$. A ball in this
metric space has the form $(x-d,x+d)\cap[N]$ for some $x\in[N]$ and $d\in[N]$.

######  Lemma 6.18.

For all $0<r_{1}<1$, there is $n_{0}$ so that if $N\geq n_{0}$, the following
holds. Suppose $0<r_{1}<r_{2}$, and $I=(\alpha,\beta)$ is an open ball of
radius $r_{2}N$ in $[N]$. Then there is $m\leq 4r_{2}/r_{1}$ and a collection
$\mathcal{P}$ of $m$ open balls contained in $I$, each of radius at most
$r_{1}N$ and at least $r_{1}N/3$, such that
$|I\setminus(\bigcup\mathcal{P})|\leq 2m$.

###### Proof.

Assume $N\gg r_{1}^{-1},r_{2}^{-1}$. Set $d_{2}=\lceil r_{2}N\rceil$ and
$d_{1}=\lceil r_{1}N/3\rceil$. Let $i\in[N]$ be such that

$I=(\alpha,\beta)=(i-d_{2},i+d_{2})\cap[1,N].$

Note $d_{2}+1\leq|I|=\beta-\alpha+1\leq 2d_{2}+1$. Set
$s=\lfloor|\beta-\alpha|/(2d_{1})\rfloor$, and for each $j\in[s]$, set
$x_{j}=\alpha+(2j-1)d_{1}$. Note that for each $j\in[s]$, $x_{j}+d_{1}<\beta$,
so the ball of radius $d_{1}$ around $x_{j}$ is contained in $I$. However,
$I\setminus(\bigcup_{j=1}^{s}B_{d_{1}}(x_{j}))$ could be large if
$(x_{s}+d_{1},\beta)$ is large. To make sure this is not an issue, we will
combine the last two balls into one ball of a slightly different radius.

By definition of $x_{s-1}$, $2d_{1}<\beta-(x_{s-1}-d_{1})\leq 4d_{1}$. Set
$d_{1}^{\prime}=\lfloor(\beta-(x_{s-1}-d_{1}))/2\rfloor$, and let
$x_{s-1}^{\prime}=x_{s-1}+d_{1}^{\prime}$. Set

$\mathcal{P}=\\{B_{d_{1}}(x_{i}):1\leq i\leq
s-1\\}\cup\\{B_{d_{1}^{\prime}}(x^{\prime}_{s-1})\\}.$

By construction, every element in $\mathcal{P}$ is an open ball of radius at
most $r_{1}N$ and at least $r_{1}N/3$, and

$|I\setminus(\bigcup\mathcal{P})|\leq|\\{\alpha,x_{1},\ldots,x_{s-2},x_{s-1}^{\prime}\\}\cup\\{\beta,\beta-1\\}|\leq
s+2.$

By definition $s\leq(2r_{2}N+2)/2d_{1}N\leq(2r_{2}N+2)/(2r_{1}N/3)\leq
4r_{2}/r_{1}$, where the last inequality uses that $N$ is large. ∎

We can now give a weak analogue of Claim 6.9.

######  Claim 6.19.

Suppose $0<r_{1}<\mu^{2}$, $r_{1}<r_{2}\leq 1$, $N$ is sufficiently large
compared to $r_{1}$, and $a\in A$. Then there is some $m\leq 4r_{1}/r_{2}$ and
a set $\mathcal{P}$ of $m$ disjoint open balls, each of radius at least
$r_{1}/3$ and at most $r_{1}$, all contained in $B_{r_{2}}(a)$, such that
$|B_{r_{2}}(a)\setminus(\bigcup\mathcal{P})|\leq 2m$.

###### Proof.

Note $B_{r_{2}}(a)=\\{a_{i}:i\in I\\}$ for some open ball $I$ in $[N]$. The
conclusion is thus an immediate corollary of Lemma 6.18. ∎

We recall that in Claim 6.9, there was an additional conclusion beyond what we
have shown above, namely that we were also able to choose one of the balls in
the cover ahead of time. Due to divisibility issues, we cannot always do this
in $\textnormal{HP}(N)$, but it turns out that Claim 6.19 along with Claim