6.20 below will suffice. In particular, Claim 6.20 says that given an open
ball $B_{r}(a)$ in $A$, whose center is not too close to the endpoints of
$[N]$ (where problems arise), we can almost partition $A$ into balls, one of
which is $B_{r}(a)$. To help deal with this requirement, we define the
following slightly enlarged versions of our special sets:

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

We define $B_{sm}(\mu)^{+},B_{lg}(\mu)^{+}$ and
$C_{sm}(\mu)^{+},C_{lg}(\mu)^{+}$ similarly.

######  Claim 6.20.

Assume $0<\tau<1/4$, $0<\mu<\tau/3$, and $0<r<\mu^{2}$. For $N$ sufficiently
large, the following holds. For all $a_{i}\in A_{lg}(\tau)^{+}\cup
A_{sm}(\mu)^{+}$, there are $m\leq 8r^{-1}$ and a set $\mathcal{P}$ of $m$
disjoint open balls in $A$, each of radius at most $r$ and at least $r/3$,
such that $B_{r}(a_{i})\in\mathcal{P}$ and
$|A\setminus(\bigcup\mathcal{P})|\leq 2m$.

###### Proof.

Assume $N\gg r^{-1},\mu^{-1}$. Suppose $a_{i}\in A_{lg}(\tau)^{+}\cup
A_{sm}(\mu)^{+}$ and $0<r<\mu^{2}$. By assumption,
$i\in((\tau-\mu^{2})N,(1-\tau+\mu^{2})N)\cup((\mu-\mu^{2})N,(2\mu+\mu^{2})N)$.
Let $d=\lceil rN\rceil$. Note that $B_{r}(a_{i})$ has the form $\\{a_{i}:i\in
I\\}$ for some open ball $I=(i-d,i+d)\cap[N]$ in $[N]$. Since $a_{i}\in
A_{lg}^{+}(\tau)\cup A_{sm}^{+}(\mu)$ and $r<\mu^{2}$, we know that
$i-d>\mu-2\mu^{2}$ and $i+d<\tau+2\mu^{2}$. Consequently, both $i-d$ and $i+d$
are in $[N]$. Let $I_{1}=[1,i-d)$ and $I_{2}=(i+d,N]$. These can also be
written as open balls in $[N]$, say of radii $d_{1}$ and $d_{2}$,
respectively. Note that $d_{1},d_{2}\geq(\mu-2\mu^{2})N/2$.

By Lemma 6.18 there are $m_{1}\leq 4\frac{r_{1}}{N}r^{-1}$ and a collection
$\mathcal{P}_{1}$ of open balls in $([N],d_{N})$, each of radius at least
$rN/3$ and at most $rN$ such that each element of $\mathcal{P}_{1}$ is
contained in $(i+d,N)$ and $|(i+d,N)\setminus(\bigcup\mathcal{P}_{1})|\leq
2m_{1}$. Similarly, there are $m_{2}\leq 4r_{2}r^{-1}$ and a collection
$\mathcal{P}_{1}$ of open balls in $([N],d_{N})$, each of radius at least
$rN/3$ and at most $rN$ such that each element of $\mathcal{P}_{2}$ is
contained in $(1,i-d)$ and $|(1,i-d)\setminus(\bigcup\mathcal{P}_{2})|\leq
2m_{2}$. We then let

$\mathcal{P}=\\{B_{r}(a_{i})\\}\cup\mathcal{P}_{1}\cup\mathcal{P}_{2}.$

Note $|\mathcal{P}|=m_{1}+m_{2}+1\leq 4r^{-1}$. By construction, each element
of $\mathcal{P}$ is a ball of radius at least $r/3$ and at most $r$, and
$|A\setminus(\bigcup\mathcal{P})|\leq 2m_{1}+2m_{2}+2\leq 8r^{-1}$, as
desired. ∎

We will need one more partition fact, namely that given a ball $B_{r}(a_{i})$
whose center $a_{i}$ is in $A_{sm}(\mu)$, the approximate subcover obtained in
Claim 6.19 will have the property that $B_{r}(a_{i})\cap A_{sm}(\mu)$ is
mostly covered by balls whose centers are in $A_{sm}(\mu)^{+}$.

######  Claim 6.21.

In Claim 6.19, if $\mathcal{P}^{\prime}$ are the elements of $\mathcal{P}$
centered at elements in $A^{+}_{sm}(\mu)$, and $\mathcal{P}^{\prime\prime}$
are those centered at $A_{lg}(\tau)^{+}$, then

$\displaystyle|(B_{r_{2}}(a)\cap
A_{sm}(\mu))\setminus(\bigcup\mathcal{P}^{\prime})|\leq 2m$
$\displaystyle|(B_{r_{2}}(a)\cap
A_{lg}(\tau))\setminus(\bigcup\mathcal{P}^{\prime\prime})|\leq 2m$

###### Proof.

This is immediate from the definitions of $A_{sm}(\mu)^{+}$ and
$A_{lg}(\tau)^{+}$. ∎

We now turn to the analogues of Claims 6.11 and 6.12. For these we must
restrict ourselves to our special sets $A_{sm}(\mu)^{+}$ and
$A_{lg}(\mu)^{+}$.

######  Claim 6.22.

Suppose $0<\tau<1/4$, $0<\mu<\tau/3$, and $0<r<\mu^{2}$. For all sufficiently
large $N$ the following holds. For every $a\in A_{lg}(\tau)^{+}$ and $b\in
B_{sm}(\mu)^{+}$, there are $f_{0}(r,a,b),f_{1}(r,a,b)\in[N]$ such that

$\displaystyle K_{3}[B_{r/2}(c_{f_{0}(r,a,b)}),B_{r}(a),B_{r}(b)]\subseteq
E\text{ and }K_{3}[B_{r/2}(c_{f_{1}(r,a,b)}),B_{r}(a),B_{r}(b)]\cap
E=\emptyset,$

and such that $d(c_{f_{0}(r,a,b)},c_{f_{1}(r,a,b)})\leq 7r$.

###### Proof.

Suppose $(\tau-\mu^{2})N<i<(1-\tau+\mu^{2})N$,
$(\mu-\mu^{2})N<j<(2\mu+\mu^{2})N$, and $0<r<\mu^{2}$. Set $d_{1}=\lceil
rN\rceil$, and define

$\displaystyle f_{0}(r,a_{i},b_{j})=N+2-i-j-3d_{1}\text{ and
}f_{1}(r,a_{i},b_{j})=N+2-i-j+3d_{1}.$

Note each of these are in $[N]$ due to the assumptions on $i$, $j$, and $r$.
Suppose $a_{w}b_{u}c_{v}\in B_{r}(a_{i})\times B_{r}(b_{j})\times
B_{r/2}(c_{f_{0}(r,a_{i},b_{j})})$. Then

$\displaystyle w+u+v<(i+d_{1})+(j+d_{1})+(N+2-i-j-3d_{1})+\lceil
d_{1}/2\rceil$ $\displaystyle=N+2-d_{1}+\lceil rN/2\rceil$
$\displaystyle<N+2.$

On the other hand, if $a_{w}b_{u}c_{v}\in B_{r}(a_{i})\times
B_{r}(b_{j})\times B_{r/2}(c_{f_{1}(r,a_{i},b_{j})})$. Then

$\displaystyle w+u+v$ $\displaystyle>(i-\lfloor rN\rfloor)+(j-\lfloor
rN\rfloor)+(N+2-i-j+3d_{1})-\lfloor rN/2\rfloor$ $\displaystyle\geq
N+d_{1}-\lfloor rN/2\rfloor$ $\displaystyle>N+2,$

where the last inequality uses the $N$ is large. Note that by construction,
$d(c_{f_{1}(r,a_{i},b_{j})},c_{f_{0}(r,a_{i},b_{j})})=6d_{1}/N\leq 7r$. ∎

As in Section 6.3.1, it is important to know the $f_{u}(r,a,b)$,
$f_{v}(r^{\prime},a^{\prime},b^{\prime})$ obtained in Claim 6.22 are far for
certain choices of $a,b,r,a^{\prime},b^{\prime},r^{\prime}$.

######  Claim 6.23.

Assume $0<\tau<1/4$, $0<\mu<\tau/3$, and $0<r\leq r^{\prime}<\mu^{2}$. For any
$a,a^{\prime}\in A_{lg}(\tau)^{+}$ and $b,b^{\prime}\in B_{sm}(\mu)^{+}$ the
following hold.

  1. (1)

For each $u\in\\{0,1\\}$, $d(f_{u}(r,a,b),f_{u}(r,a,b^{\prime}))\geq
d(b,b^{\prime})$ and $d(f_{u}(r,a^{\prime},b),f_{u}(r,a,b))\geq
d(a,a^{\prime})$.

  2. (2)

If $d(a,a^{\prime})\geq d(b,b^{\prime})+6r^{\prime}$, then

$\min\\{d(c_{f_{u}(r,a,b)},c_{f_{v}(r^{\prime},a^{\prime},b^{\prime})}):u,v\in\\{0,1\\}\\}\geq
d(a,a^{\prime})-d(b,b^{\prime})-7r^{\prime}.$

  3. (3)

If $d(b,b^{\prime})\geq d(a,a^{\prime})+6r^{\prime}$, then

$\min\\{d(c_{f_{u}(r,a,b)},c_{f_{v}(r^{\prime},a^{\prime},b^{\prime})}):u,v\in\\{0,1\\}\\}\geq
d(b,b^{\prime})-d(a,a^{\prime})-7r^{\prime}.$

###### Proof.

Suppose $a_{i},a_{i^{\prime}}\in A_{lg}(\tau)^{+}$ and
$b_{j},b_{j^{\prime}}\in B_{sm}(\mu)^{+}$. By definition, for each
$u\in\\{0,1\\}$,

$d(f_{u}(r,a_{i},b_{j}),f_{u}(r,a_{i^{\prime}},b_{j}))=|i-i^{\prime}|.$

Thus
$d(c_{f_{u}(r,a_{i},b_{j})},d_{f_{u}(r,a_{i^{\prime}},b_{j})})=|i-i^{\prime}|/N=d(a,a^{\prime})$.
A symmetric argument shows that
$d(f_{u}(r,a,b),f_{u}(r,a,b^{\prime}))=d(b,b^{\prime})$, so (1) holds. For
(2), suppose that $d(b_{j},b_{j^{\prime}})\geq
d(a_{i},a_{i^{\prime}})+6r^{\prime}$. Without loss of generality, say
$j^{\prime}>j$. Then for any $(u,v)\in\\{0,1\\}^{2}$,

$\displaystyle d(f_{u}(r,a,b),f_{v}(r^{\prime},a^{\prime},b^{\prime}))$
$\displaystyle=|N+2-i-j+(-1)^{u}3\lceil rN\rceil-(N+2-i-j+(-1)^{v}3\lceil
r^{\prime}N\rceil)|$ $\displaystyle\geq|j^{\prime}-j|-|i^{\prime}-i|-6\lceil
r^{\prime}N\rceil,$

where the inequality is using the assumption that $d(b_{j},b_{j^{\prime}})\geq
d(a_{i},a_{i^{\prime}})+6r^{\prime}$, and that $r^{\prime}\geq r$.
Consequently,

$\displaystyle
d(c_{f_{u}(r,a_{i},b_{j})},c_{f_{v}(r^{\prime},a_{i^{\prime}},b_{j^{\prime}})})$
$\displaystyle\geq|j^{\prime}-j|-|i^{\prime}-i|-6\lceil
r^{\prime}N\rceil/N\geq
d(b_{j},b_{j^{\prime}})-d(a_{i},a_{i^{\prime}})-7r^{\prime}.$

The argument for (3) is similar. ∎

We now give the analogue of Claim 6.14. The version here is a bit weaker
because the balls are smaller, and we will also require things to be
sufficiently spaced out.

######  Claim 6.24.

Suppose $0<\tau<1/4$, $0<3\mu<\tau$, $0<r,r^{\prime}<\mu^{2}$ and
$r^{\prime\prime}\geq\max\\{r,r^{\prime}\\}$. Then if $N$ is sufficiently
large, the following hold.

For all $a_{i}\in A^{+}_{lg}(\tau)$ and $a_{i^{\prime}}\in A$ with
$d(a,a^{\prime})=r^{\prime\prime}+r^{\prime}+r$, there is $b\in B_{sm}(\mu)$
and $c\in C$ such that if $r_{0}=\min\\{r,r^{\prime},r^{\prime\prime}\\}/3$,
then
$K_{3}[B_{r_{0}/2}(c),B_{r_{0}/2}(b),B_{r^{\prime}}(a_{i^{\prime}})]\subseteq
E$ and $K_{3}[B_{r_{0}/2}(c),B_{r_{0}/2}(b),B_{r}(a_{i})]\cap E=\emptyset$, or
vice versa.

###### Proof.

Fix $a_{i}\in A_{lg}^{+}(\tau)$ and $a_{i^{\prime}}\in A$ satisfying
$d(a,a^{\prime})=r^{\prime\prime}+r^{\prime}+r$, where
$r^{\prime\prime}>2\max\\{r^{\prime},r\\}$ and $0<r,r^{\prime}<\mu^{2}$. Set
$r_{0}=\min\\{r,r^{\prime},r^{\prime\prime}\\}/3$, and choose any $b_{j}\in
B_{sm}(\mu)$ (note this implies $\mu N<j<2\mu N$).

Suppose first that $i^{\prime}\in((\tau-\mu^{2})N,N(1-\tau+\mu^{2}))$ and
$i\leq i^{\prime}$. Let $k=N+2-i^{\prime}-j+\lceil r^{\prime}N\rceil+\lceil
r_{0}N\rceil$. Our assumptions imply $i^{\prime}+j\leq(1-\tau+\mu)N$ so $k\geq
N+2-i^{\prime}-j\geq(\tau-\mu^{2}-\mu)N\geq 1$. On the other hand,

$k\leq N+2-(\tau-\mu^{2})N-\mu N+2+r^{\prime}N+r_{0}N\leq N,$

where the last inequality is because $r^{\prime},r_{0}<\mu^{2}$ and $N$ is
large. Thus $k\in[N]$, so it makes sense to define $c=c_{k}$. Suppose
$b_{u}c_{v}\in B_{r_{0}/2}(b_{j})\times B_{r_{0}/2}(c)$, $a_{s}\in
B_{r^{\prime}}(a_{i^{\prime}})$ and $a_{t}\in B_{r}(a_{i})$. Then using that
$i^{\prime}-i=r+r^{\prime}+r^{\prime\prime}$ by assumption, we have

$\displaystyle t+u+v$
$\displaystyle<(i+rN)+(j+r_{0}N/2)+(N+2-i^{\prime}-j+\lceil
r^{\prime}N\rceil+\lceil r_{0}N\rceil+r_{0}N/2)$
$\displaystyle=N+2+r_{0}N-(i^{\prime}-i)+\lceil r^{\prime}N\rceil+\lceil
r_{0}N\rceil$ $\displaystyle\leq
N+7-(r+r^{\prime}+r^{\prime\prime})N-r^{\prime}N+r_{0}N$ $\displaystyle<N+2,$

where the last inequality is because
$r^{\prime\prime}>2\max\\{r,r^{\prime}\\}$ and $N$ is large. Thus
$a_{t}b_{u}c_{v}\notin E$. On the other hand,

$\displaystyle s+u+v$
$\displaystyle>(i^{\prime}-r^{\prime}N)+(j-r_{0}N/2)+(N+2-i^{\prime}-j+\lceil
r^{\prime}N\rceil+\lceil r_{0}N\rceil-r_{0}N/2)$
$\displaystyle=N+2-r_{0}N+\lceil r^{\prime}N\rceil+\lceil r_{0}N\rceil$
$\displaystyle\geq N+2.$

Thus $a_{s}b_{u}c_{v}\in E$.

If $i^{\prime}\in((\tau-\mu^{2})N,N(1-\tau+\mu^{2}))$ and $i^{\prime}\leq i$,
then proceed as above with the roles of $i$ and $i^{\prime}$ switched.

Suppose now that $i^{\prime}<(\tau-\mu^{2})N$. In this case, set
$k=N+2-i-j+\lceil rN\rceil+\lceil r_{0}N\rceil$. It is straightforward to
check that $k\in[N]$ since $i\in((\tau-\mu^{2})N,(1-\tau+\mu^{2})N)$ and
$j\in(\mu N,2\mu N)$. Thus it makes sense to define $c=c_{k}$. Suppose
$b_{u}c_{v}\in B_{r_{0}/2}(b_{j})\times B_{r_{0}/2}(c)$, $a_{s}\in
B_{r^{\prime}}(a_{i^{\prime}})$ and $a_{t}\in B_{r}(a_{i})$. Then

$\displaystyle t+u+v$ $\displaystyle>(i-rN)+(j-r_{0}N/2)+(N+2-i-j+\lceil
rN\rceil+\lceil r_{0}N\rceil-r_{0}N/2)$ $\displaystyle=N+2-rN+\lceil rN\rceil-
r_{0}N+\lceil r_{0}N\rceil$ $\displaystyle\geq N+2.$

Thus $a_{t}b_{u}c_{v}\in E$. On the other hand

$\displaystyle s+u+v$
$\displaystyle<(i^{\prime}+r^{\prime}N)+(j+r_{0}N/2)+(N+2-i-j+\lceil
rN\rceil+\lceil r_{0}N\rceil+r_{0}N/2)$
$\displaystyle=N+2-(i-i^{\prime})+r_{0}N+\lceil rN\rceil+\lceil r_{0}N\rceil$
$\displaystyle\leq N+2-\lfloor(r+r^{\prime}+r^{\prime\prime})N\rfloor+\lceil
rN\rceil+\lceil r_{0}N\rceil$ $\displaystyle\leq N+2,$

where the last inequality is since $N$ is large and
$r^{\prime\prime}>2\max\\{r,r^{\prime}\\}\geq 6r_{0}$. Thus
$a_{s}b_{u}c_{v}\notin E$.

Finally, consider the case where $i^{\prime}>N(1-\tau+\mu^{2})$. In this case,
set

$k=N+2-i-j-\lceil rN\rceil-\lceil r_{0}N\rceil.$

As above, it is straightforward to check that $k\in[N]$. Thus it makes sense
to define $c=c_{k}$. Suppose $b_{u}c_{v}\in B_{r_{0}/2}(b_{j})\times
B_{r_{0}/2}(c)$, $a_{s}\in B_{r^{\prime}}(a_{i^{\prime}})$ and $a_{t}\in
B_{r}(a_{i})$. Then

$\displaystyle s+u+v$
$\displaystyle>(i^{\prime}-r^{\prime}N)+(j-r_{0}N/2)+(N+2-i-j-\lceil
rN\rceil-\lceil r_{0}N\rceil-r_{0}N/2)$
$\displaystyle=N+2+(i^{\prime}-i)-r^{\prime}N-\lceil rN\rceil-r_{0}N-\lceil
r_{0}N\rceil$ $\displaystyle\geq
N+2+\lfloor(r+r^{\prime}+r^{\prime\prime})N\rfloor-r^{\prime}N-\lceil
rN\rceil-r_{0}N-\lceil r_{0}N\rceil$ $\displaystyle\geq N+2,$

where the last inequality is because $N$ is large and
$r^{\prime\prime}>2\max\\{r,r^{\prime}\\}\geq 6r_{0}$. Thus
$a_{s}b_{u}c_{v}\notin E$. On the other hand

$\displaystyle t+u+v$ $\displaystyle<(i+rN)+(j+r_{0}N/2)+(N+2-i-j-\lceil
rN\rceil-\lceil r_{0}N\rceil+r_{0}N/2)$ $\displaystyle=N+2+rN-\lceil
rN\rceil+r_{0}N-\lceil r_{0}N\rceil$ $\displaystyle\leq N+2,$

thus $a_{t}b_{u}c_{v}\notin E$. This finishes the proof. ∎

We will see that the properties described in this section are sufficient for
showing that $\textnormal{HP}(N)$ requires non-binary
$\textnormal{vdisc}_{3}$-error. Further, they are strictly weaker than the
properties laid out in Section 6.3.1. For this reason, the axioms in
Definition 6.25 will be based on what holds in $\textnormal{HP}(N)$.

####  6.3.3. Special $3$-graphs

In this section we define special $3$-graphs, and show that both
$\textnormal{HP}(N)$ and $\textnormal{GS}_{p}(n)$ are special, for
appropriately chosen parameters.

######  Definition 6.25.

Suppose $p\geq 2$ and $G=(A\cup B\cup C,E)$ is a $3$-partite $3$-graph where
$|A|=|B|=|C|=N$. We say $G$ is _$(p,\mu,\tau,\alpha,\rho)$ -special_ if there
is a metric $d$ on $A$, $B$, and $C$ with distances in $[0,1]$, and
distinguished subsets $A_{sm}\subseteq A_{sm}^{+}$ and $A_{lg}\subseteq
A_{lg}^{+}$ of $A$, $B_{sm}\subseteq B_{sm}^{+}$ and $B_{lg}\subseteq
B_{lg}^{+}$ of $B$, and $C_{sm}\subseteq C_{sm}^{+}$, and $C_{lg}\subseteq
C_{lg}^{+}$ of $C$, satisfying the following axioms for all permutations $XYZ$
of $ABC$, where given $X\in\\{A,B,C\\}$, $B_{r}(x)=\\{x^{\prime}\in
X:d(x,x^{\prime})<r\\}$.

  1. (1)

(Special Subsets Axiom) There are $r_{sm}\geq\mu/2$, $r_{lg}\geq\tau/2$, and
$x_{sm},x_{lg}\in X$ such that $X_{sm}=B_{r_{sm}}(x_{sm})$,
$X_{lg}=B_{r_{lg}}(x_{lg})$, $X_{sm}^{+}=B_{r_{sm}+\mu^{2}}(x_{sm})$, and
$X_{lg}^{+}=B_{r_{lg}+\mu^{2}}(x_{lg})$.

  2. (2)

(Size Axiom) For each $r\in(0,1]$ and $x\in X$, $r|X|/2p\leq|B_{r}(x)|\leq
pr|X|$.

  3. (3)

(Degree Axiom) For all $x\in X_{lg}^{+}\cup X_{sm}^{+}$,

$\min\\{|N(x)\cap K_{2}[Y,Z]|,|\neg N(x)\cap K_{2}[Y,Z]|\\}\geq\alpha n^{2}.$

  4. (4)

(Intersection Axiom) For all $y\in Y$ and $z,z^{\prime}\in Z$, there is a
closed ball of radius at most $d(z,z^{\prime})$ containing $N(y,z)\cap\neg
N(y,z^{\prime})$.

  5. (5)

(Partition Axiom) For any $\rho<r<\mu^{2}$ and $x\in X_{lg}^{+}\cup
X_{sm}^{+}$, there are $m\leq 4p(r^{-1})$ and a set $\mathcal{P}$ of $m$
disjoint open balls in $X$ of radius at least $r/3$ and at most $r$, one of
which is $B_{r}(x)$, such that $|X\setminus(\bigcup\mathcal{P})|\leq 2m$.

  6. (6)

(Covering Axiom) Suppose $\rho<r_{1}<\mu^{2}$ and $r_{1}<r_{2}\leq 1$, and $B$
is a ball of radius $r_{2}$ in $X$. Then there is some $m\leq 2pr_{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$, such that
$|B\setminus(\bigcup\mathcal{P})|\leq 2m$. Moreover, the following hold.

    1. (a)

If $\mathcal{P}^{\prime}=\\{B_{r}(x)\in\mathcal{P}:x\in X_{lg}^{+}\\}$, then
$|(B\cap X_{lg})\setminus(\bigcup\mathcal{P}^{\prime})|\leq 2m$

    2. (b)

If $\mathcal{P}^{\prime\prime}=\\{B_{r}(x)\in\mathcal{P}:x\in X_{sm}^{+}\\}$,
then $|(B\cap X_{sm})\setminus(\bigcup\mathcal{P}^{\prime\prime})|\leq 2m$.

  7. (7)

(Splitting Axiom 1) For every $x\in X_{lg}^{+}$ and $y\in Y_{sm}^{+}$ and
$\rho<r<\mu^{2}$, there are $f_{0}(r,x,y)$ and $f_{1}(r,x,y)$ such that
$B_{r/2}(f_{u}(r,x,y))\times B_{r}(x)\times B_{r}(y)\subseteq E^{u}$ for each
$u\in\\{0,1\\}$, and such that $d(f_{0}(r,x,y),f_{1}(r,x,y))\leq 3r$. Further,
the following hold.

    1. (a)

If $y\neq y^{\prime}$, then for each $u\in\\{0,1\\}$,
$d(f_{u}(r,x,y),f_{u}(r,x,y^{\prime}))\geq d(y,y^{\prime})$,

    2. (b)

If $d(y,y^{\prime})\geq d(x,x^{\prime})+6r^{\prime}$, then

$\min\\{d(f_{u}(r,x,y),f_{v}(r^{\prime},x^{\prime},y^{\prime})):u,v\in\\{0,1\\}\\}\geq
d(y,y^{\prime})-d(x,x^{\prime})-7r^{\prime}.$

    3. (c)

If $d(x,x^{\prime})\geq d(y^{\prime},y)+6r^{\prime}$, then

$\min\\{d(f_{u}(r,x,y),f_{v}(r^{\prime},x^{\prime},y^{\prime})):u,v\in\\{0,1\\}\\}\geq
d(x,x^{\prime})-d(y,y^{\prime})-7r^{\prime}.$

  8. (8)

(Splitting Axiom 2) For all $x\in X^{+}_{lg}$ and $x^{\prime}\in X$ satisfying
$d(x,x^{\prime})=r^{\prime\prime}+r^{\prime}+r$, where $\rho\leq
r,r^{\prime}<\mu^{2}$ and $r^{\prime\prime}>2\max\\{r^{\prime},r\\}$, and all
$y\in Y_{sm}$ there is $z=f(x,x^{\prime},y)\in Z$ such that if
$r_{0}=\min\\{r,r^{\prime},r^{\prime\prime}\\}/3$, then
$K_{3}[B_{r_{0}/2}(y),B_{r_{0}/2}(z),B_{r^{\prime}}(x^{\prime})]\subseteq E$
and $K_{3}[B_{r_{0}/2}(y),B_{r_{0}/2}(z),B_{r}(x)]\cap E=\emptyset$, or vice
versa.

  9. (9)

(Disjointness Axiom) The sets $X_{sm}^{+}$ and $X_{lg}^{+}$ are disjoint.

It seems likely that with a bit more work, one could get rid of Splitting
Axiom 2 by deducing it from a version of Splitting Axiom. However, optimizing
the list of axioms is not our main goal. We can now easily verify that our
main examples are special.

######  Proposition 6.26.

For all $p\geq 2$, there is $n_{0}$ such that for all $\rho>0$ and all $n\geq
n_{0}$, $\textnormal{GS}_{p}(n)$ is
$(p,1/p^{2},1/p^{2},\frac{1}{2(p-1)},\rho)$-special.

###### Proof.

Equip $A$, $B$, and $C$ with the metrics defined in Section 6.3.1. For each
$X\in\\{A,B,C\\}$, set

$\displaystyle X_{lg}$ $\displaystyle=X_{lg}^{+}=\\{x_{g}:g\in
H_{1}+e_{1}\\}\text{ and }X_{sm}=X_{sm}^{+}=\\{x_{g}:g\in H_{1}+e_{2}\\}.$

Clearly these are balls of radius at least $p^{-2}$ (see Claim 6.9), and
$X_{sm}^{+}\cap X_{lg}^{+}=\emptyset$. Thus Axiom (1) holds. Axiom (2) holds
by the comments following 6.8. Axioms (3)-(7) hold immediately from Claims
6.9, 6.10, 6.11, 6.12, 6.13, 6.14, and the fact that the roles of $A$, $B$ and
$C$ are symmetric in $\textnormal{GS}_{p}(n)$. ∎

######  Proposition 6.27.

For all $0<\tau<1/4$, $0<\mu<\tau/3$, $0<\rho<\mu^{3}$, and $p\geq 2$, there
is $n_{0}$ such that for all $N\geq n_{0}$, $\textnormal{HP}(N)$ is
$(p,\mu,1-\tau,\mu^{2},\rho)$-special.

###### Proof.

Choose $n_{0}$ sufficiently large for $\tau$, $\mu$, and
$r,r^{\prime},r^{\prime\prime}\geq\rho$ in Claims 6.19 and 6.24. Assume $N\geq
n_{0}$ and equip each of $A,B,C$ in $\textnormal{HP}(N)$ the metrics described
in Section 6.3.2. Set $x_{lg}=x_{\lfloor n/2\rfloor}$, $x_{sm}=x_{\lfloor 3\mu
N/2\rfloor}$, $r_{sm}=\mu/2$, and $r_{lg}=(1-\tau)/2$. Then define
$X_{sm},X_{sm}^{+},X_{lg},X_{lg}^{+}$ to satisfy Axiom of 1 of Definition
6.25. These will each differ from the sets defined as
$X_{sm}(\mu),X_{sm}^{+}(\mu),X_{lg}(\tau),X_{lg}(\tau)^{+}$ in Section 6.3.2
by at most two points each (note not every interval in $[N]$ is an open ball
due to divisibility issues). This difference will not effect the results
proved in Section 6.3.2 as $N$ is large. Note Axiom (9) holds by the
definition of $X_{lg}^{+},X_{sm}^{+}$ and the assumptions on $\tau$ and $\mu$.
Axiom (2) clearly holds by the discussion following Claim 6.17. Then (3)-(7)
hold by Claims 6.17, 6.22, 6.23, 6.19, 6.21, 6.16, 6.24, along with the fact
that the roles of $A$, $B$ and $C$ are symmetric in $\textnormal{HP}(N)$. ∎

###  6.4. Proof of Theorems 1.60 and 1.63

In this subsection we give the proofs of Theorems 1.60 and 1.63. We begin with
Theorem 6.28 below, which shows that special $3$-graphs will not admit
$\textnormal{vdisc}_{3}$-homogeneous partitions with binary error.

######  Theorem 6.28.

Suppose $p\geq 2$, $0<\mu<1/16$, $0<\tau<1-4\mu$, and $\alpha>0$. For all
$0<\epsilon<\alpha\mu/p^{16}$, there is $t_{0}\geq 1$, so that for all $T\geq
t_{0}$, the following holds. There is $\rho>0$ such that for all sufficiently
large $n$, if $G=(A\cup B\cup C,E)$ is a $(p,\mu,\tau,\alpha,\rho)$-special
$3$-partite $3$-graph with $|A|=|B|=|C|=n$, then $G$ does not admit an
$\epsilon$-homogeneous partition with binary error and $t$ parts, for any
$t_{0}\leq t\leq T$.

###### Proof.

Fix $p\geq 2$, $0<\mu<1/16$, $0<\tau<1-4\mu$, and $\alpha>0$. Choose
$0<\epsilon\ll\alpha,\mu,\tau$ and $t_{0}\gg\epsilon^{-1}$. Fix $T\geq t_{0}$.
Then choose $0<\rho\ll T^{-1}p^{-100}\mu\tau$, $n\gg
T\rho^{-1}\epsilon^{-1}p^{-1}$ and set $N=3n$.

Suppose $G=(A\cup B\cup C,E)$ is a $3$-partite $3$-graph with $|A|=|B|=|C|=n$,
and which is $(p,\alpha,\mu,\tau,\rho)$-special. For ease of notation, set
$V=A\cup B\cup C$. Suppose towards a contradiction there are $t_{0}\leq t\leq
T$ and an equipartition $\mathcal{P}=\\{V_{1}\cup\ldots\cup V_{t}\\}$ of $V$
and $\Sigma\subseteq{[t]\choose 2}$ so that $|\Sigma|\leq\epsilon t^{2}$, and
for all $ijk\in{[t]\choose 2}$, if $ij,jk,ik\notin\Sigma$, then $\frac{|E\cap
K_{3}[V_{i},V_{j},V_{k}]|}{|K_{3}[V_{i},V_{j},V_{k}]}\in[0,\epsilon)\cup(1-\epsilon,1]$.

Enumerate the sets $A=\\{a_{i}:i\in[n]\\}$, $B=\\{b_{i}:i\in[n]\\}$, and
$C=\\{c_{i}:i\in[n]\\}$. For each $X\in\\{A,B,C\\}$, let
$X_{sm},X_{sm}^{+},X_{lg},X_{lg}^{+}$ be as in Definition 6.25. Set
$\epsilon_{3}=\epsilon^{1/8}$. We will use throughout that $t\geq
t_{0}\gg\epsilon^{-1}$, and that each $V_{i}$ is very large (since
$|V_{i}|=(3n/t)\pm 1$ and $t\leq T$).

We say that a pair $xy\in{V\choose 2}$ is a _non- $\Sigma$ pair_ if $xy\in
K_{2}[V_{i},V_{j}]$ for some $V_{i}V_{j}\in{\mathcal{P}\choose
2}\setminus\Sigma$. On the other hand, we say $xy$ is a _$\Sigma$ -pair_ if
$xy\in K_{2}[V_{i},V_{j}]$ for some $V_{i}V_{j}\in\Sigma$. Since
$|\Sigma|\leq\epsilon t^{2}$, the number of non-$\Sigma$ pairs is at least

${|V|\choose 2}-\sum_{i=1}^{t}{|V_{i}|\choose
2}-\sum_{ij\in\Sigma}|V_{i}||V_{j}|\geq{|V|\choose
2}-|V|^{2}/t-\epsilon|V|^{2}\geq(1-2\epsilon){|V|\choose 2},$

there the last inequality uses that $t\geq t_{0}$, and that $|V|$ is large.
For each $1\leq i\leq t$, set

$A_{i}=A^{*}\cap V_{i},\text{ }B_{i}=B^{*}\cap V_{i},\text{ and
}C_{i}=C^{*}\cap V_{i}.$

Given $i\in[t]$ and $X\in\\{A,B,C\\}$, we say $X_{i}$ is _trivial_ if
$|X_{i}|<\epsilon_{3}|V_{i}|$, and 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, the number of trivial
vertices in $V_{i}$ is at most $2\epsilon_{3}|V_{i}|$. Consequently, at most
$4\epsilon_{3}N$ vertices are trivial. For each $X\in\\{A,B,C\\}$, let

$\mathcal{I}_{X}:=\\{i\in[t]:X_{i}\text{ is non-trivial}\\}.$

Since all but at most $4\epsilon_{3}N$ vertices are non-trivial,

(9)
$\displaystyle\Big{|}\bigcup_{i\in\mathcal{I}_{X}}X_{i}\Big{|}\geq(1-12\epsilon_{3})|X|,$

and consequently,
$|\mathcal{I}_{X}|\geq(1-12\epsilon_{3})|X|/(N/t)\geq(1-12\epsilon_{3})t/3$,
for each $X\in\\{A,B,C\\}$. We now turn to the sets of pairs which are in some
sense “error pairs” with respect to the partition $\\{V_{1},\ldots,V_{t}\\}$.
In particular, we define

$\displaystyle\mathcal{S}_{1}$
$\displaystyle=\\{X_{i}Y_{j}:i,j\in[t],XY\in{\\{A,B,C\\}\choose 2}\text{ and
either }i=j,\text{ or one of }X_{i},Y_{j}\text{ is trivial}\\},\text{ and }$
$\displaystyle\mathcal{S}_{2}$
$\displaystyle=\\{X_{i}Y_{j}\notin\mathcal{S}_{1}:V_{i}V_{j}\in\Sigma\\}.$

Set $\mathcal{S}=\mathcal{S}_{1}\cup\mathcal{S}_{2}$. Note that
$|\mathcal{S}_{2}|\leq 3|\Sigma|\leq 3\epsilon t^{2}$. Using (9), we have that

(10) $\displaystyle|\mathcal{S}|\leq
3|\Sigma|+3t+t\Big{|}\bigcup_{i\notin\mathcal{I}_{X}}X_{i}\Big{|}/(N/t)\leq
13\epsilon_{3}t^{2},$

where the last inequality uses that $t\gg t_{0}\gg\epsilon^{-1}$. We think of
the set $\mathcal{S}$ as controlling all potential error triples. Indeed, we
will show that any triple $A_{i}B_{j}C_{k}$ avoiding $\mathcal{S}$ will be
somewhat homogenous with respect to $H$. Specifically, we claim that if
$A_{i}B_{j}C_{k}$ has $A_{i}B_{j},A_{i}C_{k},B_{j}C_{k}\notin\mathcal{S}$,
then $A_{i}B_{j}C_{k}$ is $\sqrt{\epsilon}\mu^{8}$-homogeneous with respect to
$H$. Suppose towards a contradiction that
$A_{i}B_{j},A_{i}C_{k},B_{j}C_{k}\notin\mathcal{S}$, but $|E\cap
K_{3}[A_{i},B_{j},C_{k}]|/|A_{i}||B_{j}||C_{k}|\in(\sqrt{\epsilon}\mu^{8},1-\sqrt{\epsilon}\mu^{8})$.
Since $A_{i}B_{j},A_{i}C_{k},B_{j}C_{k}\notin\Sigma$, by assumption, there is
$u\in\\{0,1\\}$ such that $|E^{u}\cap
K_{3}[V_{i},V_{j},V_{k}]|\geq(1-\epsilon)|V_{i}||V_{j}||V_{k}|$. But we also
have

$|K_{3}[V_{i},V_{j},V_{k}]\setminus
E^{u}|\geq\sqrt{\epsilon}|K_{3}[A_{i},B_{j},C_{k}]|\geq\epsilon^{1/2}\mu^{8}\epsilon_{3}^{3}|V_{i}||V_{j}||V_{k}|>\epsilon|V_{i}||V_{j}||V_{k}|,$

where the last inequality is by our choice of $\epsilon\ll\mu$. This
contradicts that $|E^{u}\cap
K_{3}[V_{i},V_{j},V_{k}]|\geq(1-\epsilon)|V_{i}||V_{j}||V_{k}|$. Thus any
triple $A_{i}B_{j}C_{k}$ avoiding $\mathcal{S}$ is
$\sqrt{\epsilon}\mu^{8}$-homogenous with respect to $H$.

Eventually, we will contradict (10). We will use the following definition.
Given $X\in\\{A,B,C\\}$ and $i\in[t]$, set

$Irr(X_{i})=\\{Y_{j}Z_{k}:X_{i}Y_{j},X_{i}Z_{k}\notin\mathcal{S},|E\cap
K_{3}[X_{i},Y_{j},Z_{k}]|/|K_{3}[X_{i},Y_{j},Z_{k}]|\in(\epsilon^{1/2}\mu^{8},1-\epsilon^{1/2}\mu^{8})\\}.$

If $X_{i}$ is non-trivial, then our arguments above imply that if
$Y_{j}Z_{k}\in Irr(X_{i})$, then $Y_{j}Z_{k}\in\mathcal{S}$. Consequently, for
any non-trivial $X_{i}$, $|Irr(X_{i})|\leq 13\epsilon_{3}t^{2}$, and thus
$|\bigcup_{Y_{j}Z_{k}\in Irr(X_{i})}Y_{j}Z_{k}|\leq 39\epsilon_{3}n^{2}$.

It will be important to know that, based on our assumptions, the pairs in
$\mathcal{S}$ are somewhat constrained in their distibution. This is the
purpose of our next series of definitions. First, set

$\displaystyle
S_{1}=\bigcup_{X_{i}Y_{j}\in\mathcal{S}_{1}}K_{2}[X_{i},Y_{j}],\text{ and
}S_{2}=\bigcup_{X_{i}Y_{j}\in\mathcal{S}_{2}}K_{2}[X_{i},Y_{j}].$

By (9), we have that

$\displaystyle|S_{1}|\leq\sum_{i=1}^{t}t{V_{i}\choose
2}+\sum_{X\in\\{A,B,C\\}}\sum_{i\in\mathcal{I}_{X}}|X_{i}||V\setminus X|$
$\displaystyle\leq
t(3n/t)^{2}+2n\sum_{X\in\\{A,B,C\\}}\sum_{i\in\mathcal{I}_{X}}|X_{i}|$
$\displaystyle\leq 9n^{2}/t+6(12\epsilon_{3})n^{2}$ $\displaystyle\leq
61\epsilon_{3}n^{2},$

where the last inequality uses that $t\gg\epsilon^{-1}$. Given $X_{i}$, set

$\mathcal{S}_{1}(X_{i}):=\\{Y_{j}:X_{i}Y_{j}\in\mathcal{S}_{1}\\}\text{ and
}S_{1}(X_{i})=\bigcup_{Y_{j}\in\mathcal{S}_{1}(X_{i})}Y_{j}.$

If $X_{i}$ is non-trivial, then using the above and our bound on the number of
non-trivial vertices, we have

$|S_{1}(X_{i})|\leq|V_{i}\setminus
X_{i}|+|\bigcup_{j\notin\mathcal{I}_{Y}}Y_{j}\cup\bigcup_{j\notin\mathcal{I}_{Z}}Z_{j}|\leq|V_{i}|+4\epsilon_{3}N\leq
7\epsilon_{3}(2n)=14\epsilon_{3}n.$

Because $|\mathcal{S}_{2}|\leq 3\epsilon t^{2}$, $|S_{2}|\leq 9\epsilon
n^{2}$. Similar to the above, given $X_{i}$, we set

$\mathcal{S}_{2}(X_{i})=\\{Y_{j}:X_{i}Y_{j}\in\mathcal{S}_{2}\\}\text{ and
}S_{2}(X_{i})=\bigcup_{Y_{j}\in\mathcal{S}_{2}(X_{i})}Y_{j}.$

To deduce that $S_{2}(X_{i})$ is small, it is not enough to just know that
$X_{i}$ is non-trivial. This is the motivation of the next definition. Given
$X\in\\{A,B,C\\}$, define

$Gd(X):=\\{x\in X:x\text{ is non-trivial and }|\\{y\in V\setminus X:xy\in
S_{2}\\}|\leq 3\sqrt{\epsilon}(2n)\\}.$

We say $x\in X$ is _good_ if $x\in Gd(X)$. Since $|S_{2}|\leq 9\epsilon
n^{2}$, we must have that for any $X\in\\{A,B,C\\}$,
$|Gd(X)|\geq(1-3\epsilon^{1/2})n$. Given $X\in\\{A,B,C\\}$ and $i\in[t]$, we
say that $X_{i}$ is _good_ if $X_{i}$ is non-trivial and $|X_{i}\cap
Gd(X)|\geq(1-(3\epsilon)^{1/3})|X_{i}|$. Note that for each $X\in\\{A,B,C\\}$,

$|\bigcup_{X_{i}\text{ not
good}}X_{i}|\leq|\bigcup_{i\notin\mathcal{I}_{X}}X_{i}|+\frac{|X\setminus
Gd(X)|}{(3\epsilon)^{1/3}\epsilon_{3}(3n/t)}\leq
12\epsilon_{3}|X|+3\epsilon^{1/2-1/3-1/8}|X|\leq 4\epsilon_{3}^{1/3}|X|.$

Thus, most of the elements in $X$ are in a good $X_{i}$. We claim that if
$X_{i}$ is good, then $|\mathcal{S}_{2}(X_{i})|\leq 4\epsilon^{5/24}t$.
Suppose $X_{i}$ is good. By definition,

$\displaystyle|\\{xy:x\in X,xy\in S_{2}\\}|\leq(3\sqrt{\epsilon})2n|X_{i}\cap
Gd(X)|+2n|X_{i}\setminus Gd(X)|$ $\displaystyle\leq
6\sqrt{\epsilon}n|X_{i}|+2n(3\epsilon)^{1/3}|X_{i}|$ $\displaystyle\leq
12\epsilon^{1/3}|X_{i}|n.$

Note that if $Y_{j}\in\mathcal{S}_{2}(X_{i})$, then $Y_{j}$ is non-trivial so
$K_{2}[X_{i},Y_{j}]$ contains at least $|X_{i}|\epsilon_{3}(3n/t)$ many
elements of $S_{2}(X_{i})$. Consequently,

$|\mathcal{S}_{2}(X_{i})|\leq(12\epsilon^{1/3}|X_{i}|n)/(|X_{i}|\epsilon_{3}(3n/t))=4\epsilon^{5/24}t.$

This also shows that if $X_{i}$ is good, then
$|S_{2}(X_{i})|\leq(3n/t)4\epsilon^{5/24}t=12\epsilon^{5/24}n$. We have now
establishes the required properties about the distribution of $\mathcal{S}$.
We now turn to considering the implications of the axioms from Definition
6.25.

We say that $X_{i}$ is _mixed-degree_ if it is good, and moreover,

$|\\{x\in X_{i}:\min\\{|N(x)|,|\neg N(x)|\\}\geq\alpha
n^{2}\\}|\geq\epsilon_{3}^{1/10}|X_{i}|.$

Note that by the Degree Axiom, if a set $X_{i}$ is good and satisfies
$|X_{i}\cap(X_{sm}^{+}\cup X_{lg}^{+})|\geq\epsilon_{3}^{1/10}|X_{i}|$, then
$X_{i}$ is mixed degree. Our next goal is to show that every mixed-degree
$X_{i}$ is mostly contained in an open ball of small radius. Given
$\eta\in(0,1)$, define

$\\\ Mix(\eta,X_{i})=\\{yz\in YZ:|N_{H}(yz)|/|X_{i}|\in(\eta,1-\eta)\\}.$

We can already show that if $X_{i}$ is good, then ${\mathrm{Mix}}(\eta,X_{i})$
is not too large for certain values of $\eta$.

######  Claim 6.29.

If $X_{i}$ is good then $|{\mathrm{Mix}}(\epsilon^{1/4}\mu^{4},X_{i})|\leq
2\epsilon^{1/4}\mu^{4}n^{2}$.

###### Proof.

Recall that since $X_{i}$ is non-trivial, for any
$X_{i}Y_{j},X_{i}Y_{j}\notin\mathcal{S}$ and $Y_{j}Z_{k}\notin Irr(X_{i})$,
the triple $X_{i}Y_{j}Z_{k}$ is $\epsilon^{1/2}\mu^{8}$-homogeneous. Thus, for
any such $Y_{j},Z_{k}$, there is some $\eta\in\\{0,1\\}$ so that at least
$(1-\epsilon^{1/4}\mu^{4})|Y_{j}||Z_{k}|$ many elements $yz\in Y_{j}Z_{k}$
have $|N^{\eta}_{H}(yz)\cap X_{i}|\geq(1-\epsilon^{1/4}\mu^{4})|X_{i}|$. Using
the size estimates from earlier in the proof, and the fact that $X_{i}$ is
good, we have

$\displaystyle|{\mathrm{Mix}}(\epsilon^{1/4}\mu^{4},X_{i})|$
$\displaystyle\leq\epsilon^{1/4}\mu^{4}\Big{|}\bigcup_{Y_{j}Z_{k}\notin(\mathcal{S}_{1}(X_{i})\cup\mathcal{S}_{2}(X_{i}))\setminus
Irr(X_{i})}K_{2}[Y_{j},Z_{k}]\Big{|}+$
$\displaystyle+\Big{|}\bigcup_{Y_{j}Z_{k}\in
Irr(X_{i})}|K_{2}[Y_{j},Z_{k}]\Big{|}+n|S_{1}(X_{i})|+n|S_{2}(X_{i})|$
$\displaystyle\leq\epsilon^{1/4}\mu^{4}n^{2}+39\epsilon_{3}n^{2}+14\epsilon_{3}n^{2}+12\epsilon^{1/3}n^{2}$
$\displaystyle\leq 2\epsilon^{1/4}\mu^{4}n^{2},$

where the last inequality is because $\epsilon\ll\mu$. ∎

Claim 6.29 tells us that, for any mixed degree $X_{i}$, there is only a small
number of pairs $yz$ with $N(yz)\cap X_{i}$ and $\neg N(yz)\cap X_{i}$ both
being large. On the other hand, because $X_{i}$ has mixed degree, its vertices
are involved in many edges as well as many non-edges. This suggests that there
must be many pairs $yz$ for which $N(yz)\cap X_{i}$ is most of $X_{i}$, as
well as many pairs $yz$ for which $\neg N(yz)\cap X_{i}$ is almost all of
$X_{i}$. This idea is important for the rest of the proof.

Consider the following sets.

$\displaystyle\Gamma^{0}(X_{i})$ $\displaystyle:=\\{yz\in K_{2}[Y,Z]:|(\neg
N(yz))\cap X_{i}|\geq(1-2\epsilon^{1/4})|X_{i}|\\}\text{ and }$
$\displaystyle\Gamma^{1}(X_{i})$ $\displaystyle:=\\{yz\in
K_{2}[Y,Z]:|N(yz)\cap X_{i}|\geq(1-2\epsilon^{1/4})|X_{i}|\\}.$

Note that
${\mathrm{Mix}}(2\epsilon^{1/4},X_{i})=K_{2}[Y,Z]\setminus(\Gamma^{0}(X_{i})\cup\Gamma^{1}(X_{i}))$.
Define

$\displaystyle Q(X_{j})=\\{yzz^{\prime}\in K_{3}[Y,Z,Z]:$ $\displaystyle
yz\in\Gamma^{1}(X_{i}),yz^{\prime}\in\Gamma^{0}(X_{i})\\}$
$\displaystyle\cup\\{yy^{\prime}z\in
K_{3}[Y,Y,Z]:yz\in\Gamma^{1}(X_{i}),y^{\prime}z\in\Gamma^{0}(X_{i})\\}.$

We show in our next claim that if $X_{i}$ is mixed-degree, then $Q(X_{i})$ is
nonempty. Later, we will use this, along with the Intersection Axiom, to
deduce that every mixed-degree $X_{i}$ is mostly contained in an open ball of
small radius.

######  Claim 6.30.

If $X_{i}$ is mixed-degree, then $Q(X_{i})$ is nonempty.

###### Proof.

Fix $X\in\\{A,B,C\\}$ and suppose $X_{i}$ is mixed-degree. Let $Y,Z$ be such
that $\\{X,Y,Z\\}=\\{A,B,C\\}$. Define

$J_{Y}=\\{Y_{j}:X_{i}Y_{j}\notin\mathcal{S}\\}\text{ and
}J_{Z}=\\{Z_{k}:X_{i}Z_{k}\notin\mathcal{S}\\}.$

Note that since $X_{i}$ is non-trivial, $Y_{j}\in J_{Y}$ if and only if $j\neq
i$, $Y_{j}$ is non-trivial and $Y_{j}\notin\mathcal{S}_{2}(X_{i})$.
Consequently, since $X_{i}$ is good,

$|J_{Y}|\geq|\mathcal{I}_{Y}|-1-|\mathcal{S}_{2}(X_{i})|\geq|\mathcal{I}_{Y}|-1-4\epsilon^{5/24}t\geq(1-13\epsilon_{3})|\mathcal{I}_{Y}|\geq(1-13\epsilon_{3})^{2}t/3,$

where the last inequality uses the fact that
$|\mathcal{I}_{Y}|\geq(1-12\epsilon_{3})t/3$. Similarly $Z_{k}\in J_{Z}$ if
and only if $k\neq i$, $Z_{k}$ is non-trivial and
$Z_{k}\notin\mathcal{S}_{2}(X_{i})$. A similar argument also shows
$|J_{Z}|\geq(1-13\epsilon_{3})|\mathcal{I}_{Z}|\geq(1-13\epsilon_{3})^{2}t/3$.
Define

$\displaystyle F_{0}$ $\displaystyle=\\{Y_{j}Z_{k}\in
K_{2}[J_{Y},J_{Z}]:|E\cap
K_{3}[X_{i},Y_{j},Z_{k}]|/|X_{i}||Y_{j}||Z_{k}|\leq\epsilon^{1/2}\\}\text{ and
}$ $\displaystyle F_{1}$ $\displaystyle=\\{Y_{j}Z_{k}\in
K_{2}[J_{Y},J_{Z}]:|E\cap K_{3}[X_{i},Y_{j},Z_{k}]|/|X_{i}||Y_{j}||Z_{k}|\geq
1-\epsilon^{1/2}\\}.$

Note that by the definition of $J_{Y},J_{Z}$, we have that if $Y_{j}Z_{k}\in
K_{2}[J_{Y},J_{Z}]\setminus(F_{1}\cup F_{0})$, then $Y_{j}Z_{k}\in
Irr(X_{i})$.

We claim that it suffices to show that either there is some
$Y_{j}Z_{k}Z_{k^{\prime}}$ with $Y_{j}Z_{k}\in F_{0}$ and
$Y_{j}Z_{k^{\prime}}\in F_{1}$, or there is some $Y_{j}Y_{j^{\prime}}Z_{k}$
with $Y_{j}Z_{k}\in F_{0}$ and $Y_{j^{\prime}}Z_{k}\in F_{1}$. Indeed, suppose
there exists some $Y_{j}Z_{k}Z_{k^{\prime}}$ with $Y_{j}Z_{k}\in F_{0}$ and
$Y_{j}Z_{k^{\prime}}\in F_{1}$. Since $Y_{j}Z_{k}\in F_{0}$, standard counting
arguments imply that there is a set $\Omega_{0}\subseteq Y_{j}$ of size at
least $(1-\epsilon^{1/4})|Y_{j}|$ such that for all $y\in\Omega_{0}$,

$|\\{zx\in K_{2}[Z_{k},X_{i}]:xyz\notin
E\\}|\geq(1-\epsilon^{1/4})|X_{i}||Z_{k}|.$

Similarly, since $Y_{j}Z^{\prime}_{k}\in F_{1}$, there is a set
$\Omega_{1}\subseteq Y_{j}$ of size at least $(1-\epsilon^{1/4})|Y_{j}|$ such
that for all $y\in\Omega_{1}$,

$|\\{zx\in K_{2}[Z_{k},X_{i}]:xyz\in
E\\}|\geq(1-\epsilon^{1/4})|X_{i}||Z_{k}|.$

Choose any $y_{\star}\in\Omega_{1}\cap\Omega_{0}$ (clearly
$\Omega_{0}\cap\Omega_{1}$ is nonempty, as its size is at least
$(1-2\epsilon^{1/4})|Y_{j}|$). Consider the bipartite graphs

$G_{0}=(Z_{k}\cup X_{i},N_{H}(y_{\star})\cap K_{2}[Z_{k},X_{i}])\text{ and
}G_{1}=(Z_{k^{\prime}}\cup X_{i},N_{H}(y_{\star})\cap
K_{2}[Z_{k^{\prime}},X_{i}]).$

By construction, the density of edges in $G_{0}$ is at most $\epsilon^{1/4}$,
and the density of edges in $G_{1}$ is at least $1-\epsilon^{1/4}$. Thus,
there exists a $z\in Z_{k}$ of degree at most $\epsilon^{1/4}|X_{i}|$ in
$G_{0}$, and there exists a $z^{\prime}\in Z_{k^{\prime}}$ with degree at
least $(1-\epsilon^{1/4})|X_{i}|$ in $G_{1}$. Now

$\min\\{|\neg N_{H}(y_{\star}z)\cap X_{i}|,|N_{H}(y_{\star}z^{\prime})\cap
X_{i}|\\}=\min\\{|N_{G_{1}}(z^{\prime})|,|N_{G_{0}}(z)|\\}\geq(1-\epsilon^{1/4})|X_{i}|,$

so $y_{\star}zz^{\prime}\in Q(X_{i})$. An symmetric argument shows that if
there is some $Y_{j}Y_{j^{\prime}}Z_{k}$ with $Y_{j}Z_{k}\in F_{0}$ and
$Y_{j^{\prime}}Z_{k}\in F_{1}$, then there exists some
$yy^{\prime}z_{\star}\in Q(X_{i})$. Thus we just need to show that either
there is some $Y_{j}Y_{j^{\prime}}Z_{k}$ with $Y_{j}Z_{k}\in F_{0}$ and
$Y_{j}Z_{k^{\prime}}\in F_{1}$, or there is some $Y_{j}Z_{k}Z_{k^{\prime}}$
with $Y_{j}Z_{k}\in F_{0}$ and $Y_{j^{\prime}}Z_{k}\in F_{1}$.

Suppose towards a contradiction that no such $Y_{j}Y_{j^{\prime}}Z_{k}$ or
$Y_{j}Z_{k}Z_{k^{\prime}}$ exist. Let $\mathcal{G}$ be the bipartite graph
$\mathcal{G}$ with vertex set $J_{Y}\cup J_{Z}$ and edge set $F_{1}$. Recall
that for all $Y_{j}Z_{k}\in(J_{Y}\times J_{Z})\setminus(F_{0}\cup F_{1})$, we
must have $Y_{j}Z_{k}\in Irr(X_{i})$. Consequently,

$|K_{2}[J_{Y},J_{Z}]\setminus(F_{0}\cup F_{1})|\leq 13\epsilon_{3}t^{2}\leq
100\epsilon_{3}|J_{Y}||J_{Z}|,$

where the last inequality uses our lower bounds on $|J_{Y}|,|J_{Z}|$.
Therefore, if we set

$\displaystyle J_{Y}^{\prime}$ $\displaystyle=\\{Y_{j}\in J_{Y}:|\\{Z_{k}\in
J_{Z}:Y_{j}Z_{k}\notin F_{0}\cup
F_{1}\\}|\leq\sqrt{100\epsilon_{3}}|J_{Z}|\\}\text{ and }$ $\displaystyle
J_{Z}^{\prime}$ $\displaystyle=\\{Z_{k}\in J_{Z}:|\\{Y_{j}\in
J_{Y}:Y_{j}Z_{k}\notin F_{0}\cup
F_{1}\\}|\leq\sqrt{100\epsilon_{3}}|J_{Y}|\\},$

then $|J_{Y}^{\prime}|\geq\sqrt{100\epsilon_{3}}|J_{Y}|$ and
$|J_{Z}^{\prime}|\geq\sqrt{100\epsilon_{3}}|J_{Z}|$. Because there does not
exist $Y_{j},Z_{k},Z_{k^{\prime}}$ with $Y_{j}Z_{k}\in F_{0}$ and
$Y_{j}Z_{k^{\prime}}\in F_{1}$, we have that for all $Y_{j}\in
J^{\prime}_{Y}$, either
$|N_{\mathcal{G}}(Y_{j})|\geq(1-\sqrt{100\epsilon_{3}})|J_{Z}|$ or
$|N_{\mathcal{G}}(Y_{j})|=0$. Similarly, because there does not exist
$Y_{j},Y_{j^{\prime}},Z_{k}$ with $Y_{j}Z_{k}\in F_{0}$ and
$Y_{j^{\prime}}Z_{k}\in F_{1}$, we have that for all $Z_{k}\in
J_{Z}^{\prime}$, either
$|N_{\mathcal{G}}(Z_{k})|\geq(1-\sqrt{100\epsilon_{3}})|J_{Z}|$ or
$|N_{\mathcal{G}}(Z_{k})|=0$. By Lemma 4.9, either $|F_{1}|\leq
2(100\epsilon_{3})^{1/4}|J_{Y}||J_{Z}|$ or
$|F_{1}|\geq(1-2(100\epsilon_{3})^{1/4})|J_{Y}||J_{Z}|$.

Suppose first that $|F_{1}|\leq 2(100\epsilon_{3})^{1/4}|J_{Y}||J_{Z}|$. Then

$\displaystyle|\bigcup_{x\in X_{i}}N_{H}(x)|$
$\displaystyle\leq|X_{i}|\Big{|}\bigcup_{Y_{j}Z_{k}\notin F_{0}\cup
F_{1}}K_{2}[Y_{j},Z_{k}]\Big{|}+\sum_{Y_{j}Z_{k}\in
F_{1}}|X_{i}||Y_{j}||Z_{k}|+\sum_{Y_{j}Z_{k}\in F_{0}}|E\cap
K_{3}[X_{i},Y_{j},Z_{k}]|$
$\displaystyle\leq|X_{i}|39\epsilon_{3}n^{2}+|F_{1}|(3n/t)^{2}+\epsilon^{1/2}|J_{Y}||J_{Z}|(3n/t)^{2}$
$\displaystyle\leq|X_{i}|\Big{(}39\epsilon_{3}n^{2}+3(100\epsilon_{3})^{1/4}t^{2}(3n/t)^{2}+\epsilon^{1/2}t^{2}(3n/t)^{2}\Big{)}$
$\displaystyle=|X_{i}|n^{2}\Big{(}39\epsilon_{3}n^{2}+27(100\epsilon_{3})^{1/4}+9\epsilon^{1/2}\Big{)}$
$\displaystyle\leq\epsilon^{1/5}_{3}|X_{i}|n^{2},$

where the last inequality is because $\epsilon$ is small. This implies that
there is a set $X_{i}^{\prime}\subseteq X_{i}$ such that
$|X_{i}^{\prime}|\geq(1-\epsilon_{3}^{1/10})|X_{i}|$, and such that for all
$x\in X_{i}^{\prime}$, $|N_{H}(x)|\leq\epsilon_{3}^{1/10}n^{2}<\alpha n^{2}$,
but this contradicts that $X_{i}$ is mixed degree.

Suppose on the other hand that
$|F_{1}|\geq(1-2(100\epsilon_{3})^{1/4})|J_{Y}||J_{Z}|$. Note that

$\displaystyle\Big{|}\bigcup_{Y_{j}Z_{k}\notin
F_{1}}K_{2}[Y_{j},Z_{k}]\Big{|}$
$\displaystyle\leq\Big{|}\bigcup_{Y_{j}Z_{k}\notin F_{0}\cup
F_{1}}K_{2}[Y_{j},Z_{k}]\Big{|}+\Big{|}\bigcup_{Y_{j}Z_{k}\in
F_{0}}K_{2}[Y_{j},Z_{k}]\Big{|}$ $\displaystyle\leq
39\epsilon_{3}n^{2}+2(100\epsilon_{3})^{1/4}t^{2}\Big{(}\frac{3n}{t}\Big{)}^{2}$
$\displaystyle\leq\epsilon_{3}^{1/5}n^{2}/2,$

where the last inequality is because $\epsilon$ is small. Consequently, we
have that

$|\bigcup_{x\in X_{i}}N_{H}(x)|\geq(1-2\epsilon^{1/4})\sum_{Y_{j}Z_{k}\in
F_{1}}|Y_{j}||Z_{k}|\geq(1-\epsilon^{1/2})n^{2}(1-\epsilon_{3}^{1/5}/2)\geq
n^{2}(1-\epsilon^{1/5}_{3}).$

From this we deduce there is a set $X_{i}^{\prime}\subseteq X_{i}$ of size at
least $(1-\epsilon_{3}^{1/10})|X_{i}|$, so that for all $x\in X_{i}^{\prime}$,
$|N_{H}(x)|\geq(1-\epsilon_{3}^{1/10})n^{2}>(1-\alpha)n^{2}$, contradicting
that $X_{i}$ is mixed-degree. This finishes the proof of Claim 6.30. ∎

We now deduce that every mixed-degree $X_{i}$ is mostly contained in an open
ball. Given a mixed-degree $X_{i}$, define

$D(X_{i})=\\{d>0:\text{there is $yzz^{\prime}\in Q(X_{i})$ with
$d(z,z^{\prime})=d$ or $yy^{\prime}z\in Q(X_{i})$ with
$d(y,y^{\prime})=d$}\\}.$

Since $D(X_{i})$ is nonempty by Claim 6.30 (and $V$ is finite), we may choose
$d_{X_{i}}:=\min D(X_{i})$ and define a ball $B_{X_{i}}$ as follows. If
$d_{X_{i}}$ is witnessed by some $yy^{\prime}z^{\prime}\in Q(X_{i})$, let
$\rho_{X_{i}}\leq d_{X_{i}}$ be minimal such that for some $x$, $N(yz)\cap\neg
N(y^{\prime},z)\subseteq\overline{B_{\rho_{X_{i}}}(x)}$ (such an $x$ and
$\rho_{X_{i}}$ exist by the Intersection Axiom). If on the other hand,
$d_{X_{i}}$ is witnessed by some $yzz^{\prime}\in Q(X_{i})$, let
$\rho_{X_{i}}\leq d_{X_{i}}$ be minimal such that for some $x$, $N(yz)\cap\neg
N(y,z^{\prime})\subseteq\overline{B_{\rho_{X_{i}}}(x)}$ (again such an $x$ and
$\rho_{X_{i}}$ exists by the Intersection Axiom). In either case, set
$B_{X_{i}}=\overline{B_{\rho_{X_{i}}}(x)}$, and note $|X_{i}\cap
B_{X_{i}}|\geq(1-2\epsilon^{1/4})|X_{i}|$. Combining this with the Size Axiom
and the fact that $X_{i}$ is non-trivial (since it is good) we have that

$(1-2\epsilon^{1/4})\epsilon_{3}(3n/t)\leq|B_{X_{i}}|\leq p\rho_{X_{i}}n,$

and thus, $\rho_{X_{i}}\geq(1-2\epsilon^{1/4})t^{-1}p^{-1}\epsilon_{3}>50\rho
p^{50}$, where the last inequality is because $t\leq T$ and by our choice of
$\rho$.

We say $X_{i}$ is _sm-interesting_ if it is good and $|X_{i}\cap
X_{sm}|\geq\epsilon_{3}^{1/10}|X_{i}|$. Similarly, we say $X_{i}$ is _lg-
interesting_ if it is good and $|X_{i}\cap
X_{lg}|\geq\epsilon_{3}^{1/10}|X_{i}|$. We will say $X_{i}$ is simply
_interesting_ if it is either sm-interesting or lg-interesting. Note that by
the Degree Axiom, any interesting $X_{i}$ is automatically mixed-degree.
Therefore, when $X_{i}$ is sm-interesting, we can apply Claim 6.30 to find
$B_{X_{i}}$. In this case, we have that $|X_{i}\cap
B_{X_{i}}|\geq(1-2\epsilon^{1/4})|X_{i}|$ and $|X_{i}\cap
X_{sm}|\geq\epsilon_{3}^{1/10}|X_{i}|$. This implies that

$|X_{i}\cap B_{X_{i}}^{\prime}\cap
X_{sm}|\geq(\epsilon_{3}^{1/10}-2\epsilon^{1/4})|X_{i}|\geq\epsilon_{3}^{1/10}|X_{i}|/2>0.$

Thus, we may choose some $x_{i}\in X_{i}\cap B_{X_{i}}\cap X_{sm}$, and define
$B_{X_{i}}^{\prime}=B_{2\rho_{X_{i}}}(x_{i})$.

Similarly, when $X_{i}$ lg-interesting, $|X_{i}\cap
B_{X_{i}}|\geq(1-2\epsilon^{1/4})|X_{i}|$ and $|X_{i}\cap
X_{lg}|\geq\epsilon_{3}|X_{i}|$ imply

$|X_{i}\cap B_{X_{i}}^{\prime}\cap
X_{lg}|\geq(\epsilon_{3}^{1/10}-2\epsilon^{1/4})|X_{i}|\geq\epsilon_{3}^{1/0}|X_{i}|/2>0.$

Thus, we may choose some $x_{i}\in X_{i}\cap B_{X_{i}}\cap X_{lg}$, and define
$B_{X_{i}}^{\prime}=B_{2\rho_{X_{i}}}(x_{i})$.

We have now shown that when $X_{i}$ is sm-interesting (respectively lg-
interesting), there is an open ball $B_{X_{i}}^{\prime}$ of radius
$\rho_{X_{i}}^{\prime}:=2\rho_{X_{i}}\leq 2d_{X_{i}}$, with center $x_{i}\in
X_{sm}$ (respectively $x_{i}\in X_{lg}$), and so that $|X_{i}\cap
B^{\prime}_{X_{i}}|\geq(1-2\epsilon^{1/4})|X_{i}|$. Our next goal is to show
that this $\rho^{\prime}_{X_{i}}$ is not too big.

######  Claim 6.31.

If $X_{i}$ is interesting, then $\rho^{\prime}_{X_{i}}\leq\mu^{2}/2$.

###### Proof.

Suppose towards a contradiction there exists an interesting $X_{i}$ with
$\rho^{\prime}_{X_{i}}>\mu^{2}/2$. If $X_{i}$ is sm-interesting, set
$X_{*}=X_{sm}$ and $Y_{*}=Y_{lg}$ if $X_{i}$ is lg-interesting, set
$X_{*}=X_{lg}$ and $Y_{*}=Y_{sm}$.

By the Covering Axiom, there exists $\mathcal{Q}_{1}$ a collection of $m_{1}$
open balls of radius, each of radius at most $\mu^{2}/32$, and at least
$\mu^{2}/96$, each contained in $B_{X_{i}}^{\prime}$, such that $m_{1}\leq
2p(\mu^{2}/32)(\rho^{\prime}_{X_{i}})^{-1}$, and such that if
$\mathcal{Q}_{1}^{\prime}$ is set of elements of $\mathcal{Q}_{1}$ centered at
a point in $X_{*}^{+}$, then $|(B_{X_{i}}^{\prime}\cap
X_{*})\setminus(\bigcup\mathcal{Q}_{1}^{\prime})|\leq 2m_{1}$. Note that by
assumption, $m_{1}\leq 2p(\mu^{2}/32)(\rho^{\prime}_{X_{i}})^{-1}\leq 2p$. By
the pigeonhole principle, there is
$B_{r_{1}}(x^{\prime})\in\mathcal{Q}_{1}^{\prime}$ such that

$|B_{r_{1}}(x^{\prime})\cap X_{*}\cap
X_{i}|\geq\Big{(}\epsilon_{3}^{1/10}|X_{i}|/2-2m_{1}\Big{)}/m_{1}\geq\epsilon_{3}^{1/10}|X_{i}|/4p,$

where the last inequality is because $m_{1}\leq 2p\ll|X_{i}|$. We claim

$|B_{\mu^{2}/16}(x^{\prime})\cap X_{i}|<(1-2\epsilon^{1/4})|X_{i}|.$

Suppose towards a contradiction $|B_{\mu^{2}/16}(x^{\prime})\cap
X_{i}|\geq(1-2\epsilon^{1/4})|X_{i}|$. Choose any $y\in Y_{*}$. By Splitting
Axiom 1, there exist $z_{0},z_{1}\in Z$ such that $d(z_{0},z_{1})\leq
3\mu^{2}/16$ such that $B_{\mu^{2}/16}(x^{\prime})\subseteq
N_{H}(z_{1}y)\cap\neg N_{H}(z_{0}y)$. But now $yz_{1}z_{0}\in Q(X_{i})$, so
$d(z_{1},z_{0})\in D(X_{i})$. But
$d(z_{0},z_{1})<\mu^{2}/4<\rho^{\prime}_{X_{i}}/2=\rho_{X_{i}}$, a
contradiction to the definition of $\rho_{X_{i}}$.

Thus $|B_{\mu^{2}/16}(x^{\prime})\cap X_{i}|<(1-2\epsilon^{1/4})|X_{i}|$. By
the Partition Axiom, there is a set $\mathcal{Q}_{2}$ of $m_{2}$ open balls,
each of radius at most $\mu^{2}/16$, and at least $\mu^{2}/48$, one of which
is $B_{\mu^{2}/16}(x^{\prime})$, such that $m_{2}\leq 16\cdot 4p\mu^{-2}$, and
such that $|X\setminus(\bigcup\mathcal{P})|\leq 2m_{2}$. Since
$|B_{\mu^{2}/16}(x^{\prime})\cap X_{i}|<(1-2\epsilon^{1/4})|X_{i}|$, by
pigeonhole, there is some $B_{r_{2}}(x^{\prime\prime})\in\mathcal{Q}_{2}$,
distinct from $B_{\mu^{2}/16}(x^{\prime})$, such that

$|X_{i}\cap
B_{r_{2}}(x^{\prime\prime})|\geq(2\epsilon^{1/4}|X_{i}|-2m_{2})/m_{2}\geq\frac{\epsilon^{1/4}\mu^{2}|X_{i}|}{16\cdot
2p}-2\geq\frac{\epsilon^{1/4}\mu^{2}|X_{i}|}{16\cdot 4p},$

where the last inequalities use the upper bound on $m_{2}$, and the fact that
$X_{i}$ is large. By the Covering Axiom, there exists a collection
$\mathcal{Q}_{3}$ of $m_{3}$ disjoint open balls, each of radius at most
$r_{2}/4$ and at least $r_{2}/12$, each contained in
$B_{r_{2}}(x^{\prime\prime})$, such that $m_{3}\leq 8p$, and such that
$|B_{r_{2}}(x^{\prime\prime})\setminus(\bigcup\mathcal{Q}_{3})|\leq 2m_{3}$.
By the pigeonhole principle, there is
$B_{r_{3}}(x^{\prime\prime\prime})\in\mathcal{Q}_{3}$ such that

$|X_{i}\cap
B_{r_{3}}(x^{\prime\prime\prime})|\geq(\epsilon^{1/4}\mu^{2}|X_{i}|/(16\cdot
4p)-2m_{3})/m_{3}\geq\frac{\epsilon^{1/4}\mu^{2}|X_{i}|}{16\cdot
32p^{2}}-2\geq\epsilon^{1/4}\mu^{4}|X_{i}|,$

where the last inequalities use the upper bound on $m_{3}$, the fact that
$\epsilon\ll\mu\ll 1$, and the fact that $X_{i}$ is large. Note that
$r_{2}>r_{3}\geq\rho$.

Now, since $B_{\mu^{2}/16}(x^{\prime})$ is disjoint from
$B_{r_{2}}(x^{\prime\prime})$ and $B_{r_{3}}(x^{\prime\prime\prime})\subseteq
B_{r_{2}}(x^{\prime\prime})$, we have that
$d(x^{\prime\prime\prime},x^{\prime})\geq\mu^{2}/16+r_{3}$. Set
$r^{\prime\prime}=d(x^{\prime\prime\prime},x^{\prime})-r_{1}-r_{3}$, and
$r_{0}=\min\\{r_{1},r_{3}\\}/3$. Recall $r_{1}\leq\mu^{2}/32$ and
$\mu^{2}/48\cdot 12\leq r_{2}/12\leq r_{3}\leq r_{2}/4\leq\mu^{2}/16\cdot 4$.
Consequently,

$d(x^{\prime\prime\prime},x^{\prime})\geq\mu^{2}/16+r_{3}>2\max\\{r_{1},r_{3}\\}.$

Therefore, by Splitting Axiom 2, there are is an open ball $B_{1}$ in $Y$ and
an open ball $B_{2}$ in $Z$, each of radius $r_{0}/3$, such that
$K_{3}[B_{1},B_{2},B_{r_{1}}(x^{\prime})]\subseteq E$ and
$K_{3}[B_{1},B_{2},B_{r_{3}}(x^{\prime\prime})]\subseteq\neg E$, or vice
versa. Since

$|B_{r_{1}}(x^{\prime})\cap X_{i}|\geq\epsilon_{3}^{1/10}|X_{i}|/4p\text{ and
}|B_{r_{3}}(x^{\prime\prime})\cap X_{i}|\geq\epsilon^{1/4}\mu^{4}|X_{i}|,$

we must have that
$K_{2}[B_{1},B_{2}]\subseteq{\mathrm{Mix}}(\epsilon^{1/4}\mu^{4},X_{i})$.
Since $r_{1}\geq\mu^{2}/96$ and $r_{3}\geq\mu^{2}/(48\cdot 12)$, we have
$r_{0}/3\geq\mu^{2}/(48\cdot 36)$, so the Size Axiom implies we have

$\min\\{|B_{1}|,|B_{2}|\\}\geq\mu^{2}n/(48\cdot 36)(2p)=\mu^{2}n/(96\cdot
36p).$

Consequently

$|{\mathrm{Mix}}(\epsilon^{1/4}\mu^{4},X_{i})|\geq|K_{2}[B_{1},B_{2}]|\geq\frac{\mu^{4}n^{2}}{(96\cdot
36p)^{2}}.$

However, since $X_{i}$ is good, Claim 6.29 implies
$|{\mathrm{Mix}}(\epsilon^{1/4}\mu^{4},X_{i})|\leq
2\epsilon^{1/4}\mu^{4}n^{2}$. Because we chose $\epsilon\ll\mu$,
$2\epsilon^{1/4}\mu^{4}n^{2}<\frac{\mu^{4}n^{2}}{(96\cdot 36p)^{2}}$, so this
is a contradiction. This finishes the proof of Claim 6.31. ∎

Note that Claim 6.31 tells us that if $X_{i}$ is sm-interesting, then since
the center of $B_{X_{i}}^{\prime}$ is in $X_{sm}$ and the radius of
$B_{X_{i}}^{\prime}$ is less than $\mu^{2}/2$, $B_{X_{i}}^{\prime}\subseteq
X_{sm}^{+}$. Consequently $|B_{X_{i}}^{\prime}\cap X_{i}\cap
X_{sm}^{+}|\geq(1-2\epsilon^{1/4})|X_{i}|$. Similarly if $X_{i}$ is lg-
interesting, then $B_{X_{i}}^{\prime}\subseteq X_{lg}^{+}$, and consequently
$|B_{X_{i}}^{\prime}\cap X_{i}\cap X_{lg}^{+}|\geq(1-2\epsilon^{1/4})|X_{i}|$.

Let $K^{lg}_{X}$ be the set of lg-interesting $X_{i}$, and let $K^{sm}_{X}$ be
the set of sm-interesting $X_{i}$. Using the above, we have that

$\displaystyle|X_{sm}\setminus(\bigcup_{X_{i}\notin
K^{sm}_{X}}X_{i})|\leq|\bigcup_{X_{i}\text{ not good}}X_{i}|+\sum_{X_{i}\text{
good},X_{i}\notin K^{sm}_{X}}|X_{i}\cap X_{sm}|$ $\displaystyle\leq
2\epsilon^{1/3}_{3}|X|+2\epsilon^{1/4}|X|$ $\displaystyle\leq
3\epsilon^{1/3}_{3}|X_{sm}|,$

where the last inequality is because $\epsilon\ll\mu$, and because, by the
Size and Special Sets Axioms, $|X_{sm}|\geq\mu|X|/3p$. Consequently,

(11) $\displaystyle|\bigcup_{X_{i}\in
K^{sm}_{X}}X_{i}|\geq|X_{sm}|(1-4\epsilon^{1/3}_{3}).$

A similar argument shows

(12) $\displaystyle|\bigcup_{X_{i}\in
K^{lg}_{X}}X_{i}|\geq|X_{lg}|(1-4\epsilon^{1/3}_{3}).$

Thus, for each $X\in\\{A,B,C\\}$, most of $X_{sm}$ is in an sm-interesting
$X_{i}$, and most of $X_{lg}$ is in an lg-interesting $X_{i}$.

######  Claim 6.32.

For each $X\in\\{A,B,C\\}$ and all interesting $X_{i}$, and for each
$u\in[3]$, there is a set $\phi_{u}(X_{i})$ of open balls in $X$ of radius at
most $\rho^{\prime}_{X_{i}}/p^{2+u}$, and at least
$\rho^{\prime}_{X_{i}}/3p^{2+u}$ such that the following holds for each
$u\in[3]$.

  1. (1)

For all $B\in\phi_{u}(X_{i})$, $B\subseteq B_{X_{i}}^{\prime}$,

  2. (2)

For each $B\in\phi_{u}(X_{i})$, $|X_{i}\cap
B|\geq(1-2\epsilon^{1/4})|X_{i}|/p^{3+u}$,

  3. (3)

For each $u\in[3]$,
$|X_{i}\cap(\bigcup_{B\in\phi_{u}(X_{i})}B)|\geq(1-3\epsilon^{1/4})|X_{i}|$.

###### Proof.

Suppose $X_{i}$ is interesting. If $X_{i}$ is lg-interesting, let
$X_{*}=X_{lg}$ and if sm-interesting, let $X_{*}=X_{sm}$.

By the Covering Axiom, for each $u\in[3]$, there is a set $\mathcal{P}_{u}$ of
$m_{u}\leq 2p^{3+u}$ disjoint open balls, each of some radius
$r_{u}\leq\rho^{\prime}_{X_{i}}/p^{2+u}$, such that
$|B_{X_{i}}^{\prime}\setminus(\bigcup\mathcal{P}_{u})|\leq 2m_{u}$, and such
that each ball in $\mathcal{P}_{u}$ is contained in $B_{X_{i}}^{\prime}$. For
each $u\in[3]$, let

$\phi_{u}(X_{i})=\\{B_{\rho^{\prime}_{X_{i}}/p^{2+u}}(x^{\prime}):B_{\rho^{\prime}_{X_{i}}/p^{2+u}}(x^{\prime})\in\mathcal{P}_{u}\text{
and }|B_{\rho^{\prime}_{X_{i}}/p^{2+u}}(x^{\prime})\cap
X_{i}|\geq(1-2\epsilon^{1/4})|X_{i}|/m_{u}\\}.$

Note (1) and (2) hold by definition of $\phi_{u}(X_{i})$. We show (3). By,
assumption, $|B^{\prime}_{{X_{i}}}\setminus(\bigcup\mathcal{P}_{u})|\leq
2m_{u}$. Thus,

$|X_{i}\cap(\bigcup_{B^{\prime}\in\phi_{u}(X_{i})}B^{\prime})|\geq|X_{i}\cap
B_{X_{i}}^{\prime}|-2m_{u}\geq(1-2\epsilon^{1/4})|X_{i}|-4p^{3+u}\geq(1-3\epsilon^{1/4})|X_{i}|,$

where the last inequality is because $X_{i}$ is large. ∎

For ease of notation, given an interesting $X_{i}$ and $u\in\\{1,2,3\\}$, let
$P_{u}(X_{i})$ be the set of centers of the balls in $\phi_{u}(X_{i})$, and
let $\Psi_{u}(X_{i})=\bigcup_{B^{\prime}\in\phi_{u}(X_{i})}B^{\prime}$. Note
that $P_{u}(X_{i})\subseteq X_{sm}^{+}$ when $X_{i}$ is sm-interesting, and
$P_{u}(X_{i})\subseteq X_{lg}^{+}$ when $X_{i}$ is lg-interesting.

Our next claim is crucial to the overall argument. The basic idea is that for
certain sm-ineresting $Y_{j}$, and any lg-interesting $X_{i}$, then, given any
$B^{\prime}\in\phi_{2}(X_{i})$ and $B^{\prime\prime}\in\phi_{2}(Y_{j})$, there
is a ball
$B^{\prime\prime\prime}=B^{\prime\prime\prime}(B^{\prime},B^{\prime\prime})$
in $Z$, which is not too small, and such that
$K_{2}[B^{\prime\prime},B^{\prime\prime\prime}]$ contains many $xz$ which
“split” $Y_{j}\cap B^{\prime\prime}$, in the sense that both
$N(xz)\cap(Y_{j}\cap B^{\prime})$ and $\neg N(xz)\cap(Y_{j}\cap
B^{\prime\prime})$ are large. It will also be important to know this produces
different $B^{\prime\prime\prime}$ as we let $B^{\prime}$ and
$B^{\prime\prime}$ vary (see (i) and (ii) below).

######  Claim 6.33.

Suppose $X\neq Y\in\\{A,B,C\\}$, $Y_{j}$ is sm-interesting and $X_{i}$ is lg-
interesting.

  1. (1)

Suppose $\rho^{\prime}_{X_{j}}\geq\rho^{\prime}_{Y_{i}}$. Then for each
$x_{0}\in P_{2}(X_{i})$, and each $y_{0}\in P_{2}(Y_{j})$, there is
$f_{X_{i}Y_{j}Z}(x_{0}y_{0})\in Z$ so that for at least half the $x\in
B_{\rho^{\prime}_{X_{i}}/2p^{4}}(x_{0})\cap X_{i}$, and all the $z\in
B_{\rho^{\prime}_{X_{i}}/2p^{4}}(f_{Y_{j}X_{i}Z}(x_{0}y_{0}))$,
$xz\in{\mathrm{Mix}}(2\epsilon^{1/4}/p^{5},Y_{j})$.

  2. (2)

Suppose $\rho^{\prime}_{Y_{j}}\geq\rho^{\prime}_{X_{i}}$. Then for each
$x_{0}\in P_{2}(X_{i})$, and each $y_{0}\in P_{2}(Y_{j})$, there is
$f_{Y_{j}X_{i}Z}(y_{0}x_{0})\in Z$ so that for at least half the $y\in
B_{\rho^{\prime}_{Y_{j}}/2p^{4}}(y_{0})\cap Y_{j}$, and all the $z\in
B_{\rho^{\prime}_{Y_{j}}/2p^{4}}(f_{X_{i}Y_{j}Z}(y_{0}x_{0}))$,
$yz\in{\mathrm{Mix}}(2\epsilon^{1/4}/p^{5},X_{i})$.

Moreover, the following hold.

  1. (i)

If $X_{i},X_{i}$ are lg-interesting, and
$\rho^{\prime}_{X_{i}}\geq\rho^{\prime}_{X_{i^{\prime}}}\geq\rho^{\prime}_{Y_{j}}$,
then for all $x\in P_{2}(X_{i})$, $x^{\prime}\in P_{2}(X_{i^{\prime}})$ with
$d(x,x^{\prime})\geq 10\rho_{X_{i}}$, and all $y,y^{\prime}\in P_{2}(Y_{j})$,

$d(f_{X_{i}Y_{j}Z}(xy),f_{X_{i^{\prime}}Y_{j}Z}(x^{\prime}y^{\prime}))\geq
5\rho^{\prime}_{X_{i}}.$

  2. (ii)

If $Y_{j},Y_{j^{\prime}}$ are sm-interesting, and
$\rho^{\prime}_{Y_{j}}\geq\rho^{\prime}_{Y_{j^{\prime}}}\geq\rho^{\prime}_{X_{i}}$,
then for all $y\in P_{2}(Y_{j})$, $y^{\prime}\in P_{2}(Y_{j^{\prime}})$ with
$d(y,y^{\prime})\geq 10\rho^{\prime}_{Y_{j}}$, and all $x,x^{\prime}\in
P_{2}(X_{i})$,

$d(f_{Y_{j}X_{i}Z}(yx),f_{Y_{j^{\prime}}X_{i}Z}(y^{\prime}x^{\prime}))\geq
5\rho^{\prime}_{Y_{j}}.$

###### Proof.

Assume first that $\rho^{\prime}_{X_{i}}\geq\rho^{\prime}_{Y_{j}}$. Suppose
$y_{0}\in P_{2}(Y_{j})$ and $x_{0}\in P_{2}(X_{i})$. By Claim 6.31,
$\rho^{\prime}_{X_{i}}\leq\mu^{2}/2$. Set $r=\rho_{X_{i}}^{\prime}/4p^{2}$ and
let $B^{\prime}=B_{r}(y_{0})$ and $B^{\prime\prime}=B_{r}(x_{0})$. Apply
Splitting Axiom 1 to obtain $z_{0}=f_{0}(r,x_{0},y_{0})$ and
$z_{1}=f_{1}(r,x_{0},y_{0})$, so that so that for each $\eta\in\\{0,1\\}$,
$B_{r/2}(z_{\eta})\times B^{\prime}\times B^{\prime\prime}\subseteq E^{\eta}$
and $d(z_{0},z_{1})\leq 3r$. Suppose there were $y\in Y$, $z\in
B_{r/2}(z_{0})$, and $z^{\prime}\in B_{r/2}(z_{0})$ such that
$(y,z)\in\Gamma_{1}(X_{i})$ and $(y,z^{\prime})\in\Gamma_{0}(X_{i})$, or vice
versa. Then we would have $yzz^{\prime}\in Q(X_{i})$, contradicting our choice
of $\rho_{X_{i}}$ (since $d(z,z^{\prime})<4r\leq\rho_{X_{i}}$). Thus, for all
$y\in Y$, there is $\xi=\xi(u)\in\\{0,1\\}$ such that

$(\\{y\\}\times B_{r/2}(z_{1}))\cup(\\{y\\}\times
B_{r/2}(z_{0}))\subseteq{\mathrm{Mix}}(2\epsilon^{1/4},X_{i})\cup\Gamma_{\xi}(X_{i}).$

Let $B(1)=\\{y\in B^{\prime}\cap Y_{j}:\xi(y)=1\\}$ and $B(0)=\\{y\in
B^{\prime}\cap Y_{j}:\xi(y)=0\\}$. Then

$\max\\{|B(0)|,|B(1)|\\}\geq|B^{\prime}\cap Y_{j}|/2.$

Choose $\xi^{*}\in\\{0,1\\}$ so that $|B(\xi^{*})\cap
Y_{j}|\geq|B^{\prime}\cap Y_{j}|/2$. Then for all $y\in B(\xi^{*})\cap Y_{j}$,
and all $z\in B_{|1-\xi^{*}|}(z_{|1-\xi^{*}|})$, one of the following holds.

  * •

$yz\in{\mathrm{Mix}}(2\epsilon^{1/4},X_{i})$. In this case, by definition,
$\min\\{|N(yz)\cap X_{i}|,|\neg N(yz)\cap X_{i}|\\}\geq
2\epsilon^{1/4}|X_{i}|$,

  * •

$yz\in\Gamma_{\xi^{*}}(X_{i})$. In this case
$|N^{\xi^{*}}(yz)|\geq(1-2\epsilon^{1/4})|X_{i}|$ (by definition of
$\Gamma_{\xi^{*}}(X_{i})$). Since $z\in B_{|1-\xi^{*}|}(z_{|1-\xi^{*}|})$, we
also know $|\neg N(yz)\cap X_{i}|\geq|B^{\prime\prime}\cap X_{i}|\geq
2\epsilon^{1/4}|X_{i}|/p^{5}$, where the last inequality is because
$B^{\prime\prime}\in\phi_{2}(X_{i})$.

This shows $(B(\xi^{*})\cap Y_{j})\times
B_{|1-\xi^{*}|}(z_{|1-\xi^{*}|})\subseteq{\mathrm{Mix}}(2\epsilon^{1/4}/p^{5},X_{i})$.
Define $f_{X_{i}Y_{j}Z}(y_{0}x_{0})=z_{|1-\xi^{*}|}$. This finishes the proof
of (1). The proof of (2) is symmetric, with the roles of $Y$ and $X$ switched
everywhere.

For (i), suppose $X_{i}$ and $X_{i^{\prime}}$ are lg-interesting, and
$\rho^{\prime}_{X_{i}}\geq\rho^{\prime}_{X_{i^{\prime}}}\geq\rho^{\prime}_{Y_{j}}$.
Suppose $x\in P_{2}(X_{i})$, $x^{\prime}\in P_{2}(X_{i^{\prime}})$ and
$y,y^{\prime}\in P_{2}(Y_{j})$ are such that $d(x,x^{\prime})\geq
10\rho^{\prime}_{X_{i}}$. Since we chose $f_{X_{i}Y_{j}Z}(xy)$ and
$f_{X_{i^{\prime}}Y_{j}Z}(x^{\prime}y^{\prime})$ using Splitting Axiom 1 with
$r=\rho_{X_{i}}^{\prime}/4p^{2}$ and
$r=\rho_{X_{i^{\prime}}}^{\prime}/4p^{2}$, respectively, we have by part (c)
of that axiom that, since
$d(y,y^{\prime})\leq\rho^{\prime}_{Y_{j}}\leq\rho^{\prime}_{X_{i}}$,

$d(f_{X_{i}Y_{j}Z}(xy),f_{X_{i^{\prime}}Y_{j}Z}(x^{\prime}y^{\prime}))\geq
d(x,x^{\prime})-d(y,y^{\prime})-7(\rho^{\prime}_{X_{i}}/4p^{4})\geq
5\rho^{\prime}_{X_{i}}.$

The proof of (ii) is symmetric, with the roles of $X$ and $Y$ switched
everywhere, and with Splitting Axiom part (b) in place of part (c).

∎

We are now ready to embark on the main argument of the proof. Given
$X\in\\{A,B,C\\}$, let $I_{X}(0)=K_{X}^{sm}\cup K_{X}^{lg}$. Then for $X\neq
Y$, define

$\displaystyle M^{Y}(X_{i})$ $\displaystyle=\\{Y_{j}\in
I_{Y}(0):X_{i}Y_{j}\notin\mathcal{S}\text{ and
}\rho^{\prime}_{Y_{j}}\leq\rho^{\prime}_{X_{i}}\\}.$

We will construct an integer $t^{*}$, and for each $1\leq u\leq t^{*}$ and a
collection of objects $w_{u}$, $W_{u}$, $\mathcal{S}_{W_{u}}$ and
$L_{X}(u),I_{X}(u),J_{X}(u)$ for each $X\in\\{A,B,C\\}$ so that the following
hold.

  1. (1)

For each $1\leq u\leq t^{*}$, $W_{u}\in I_{A}(0)\cup I_{B}(0)\cup I_{C}(0)$,
and $w_{u}\in P_{2}(W_{u})$,

  2. (2)

For each $1\leq u\leq t^{*}$ and $X\in\\{A,B,C\\}$,
$L_{X}(u)=\\{W_{1},\ldots,W_{u}\\}\cap I_{X}(0)$, and

$\displaystyle I_{X}(u)$ $\displaystyle=\\{X_{s}\in I_{X}(0)\setminus
L_{X}(u):X_{s}\in M^{X}(W_{u})\text{ for all }W_{u}\in L_{Y}(u)\text{ with
}Y\neq X\\},$ $\displaystyle J_{X}(u)$ $\displaystyle=\\{X_{s}\in
I_{X}(u):\text{ for all }X_{i}\in L_{X}(u),d_{X}(x_{s},x_{i})\geq
10\rho^{\prime}_{X_{i}}\\}.$

  3. (3)

For each $1\leq u\leq t^{*}$ and $X\in\\{A,B,C\\}$, if $W_{u}\in I_{X}(0)$ and
$YZ$ lists $\\{A,B,C\\}\setminus\\{X\\}$ in alphabetical order, the following
hold. If $W_{u}$ is lg-interesting, then

$\displaystyle\mathcal{S}_{W_{u}}=\\{Y_{j}Z_{k}\in
K_{2}[J_{Z}(u),J_{Y}(u)]:Y_{j}\in K_{Y}^{sm},$ $\displaystyle\text{ and for
some }y\in P_{2}(Y_{j}),$ $\displaystyle\Psi_{3}(Z_{k})\cap
B_{\rho^{\prime}_{W_{u}}/4}(f_{W_{u}Y_{j}Z}(w_{u}y))\neq\emptyset\\},$

and if $W_{u}$ is sm-interesting, then

$\displaystyle\mathcal{S}_{W_{u}}=\\{Y_{j}Z_{k}\in
K_{2}[J_{Z}(u),J_{Y}(u)]:Y_{j}\in K_{Y}^{lg}$ $\displaystyle\text{ and for
some }y\in P_{2}(Y_{j}),$ $\displaystyle\Psi_{3}(Z_{k})\cap
B_{\rho^{\prime}_{W_{u}}/4}(f_{W_{u}Y_{j}Z}(w_{u}y))\neq\emptyset\\}.$

  4. (4)

For each $1\leq u\leq t^{*}$, $\mathcal{S}_{W_{u}}\subseteq\mathcal{S}$ and
$|\mathcal{S}_{W_{u}}|\geq(1-\sqrt{\epsilon})\epsilon_{3}^{1/4}\rho^{\prime}_{W_{u}}t/2$.

  5. (5)

For all $1\leq u\neq u^{\prime}\leq t^{*}$,
$\mathcal{S}_{W_{u}}\cap\mathcal{S}_{W_{u^{\prime}}}=\emptyset$.

  6. (6)

For some $X\in\\{A,B,C\\}$, $|\bigcup_{X_{v}\in
L_{X}(t_{0})}B^{\prime}_{X_{v}}|\geq\epsilon^{1/16}n$.

Step 0: There is nothing to do, as this case is vacuous.

Step $i+1$: Suppose $i\geq 0$, and for each $1\leq u\leq i$, you have chosen
$W_{u}$, $\mathcal{S}_{W_{u}}$, and sets $L_{U}(u),I_{U}(u),J_{U}(u)$ for each
$U\in\\{A,B,C\\}$, such that (1)-(4) hold for each $1\leq u\leq i$, such that
(5) holds for each $1\leq u\neq u^{\prime}\leq i$, and such that (6) holds for
all $1\leq u<i$ (note the hypotheses say nothing if $i=0$).

If $|\bigcup_{U_{s}\in L_{U}(i)}B^{\prime}_{U_{s}}|\geq\epsilon^{1/16}n$ for
some $U\in\\{A,B,C\\}$, set $t^{*}=i$ and end the construction (clearly this
will not happen if $i=0$). Otherwise, we have that for each $U\in\\{A,B,C\\}$,
$|\bigcup_{U_{s}\in L_{U}(i)}B_{U_{s}}|<\epsilon^{1/16}n$. By the Size Axiom,
this implies that for each $U_{v}\in L_{U}(i)$, $\rho^{\prime}_{U_{v}}\leq
2p\epsilon^{1/16}n$. Consequently, using (12),

$\displaystyle\Big{|}\bigcup_{U_{s}\in
I_{U}(i)}U_{s}\Big{|}\geq\Big{|}\bigcup_{U_{s}\in
I_{U}(0)}U_{s}\Big{|}-|\bigcup_{U_{s}\in L_{U}(i)}B^{\prime}_{U_{s}}|$
$\displaystyle\geq|U_{lg}^{+}\cup
U_{sm}^{+}|(1-4\epsilon_{3}^{1/3})-\epsilon^{1/16}n$ (13)
$\displaystyle\geq|U_{lg}^{+}\cup U_{sm}^{+}|(1-5\epsilon_{3}^{1/3}).$

By our assumptions, for each $U\in\\{A,B,C\\}$ and each
$U_{i_{s}},U_{i_{v}}\in L_{U}(i)$,

$B_{10\rho^{\prime}_{U_{i_{s}}}}(u_{i_{s}})\cap
B_{10\rho^{\prime}_{U_{i_{v}}}}(u_{i_{v}})=\emptyset.$

Consequently, by the Size Axiom and the definition of $J_{U}(i)$,

$\displaystyle\Big{|}\bigcup_{U_{s}\in
J_{U}(i)}U_{s}\Big{|}\geq\Big{|}\bigcup_{U_{s}\in
I_{U}(0)}U_{s}\Big{|}-|\bigcup_{U_{i_{s}}\in
L_{U}(i)}B_{10\rho^{\prime}_{U_{i_{s}}}}(u_{i_{s}})|$
$\displaystyle\geq|U_{lg}^{+}\cup
U_{sm}^{+}|(1-5\epsilon_{3}^{1/3})-10p\epsilon^{1/16}n$ (14)
$\displaystyle\geq|U_{lg}^{+}\cup U_{sm}^{+}|(1-6\epsilon_{3}^{1/3}).$

For each $U\in\\{A,B,C\\}$, set set
$r_{i+1}^{U}=\max\\{\rho^{\prime}_{U_{j}}:U_{j}\in J_{U}(i)\\}$. Then define

$r_{i+1}=\max\\{r^{A}_{i+1},r_{i+1}^{B},r^{C}_{i+1}\\}.$

Choose $X\in\\{A,B,C\\}$ such that $r_{i+1}^{X}=r_{i+1}$, and any $j_{i+1}\in
J_{X}(i)$ such that $\rho^{\prime}_{X_{j_{i+1}}}=r_{i+1}$. Then define
$W_{i+1}:=X_{j_{i+1}}$, $L_{X}(i+1)=L_{X}(i)\cup\\{W_{i+1}\\}$, and for each
$U\neq X$, set $L_{U}(i+1)=L_{U}(i)$. For each
$U\in\\{A,B,C\\}\setminus\\{X\\}$, define $I_{U}(i+1)=M^{U}(W_{i+1})\cap
I_{U}(i)$ and $J_{U}(i+1)=J_{U}(i+1)\cap M^{U}(W_{i+1})$. Then set

$\displaystyle I_{X}(i+1):=I_{X}(i)\setminus\\{W_{i+1}\\}\text{ and
}I_{X}(i+1):=\\{X_{s}\in I_{X}(i+1):d(u_{s},x_{j_{i+1}})\geq
10\rho^{\prime}_{W_{i+1}}\\}.$

Let $YZ$ list the elements of $\\{A,B,C\\}\setminus X$ in alphabetical order,
and define

$\displaystyle K_{Y}^{sm}(i+1)$ $\displaystyle=\\{Y_{j}\in J_{Y}(i+1):\text{
$Y_{j}$ is sm-interesting}\\},\text{ and }$ $\displaystyle K_{Y}^{lg}(i+1)$
$\displaystyle=\\{Y_{j}\in J_{Y}(i+1):\text{ $Y_{j}$ is lg-interesting}\\}.$

Using (11) and (6.4), and since $J_{Y}(i+1)=J_{Y}(i)$,

$\displaystyle\Big{|}\bigcup_{Y_{j}\in
K_{Y}^{sm}(i+1)}Y_{j}\Big{|}\geq\Big{|}\bigcup_{Y_{j}\in
K^{sm}_{Y}(i+1)\setminus
J_{Y}(i+1)}Y_{j}\Big{|}\geq(1-6\epsilon_{3}^{1/3})|Y_{sm}|.$

A similar argument shows that

$\displaystyle\Big{|}\bigcup_{Y_{j}\in
K_{Y}^{lg}(i+1)}Y_{j}\Big{|}\geq(1-6\epsilon_{3}^{1/3})|Y_{lg}|.$

Consequently, combining this with the Size and Special Sets Axioms, and the
fact that $\epsilon\ll\mu,\tau$, we have

$|K_{Y}^{sm}(i+1)|\geq(\mu
n/2p)(1-6\epsilon_{3}^{1/3})/(3n/t)\geq\mu(1-6\epsilon_{3}^{1/3})t/6p\geq\mu
t/7p,$

and similarly $|K_{Y}^{lg}(i+1)|\geq\tau t/7p$. By construction, $W_{i+1}$ is
either lg-interesting or sm-interesting. If $W_{i+1}$ is lg-interesting, let
$Y_{*}=Y_{sm}$ and $K^{*}=K_{Y}^{sm}(i+1)$. If $W_{i+1}$ is sm-interesting,
let $Y_{*}=Y_{lg}$ and $K^{*}=K_{Y}^{lg}(i+1)$.

Fix $w_{i+1}\in P_{2}(W_{i+1})$. Given $Y_{j}\in K^{*}$ and $y\in
P_{2}(Y_{j})$, consider $B_{r_{i+1}/4}(f_{W_{i+1}Y_{j}Z}(w_{i+1}y))$ as in
Claim 6.33. Note that if $Z_{k}\in J_{Z}(i+1)$,
$B^{\prime\prime}\in\phi_{3}(Z_{k})$, and $B^{\prime\prime}\cap
B_{r_{i+1}/4}(f_{W_{i+1}Y_{j}Z}(w_{i+1}y))\neq\emptyset$, then
$B^{\prime\prime}\subseteq B_{r_{i+1}/2}(f_{W_{i+1}Y_{j}Z}(w_{i+1}y))$ (since
by construction, $r_{i+1}=\rho^{\prime}_{W_{i+1}}\geq\rho^{\prime}_{Z_{k}}$).
Thus, for all such $Z_{k}$, we have by Claim 6.33 that

$|E\cap
K_{3}[Z_{k},W_{i+1},Y_{j}]|/|K_{3}[Z_{k},W_{i+1},Y_{j}]|\in(\epsilon^{1/4}\mu^{4}/2,1-\epsilon^{1/4}\mu^{4}/2).$

Since we assumed $Y_{j}\in J_{Y}(i+1)\subseteq M^{Y}(W_{i+1})$,
$W_{i+1}Y_{j}\notin\mathcal{S}$. Therefore, if
$W_{i+1}Z_{k}\notin\mathcal{S}$, and $Z_{k}$ is as above, then we would have
to have $Y_{j}Z_{k}\in Irr(W_{i+1})$. Thus, if $Z_{k}\in J_{Z}(i+1)$ and
$\Psi_{3}(Z_{k})\cap B_{r_{i+1}/4}(f_{W_{i+1}Y_{j}Z}(w_{i+1}y))\neq\emptyset$,
then $Y_{j}Z_{k}\in Irr(W_{i+1})$. Let $\mathcal{S}_{W_{i+1}Y_{j}}$ be the set
of pairs arising in this way for $Y_{j}$, i.e.

$\displaystyle\mathcal{S}_{W_{i+1}Y_{j}}=\\{Y_{j}Z_{k}:Z_{k}\in J_{Z}(i+1),$
$\displaystyle\text{ and for some }y\in P_{2}(Y_{j}),$
$\displaystyle\Psi_{3}(Z_{k})\cap
B_{r_{i+1}/4}(f_{W_{i+1}Y_{j}Z}(w_{i+1}y))\neq\emptyset\\}$

We have shown that for all $Y_{j}\in K^{*}$,
$\mathcal{S}_{W_{i+1}Y_{j}}\subseteq Irr(W_{i+1})$. Clearly
$|\mathcal{S}_{W_{i+1}Y_{j}}|\geq s_{j}$, where we define $s_{j}$ as follows.

$\displaystyle s_{j}:=\frac{|(\bigcup_{y\in
P_{2}(Y_{j})}B_{r_{i+1}/4}(f_{W_{i+1}Y_{j}Z}(w_{i+1}y))\cap(\bigcup_{Z_{k}\in
J_{Z}(i+1)}\Psi_{3}(Z_{k}))|}{|N/t|}.$

Note that for any $Y_{j}\in K^{*}$,

$\displaystyle\Big{|}\Big{(}\bigcup_{y\in
P_{2}(Y_{j})}B_{r_{i+1}/4}(f_{W_{i+1}Y_{j}Z}(w_{i+1}y))\setminus\Big{(}\bigcup_{Z_{k}\in
J_{Z}(i+1)}\Psi_{3}(Z_{k})\Big{)}\Big{|}$
$\displaystyle\geq\Big{|}\bigcup_{y\in
P_{2}(Y_{j})}B_{r_{i+1}/4}(f_{W_{i+1}Y_{j}Z}(w_{i+1}y))\Big{|}-s_{j}(N/t).$

By the Size Lemma, for each $y\in P_{2}(Y_{j})$,

$\displaystyle|B_{r_{i+1}/4}(f_{W_{i+1}Y_{j}Z}(w_{i+1}y))|\geq
r_{i+1}n/8p=\rho^{\prime}_{W_{i+1}}n/8p.$

Thus

$\displaystyle\Big{|}\Big{(}\bigcup_{y\in
P_{2}(Y_{j})}B_{r_{i+1}/4}(f_{W_{i+1}Y_{j}Z}(w_{i+1}y)\Big{)}\setminus\Big{(}\bigcup_{Z_{k}\in
J_{Z}(i+1)}\Psi_{3}(Z_{k})\Big{)}\Big{|}\geq\rho^{\prime}_{W_{i+1}}n/8p-s_{j}(N/t).$

Now define

$\mathcal{G}^{*}=\\{Y_{j}\in
K^{*}:s_{j}\geq\rho^{\prime}_{W_{i+1}}(1-\sqrt{\epsilon})t/2p^{3}\\}.$

We claim $|\bigcup_{Y_{j}\in\mathcal{G}^{*}}Y_{j}|\geq\epsilon_{3}^{1/4}n$.
Suppose towards a contradiction this is not the case, i.e. that
$|\bigcup_{Y_{j}\in\mathcal{G}^{*}}Y_{j}|<\epsilon_{3}^{1/4}n$. Note that if
$Y_{j}\in K^{*}\setminus\mathcal{G}^{*}$, then by definition of
$\mathcal{G}^{*}$ and the above,

$\displaystyle\Big{|}\Big{(}\bigcup_{y\in
P_{2}(Y_{j})}B_{r_{i+1}/4}(f_{W_{i+1}Y_{j}Z}(w_{i+1}y)\Big{)}\setminus\Big{(}\bigcup_{Z_{k}\in
J_{Z}(i+1)}\Psi_{3}(Z_{k})\Big{)}\Big{|}$
$\displaystyle\geq\rho^{\prime}_{W_{i+1}}n/8p-\rho^{\prime}_{W_{i+1}}(1-\sqrt{\epsilon})N/4p^{3}$
$\displaystyle=\rho^{\prime}_{W_{i+1}}n(\frac{1}{8p}-\frac{3(1-\sqrt{\epsilon})}{4p^{3}})$
$\displaystyle\geq\rho^{\prime}_{W_{i+1}}n/16p^{3}.$

By assumption
$|\bigcup_{Y_{j}\in\mathcal{G}^{*}}Y_{j}|\leq\epsilon_{3}^{1/4}n$, so

(15) $\displaystyle|\bigcup_{Y_{j}\in
K^{*}\setminus\mathcal{G}^{*}}Y_{j}|\geq|\bigcup_{Y_{j}\in
K^{*}}Y_{j}|-\epsilon_{3}^{1/4}n\geq|Y_{*}|(1-7\epsilon_{3}^{1/4}),$

where the last inequality also uses the Size Axiom, the Special Sets Axiom,
and the fact that $\epsilon\ll\mu$ (if $Y_{*}=Y_{sm}$) and $\epsilon\ll\tau$
(if $Y_{*}=Y_{lg}$). Let $K$ be a maximal
$10\rho^{\prime}_{W_{i+1}}$-separated subset of
$\bigcup_{K^{*}\setminus\mathcal{G}^{*}}P_{2}(Y_{j})$. Since

$\bigcup_{Y_{j}\in K^{*}\setminus\mathcal{G}^{*}}Y_{j}\subseteq\bigcup_{y\in
K}B_{10\rho^{\prime}_{X_{i}}}(y),$

we know that by (15), the Size Axiom, and the Special Sets Axiom,

$\min\\{\mu,\tau\\}(1-7\epsilon_{3}^{1/4})n/2p\leq|Y_{*}|(1-7\epsilon_{3}^{1/4})\leq|K|10p\rho^{\prime}_{W_{i+1}}n.$

Thus
$|K|\geq(\rho^{\prime}_{W_{i+1}})^{-1}(1-7\epsilon_{3}^{1/4})\min\\{\mu,\tau\\}/20p^{2}$.
By definition, for all $y\neq y^{\prime}\in K$,
$d(y,y^{\prime})>10\rho^{\prime}_{W_{i+1}}$, and therefore, by Claim 6.33(i)
or (ii),
$d(f_{W_{i+1}Y_{j}Z}(w_{i+1}y),f_{W_{i+1}Y_{j^{\prime}}Z}(w_{i+1}y^{\prime}))\geq
5\rho^{\prime}_{W_{i+1}}$. Consequently,

$B_{r_{i+1}/4}(f_{W_{i+1}Y_{j}Z}(w_{i+1}y))\cap
B_{r_{i+1}/4}(f_{W_{i+1}Y_{j^{\prime}}Z}(w_{i+1}y^{\prime}))=\emptyset.$

Thus

$\displaystyle|\bigcup_{Z_{k}\in J_{Z}(i+1)}\Psi_{3}(Z_{k})|$
$\displaystyle\leq n-|(\bigcup_{Y_{j}\in
K^{*}\setminus\mathcal{G}^{*}}\bigcup_{y\in
K}B_{r_{i+1}/4}(f_{W_{i+1}Y_{j}Z}(w_{i+1}y)))\setminus\bigcup_{Z_{k}\in
J_{Z}(i+1)}\Psi_{3}(Z_{k})|$ $\displaystyle\leq
n-|K|\rho^{\prime}_{W_{i+1}}n/16p^{3}$ $\displaystyle\leq
n-(\rho^{\prime}_{W_{i+1}})^{-1}(1-7\epsilon_{3}^{1/4})\min\\{\mu,\tau\\}(20p^{2})^{-1}\rho^{\prime}_{W_{i+1}}n(16p^{3})^{-1}$
$\displaystyle\leq n(1-\min\\{\mu,\tau\\}/240p^{6}).$

However, by the definition of $\Psi_{3}(Z_{k})$ in Claim 6.32, we know that
for all $Z_{k}\in J_{Z}(i+1)$, $|\Psi(Z_{k})|\geq(1-3\epsilon^{1/4})|Z_{k}|$.
Consequently by (6.4),

$\displaystyle|\bigcup_{Z_{k}\in
J_{Z}(i+1)}\Psi_{3}(Z_{k})|\geq(1-6\epsilon^{1/3})|\bigcup_{Z_{k}\in
J_{Z}(i+1)}Z_{k}|$
$\displaystyle\geq(1-6\epsilon^{1/3})(1-\epsilon_{3}^{1/2})|Z_{lg}^{+}\cup
Z_{sm}^{+}|$ $\displaystyle>(1-\min\\{\mu,\tau\\}/240p^{6})n,$

where the last inequality uses that $\epsilon\ll\mu,\tau$. This is a
contradiction, so we must have that
$|\bigcup_{Y_{j}\in\mathcal{G}^{*}}Y_{j}|\geq\epsilon_{3}^{1/4}n$, so
$|\mathcal{G}^{*}|\geq\epsilon_{3}^{1/4}t/3$. Now define

$\mathcal{S}_{W_{i+1}}=\bigcup_{Y_{j}\in\mathcal{G}^{*}}\mathcal{S}_{W_{i+1}Y_{j}}$

Then we have shown that $\mathcal{S}_{W_{i+1}}\subseteq\mathcal{S}$ and

$|\mathcal{S}_{W_{i+1}}|\geq|\mathcal{G}^{*}|\rho^{\prime}_{W_{i+1}}(1-\sqrt{\epsilon})t/2p^{3}\geq\rho^{\prime}_{W_{i+1}}\epsilon_{3}^{1/4}(1-\sqrt{\epsilon})^{2}t^{2}/12p^{3}.$

This finishes the definition of $\mathcal{S}_{W_{i+1}}$.

We now show that for all $u\leq i$,
$\mathcal{S}_{W_{u}}\cap\mathcal{S}_{W_{i+1}}=\emptyset$. Suppose towards a
contradiction, there is some $u\leq i$ with
$\mathcal{S}_{W_{u}}\cap\mathcal{S}_{W_{i+1}}\neq\emptyset$, say
$Y_{j}Z_{k}\in\mathcal{S}_{W_{u}}\cap\mathcal{S}_{W_{i+1}}$. By construction,
this implies $W_{u}\in L_{X}(u)$, say $W_{u}=X_{j_{u}}$ for some $j_{u}\neq
j_{i+1}$. We claim that either both $W_{u},W_{i+1}\in K_{X}^{lg}$ or both
$W_{u},W_{i+1}\in K_{X}^{sm}$. Suppose $W_{u}\in K_{X}^{sm}$ and $W_{i+1}\in
K_{X}^{lg}$. Then $W_{u}\in K_{X}^{sm}$ implies $Y_{j}\in K_{Y}^{lg}$, while
$W_{i+1}\in K_{X}^{lg}$ implies $Y_{j}\in K_{Y}^{sm}$. But now $Y_{j}\in
K_{Y}^{sm}\cap K_{Y}^{lg}$. This implies that $|Y_{j}\cap
Y^{+}_{sm}|>|Y_{j}|/2$ and $|Y_{j}\cap Y^{+}_{lg}|>|Y_{j}|/2$, which implies
$Y^{+}_{sm}\cap Y^{+}_{lg}\neq\emptyset$, contradicting the Disjointness
Axiom. A similar argument shows we cannot have $W_{i+1}\in K_{X}^{sm}$ and
$W_{u}\in K_{X}^{lg}$.

Therefore we have that either $W_{u},W_{i+1}\in K_{X}^{lg}$ or
$W_{u},W_{i+1}\in K_{X}^{sm}$. By construction, there is $w_{u}\in
P_{2}(W_{u})$ such that one of the following holds.

  1. (1)

Both $W_{u},W_{i+1}\in K_{X}^{lg}$ and $Y_{j}Z_{k}\in
K_{2}[K_{Y}^{sm}(u),J_{Z}(u)]\cap K_{2}[K_{Y}^{sm}(i+1),J_{Z}(i+1)]$, and

$\displaystyle\Psi_{3}(Z_{k})\cap
B_{r_{u}/4}(f_{W_{u}Y_{j}Z}(w_{u}y))\neq\emptyset\text{ some }y\in
P_{2}(Y_{j}),\text{ and }$ $\displaystyle\Psi_{3}(Z_{k})\cap B_{r_{i+1}/4}$
$\displaystyle(f_{W_{i+1}Y_{j}Z}(w_{i+1}y))\neq\emptyset\text{ some }y\in
P_{2}(Y_{j}).$

  2. (2)

Both $W_{u},W_{i+1}\in K_{X}^{sm}$ and $Y_{j}Z_{k}\in
K_{2}[K_{Y}^{lg},J_{Z}(u)]\cap K_{2}[K_{Y}^{lg}(i+1),J_{Z}(i+1)]$, and

$\displaystyle\Psi_{3}(Z_{k})\cap
B_{r_{u}/4}(f_{W_{u}Y_{j}Z}(w_{u}y))\neq\emptyset\text{ some }y\in
P_{2}(Y_{j})\text{ and }$ $\displaystyle\Psi_{3}(Z_{k})\cap B_{r_{i+1}/4}$
$\displaystyle(f_{W_{i+1}Y_{j}Z}(w_{i+1}y))\neq\emptyset\text{ some }y\in
P_{2}(Y_{j}).$

Since $Y_{j}\in J_{Y}(i+1)$, we know
$\rho^{\prime}_{Y_{j}}\leq\min\\{\rho^{\prime}_{W_{u}},\rho^{\prime}_{W_{i+1}}\\}$.
By construction, the centers of $B_{W_{u}}$ and $B_{W_{i+1}}$ have distance at
least $10\rho^{\prime}_{W_{u}}$ from each other. Combining this with the fact
that for all $y,y^{\prime}\in P_{2}(Y_{j})$,
$d(y,y^{\prime})\leq\rho^{\prime}_{Y_{j}}$, we have by Claim 6.33 that the
following hold.

(16) $\displaystyle
d(f_{Y_{j}W_{u}Z}(yw_{u}),f_{W_{i+1}Y_{j}Z}(w_{i+1}y^{\prime}))\geq
5\rho^{\prime}_{W_{u}}\geq 5\rho^{\prime}_{Z_{k}},$

But (16) implies that it is not possible to have both
$B_{r_{u}/4}(f_{W_{u}Y_{j}Z}(w_{u}y)))$ and
$B_{r_{i+1}/4}(f_{W_{i+1}Y_{j}Z}(w_{i+1}y^{\prime}))$ intersect $B_{Z_{k}}$, a
contradiction. This finishes our verification that
$\mathcal{S}_{W_{u}}\cap\mathcal{S}_{W_{i+1}}=\emptyset$, and consequently the
$(i+1)$-st step of our construction.

Clearly this will end at some stage $t^{*}$, where we will have that for some
$X\in\\{A,B,C\\}$, $|\bigcup_{X_{v}\in
L_{X}(t^{*})}B^{\prime}_{X_{v}}|\geq\epsilon^{1/16}N$. Say $1\leq
i_{1}<\ldots<i_{s}\leq t^{*}$ are such that

$W_{i_{1}},\ldots,W_{i_{s}}\subseteq\\{X_{i}:i\in[t]\\},$

and $|\sum_{j=1}^{s}B^{\prime}_{W_{i_{j}}}|\geq\epsilon^{1/16}N$. By the size
axiom, this implies
$\sum_{j=1}^{s}\rho^{\prime}_{W_{i_{j}}}\geq\epsilon^{1/16}/4p$. Therefore, we
have that

$\displaystyle|\mathcal{S}|$
$\displaystyle\geq\sum_{j=1}^{s}|\mathcal{S}_{W_{i_{j}}}|\geq(1-2\sqrt{\epsilon})^{2}\epsilon_{3}^{1/4}t^{2}(\sum_{j=1}^{s}\rho^{\prime}_{W_{i_{s}}})/4p^{3}>\epsilon_{3}^{3/4}t^{2}/20p^{4}>13\epsilon_{3}t^{2},$

where the last inequality uses that $\epsilon\ll p^{-1}$ and $t\geq t_{0}$.
But contradicts (10), which finishes the proof. ∎

We obtain as an immediate corollary that $\mathcal{H}_{\textnormal{HP}}$ and
$\mathcal{H}_{\textnormal{GS}_{p}}$ require non-binary
$\textnormal{vdisc}_{3}$-error.

######  Corollary 6.34.

$\mathcal{H}_{\textnormal{HP}}$, as well as
$\mathcal{H}_{\textnormal{GS}_{p}}$ for any prime $p\geq 3$ require non-binary
$\textnormal{vdisc}_{3}$-error.

###### Proof.

This follows immediately from Lemmas 6.26, 6.27, and Theorem 6.28. ∎

We will now use this fact to prove Theorems 1.60 and 1.63, which state that if
$\mathcal{H}$ is a hereditary $3$-graph property and either
$\mathcal{H}_{\textnormal{HP}}\subseteq\text{Trip}(\mathcal{H})$ or
$\mathcal{H}_{\textnormal{GS}_{p}}\subseteq\text{Trip}(\mathcal{H})$, then
$\mathcal{H}$ requires non-binary $\textnormal{disc}_{2,3}$-error.

Proof of Theorems 1.60 and 1.63: Suppose towards a contradiction there exists
a hereditary $3$-graph property $\mathcal{H}_{2}$ such that one of (1) or (2)
below holds, and such that $\mathcal{H}_{2}$ admits binary
$\textnormal{disc}_{2,3}$-error.

  1. (1)

$\mathcal{H}_{1}=\mathcal{H}_{\textnormal{HP}}\subseteq\text{Trip}(\mathcal{H}_{2})$,
or

  2. (2)

$\mathcal{H}_{1}=\mathcal{H}_{\textnormal{GS}_{p}}\subseteq\text{Trip}(\mathcal{H}_{2})$.

By Corollary 6.34, there is some $\epsilon_{1}>0$ such that for all $T,M$,
there is $N_{T,M}$ such that for all $n\geq N$, neither $\textnormal{HP}(n)$
nor $\textnormal{GS}_{p}(n)$ admit an $\epsilon_{1}$-homogeneous partition
$G_{T,M}$ into at most $T$ parts with binary error.

Let $0<\epsilon_{1}\ll\epsilon_{1}$, and choose
$\epsilon_{2}:\mathbb{N}\rightarrow(0,1)$ as in Proposition 4.1 for
$\epsilon_{1}^{\prime}$ and $k=8$. Define
$\epsilon_{2}^{\prime}:\mathbb{N}\rightarrow(0,1]$ by choosing
$\epsilon_{2}^{\prime}(x)\ll\epsilon_{1}^{\prime}\epsilon_{2}(x)$ for all $x$.
By assumption, there are $T_{1},L_{1},M_{1}$ such that for all
$G^{\prime}=(V^{\prime},E^{\prime})\in\mathcal{H}_{2}$ with $|V^{\prime}|\geq
M_{1}$, there is are $1\leq t\leq T_{1}$, $1\leq\ell\leq L_{1}$ and a
$(t,\ell,\epsilon^{\prime}_{1},\epsilon^{\prime}_{2}(\ell))$-decomposition of
$V^{\prime}$ which is
$(\epsilon_{1}^{\prime},\epsilon_{2}^{\prime}(\ell))$-regular with respect to
$G^{\prime}$ with binary $\textnormal{disc}_{2,3}$-error.

Let $T_{2}=T_{1}(\epsilon^{\prime}_{1})^{-1}$ and choose $M_{2}\gg
3M_{1}T_{1}(\epsilon^{\prime}_{1})^{-1}$. Now fix $n\geq
M_{2},N_{T_{2},M_{2}}$ and let $G=\textnormal{HP}(n)=(A\cup B\cup C,E)$ if (1)
holds, and $G=\textnormal{GS}_{p}(n)=(A\cup B\cup C,E)$ if (2) holds.

By assumption, $G\in\text{Trip}(\mathcal{H}_{2})$. By definition this means
there is some $H=(V,F)\in\mathcal{H}_{2}$ and sets

$\displaystyle A^{\prime}$ $\displaystyle=\\{v_{a}:a\in A\\}\subseteq
V^{\prime},\text{ }B^{\prime}=\\{v_{b}:b\in B\\}\subseteq V^{\prime},\text{
and }C^{\prime}=\\{v_{c}:c\in C\\}\subseteq V^{\prime},$

such that $v_{a_{g}}v_{b_{g^{\prime}}}v_{c_{g^{\prime\prime}}}\in F$ if and
only if $abc\in E$. Note this implies $|V^{\prime}|\geq n\geq M_{1}$. Let
$H^{\prime}=H[A^{\prime}\cup B^{\prime}\cup C^{\prime}]$. Then
$H^{\prime}\in\mathcal{H}_{2}$, and $n\leq|V(H^{\prime})|\leq 3n$. Since
$n\geq M_{1}$, there are $t_{0}\leq t\leq T_{1}$, $\ell_{0}\leq\ell\leq L_{1}$
and a
$(t,\ell,\epsilon^{\prime}_{1},\epsilon^{\prime}_{2}(\ell))$-decomposition
$\mathcal{P}$ of $V(H^{\prime})$ which is
$(\epsilon^{\prime}_{1},\epsilon^{\prime}_{2}(\ell))$-regular with respect to
$H^{\prime}$, and which has binary $\textnormal{disc}_{2,3}$-error. Say
$\mathcal{P}_{vert}=V^{\prime}_{1}\cup\ldots\cup V^{\prime}_{t}$ and
$\mathcal{P}_{edge}=\\{P_{ij}^{\alpha}:ij\in{[t]\choose 2},\alpha\leq\ell\\}$.
Note that for each $1\leq i\leq t$, $n/t\leq|V_{i}|\leq 3n/t$. Define

$\Sigma=\\{ij\in{[t]\choose 2}:\text{ some
}P_{ijk}^{\alpha,\beta,\gamma}\in\operatorname{Triads}(\mathcal{P})\text{
fails }\textnormal{disc}_{2,3}(\epsilon_{2}(\ell),1/\ell)\text{ with respect
to }H^{\prime}\\}.$

By assumption, $|\Sigma|\leq\epsilon^{\prime}_{1}t^{2}$. For each $1\leq i\leq
t$, let

$A_{i}=\\{a\in A:v_{a}\in V_{i}^{\prime}\\},\text{ }B_{i}=\\{b\in B:v_{b}\in
V_{i}^{\prime}\\}\text{ and }C_{i}=\\{c\in C:v_{c}\in V_{i}^{\prime}\\}.$

Then $\\{A_{i},B_{i},C_{i}:i\in[t]\\}$ forms a partition of $A\cup B\cup C$.
Set $t_{0}=3\lceil\epsilon_{1}^{-2}\rceil$ and $K=\lfloor 3n/t_{0}t\rfloor$.
For each $i\in[t]$ and $X\in\\{A,B,C\\}$, let $X_{i}=X_{i0}\cup
X_{i1}\cup\ldots\cup X_{ik^{X}_{i}}$ be a partition with the property that
$|X_{i0}|<K$ and so that for each $1\leq s\leq k^{X}_{i}$, $|X_{is}|=K$. Let
$k_{X}=\sum_{i=1}^{t}k^{X}_{i}$ and set $X_{0}=\bigcup_{i=1}^{t}X_{i0}$. Note
that by definition of $t_{0}$ and $K$, $|X_{0}|\leq tK\leq
3\epsilon^{2}_{1}n$. Choose $\\{X_{0}^{is}:1\leq i\leq t,1\leq s\leq
k^{X}_{i}\\}$ any equipartition of $X_{0}$ into $k$ parts, and for each $1\leq
i\leq t$ and $1\leq s\leq k^{X}_{i}$, set $X_{is}^{\prime}=X_{is}\cup
X_{is}^{0}$. Clearly $|X_{is}^{\prime}\setminus X_{is}|\leq
3\epsilon_{2}^{2}|X_{is}|$.

We now have an partition $\mathcal{Q}_{vert}$ of $V(G)$ given by

$\\{A_{is}^{\prime}:1\leq i\leq t,1\leq s\leq
k^{A}_{i}\\}\cup\\{B_{is}^{\prime}:1\leq i\leq t,1\leq s\leq
k^{B}_{i}\\}\cup\\{C_{is}^{\prime}:1\leq i\leq t,1\leq s\leq k^{C}_{i}\\}.$

For each $1\leq\alpha\leq\ell$, $X\neq Y$ in $\\{A,B,C\\}$, $ij\in{[t]\choose
2}$, $1\leq s\leq k^{X}_{i}$, and $1\leq r\leq k^{Y}_{j}$, set
$Q_{ij,sr,XY}^{\alpha}=P_{ij}^{\alpha}\cap
K_{2}[X_{is}^{\prime},Y_{jr}^{\prime}]$. Note that by Lemma 2.18, if
$P_{ij}^{\alpha}$ satisfies
$\textnormal{disc}_{2}(\epsilon_{2}^{\prime}(\ell),1/\ell)$, then each
$Q_{ij,sr,XY}^{\alpha}$ satisfies
$\textnormal{disc}_{2}(\epsilon_{2}(\ell),1/\ell)$.

Then for each $X\in\\{A,B,C\\}$, $1\leq i\leq t$, and
$sr\in{[k^{X}_{i}]\choose 2}$, choose any partition
$K_{2}[W_{is}^{\prime},W_{ir}^{\prime}]=\bigcup_{\alpha\leq\ell}Q_{is,ir^{\prime},XX}^{\alpha}$
so that each $Q_{is,ir^{\prime},XX}^{\alpha}$ has
$\textnormal{disc}_{2}(\epsilon_{2}(\ell),1/\ell)$ (such a partition exists by
Lemma 2.24). We now set

$\displaystyle\mathcal{Q}_{edge}$
$\displaystyle=\\{Q_{ij,sr,AB}^{\alpha}:1\leq i,j\leq t,1\leq s\leq
k^{A}_{i},1\leq r\leq k^{B}_{j}\\}\cup$
$\displaystyle\\{Q_{ij,sr,AC}^{\alpha}:1\leq i,j\leq t,1\leq s\leq
k^{A}_{i},1\leq r\leq k^{C}_{j}\\}\cup$
$\displaystyle\\{Q_{ij,sr,BC}^{\alpha}:1\leq i,j\leq t,1\leq s\leq
k^{B}_{i},1\leq r\leq k^{C}_{j}\\}\cup$
$\displaystyle\\{Q_{ij,sr,X}^{\alpha}:X\in\\{A,B,C\\},1\leq s,r\leq
k^{X}_{i}\\}.$

It is straightforward to check that $\mathcal{Q}$ is a
$(tk,\ell,\epsilon_{1},\epsilon_{2}(\ell))$-decomposition of $A\cup B\cup C$.
We then define

$\displaystyle\Sigma^{\prime}=$ $\displaystyle\\{X_{is}Y_{jr}:X\neq
Y\in\\{A,B,C\\},ij\in\Sigma,s\in[k^{X}_{i}],r\in[k^{Y}_{j}]\\}\cup$
$\displaystyle\\{X_{is}Y_{ir}:X,Y\in\\{A,B,C\\},s\in[k_{i}^{X}],r\in[k_{i}^{Y}]\\}.$

It is straightforward to check that since
$\epsilon_{1}^{\prime}\ll\epsilon_{1}$ and by our choice of $t_{0}$, we have
$|\Sigma^{\prime}|\leq\epsilon_{1}|\mathcal{Q}_{vert}|^{2}$. We claim that any
triple of sets from $\mathcal{Q}_{vert}$ avoiding $\Sigma^{\prime}$ is
$\epsilon_{1}$-homogeneous with respect to $G$. Clearly this holds of any
triple of the form $X_{is}X_{js}Y_{pq}$ for $X,Y\in\\{A,B,C\\}$ or
$X_{is}X_{js}X_{pq}$ for some $X\in\\{A,B,C\\}$. Indeed, any such triple will
have edge density $0$ in $G$, since $G$ is $3$-partite with parts $A,B,C$.

So fix some triple $A_{is}B_{jr}C_{pq}\in{\mathcal{Q}_{vert}\choose 3}$ such
that $A_{is}B_{jr},B_{jr}C_{pq},A_{is}C_{pq}\notin\Sigma^{\prime}$, and a
triad

$\Gamma_{is,jr,pq}^{\alpha,\beta,\gamma}=(A_{is}\cup B_{jr}\cup
C_{pq},Q_{ij,sr,AB}^{\alpha}\cup Q_{jp,rq,BC}^{\beta}\cup
Q_{ip,sq,AC}^{\gamma}).$

By construction, $ij,ip,jp\notin\Sigma$, so the triad
$P_{ijp}^{\alpha,\beta,\gamma}=(V^{\prime}_{i}\cup V^{\prime}_{j}\cup
V^{\prime}_{p},P_{ij}^{\alpha}\cup P_{jp}^{\beta}\cup P_{ip}^{\gamma})$
satisfies
$\textnormal{disc}_{2,3}(\epsilon_{1}^{\prime},\epsilon_{2}^{\prime}(\ell))$
with respect to $H^{\prime}$. Let $d\in[0,1]$ be such that $|E(H^{\prime})\cap
K_{3}^{(2)}(P_{ijp}^{\alpha,\beta,\gamma})|=d|K_{3}^{(2)}(P_{ijp}^{\alpha,\beta,\gamma})|$.
Now suppose $\Gamma^{\prime}$ is a subgraph of
$\Gamma_{is,jr,pq}^{\alpha,\beta,\gamma}$.

Consider the graph $R_{ijp}^{\alpha,\beta,\gamma}$ with vertex set
$V_{i}^{\prime}\cup V_{j}^{\prime}\cup V_{p}^{\prime}$ and edge set

$\\{xyz\in
K_{3}[V_{i}^{\prime},V_{j}^{\prime},V_{p}^{\prime}]:x=v_{a},y=v_{b},\text{ and
}z=v_{c}\text{ for some }abc\in
E(\Gamma_{is,jr,pq}^{\alpha,\beta,\gamma})\\},$

and consider the subgraph $R^{\prime}$ with $V_{i}^{\prime}\cup
V_{j}^{\prime}\cup V_{p}^{\prime}$ and edge set

$\\{xyz\in
K_{3}[V_{i}^{\prime},V_{j}^{\prime},V_{p}^{\prime}]:x=v_{a},y=v_{b},\text{ and
}z=v_{c}\text{ for some }abc\in K_{3}^{(2)}(\Gamma^{\prime})\\},$

Both $R_{is,jr,pq}^{\alpha,\beta,\gamma}$ and $R^{\prime}$ are subgraphs of
$P_{ijp}^{\alpha,\beta,\gamma}$, so by the definition of
$\textnormal{disc}_{2,3}(\epsilon_{1}^{\prime},\epsilon_{2}^{\prime}(\ell))$,

$\displaystyle||E(H^{\prime})\cap
K_{3}^{(2)}(R_{is,jr,pq}^{\alpha,\beta,\gamma})|-d|K_{3}^{(2)}(R_{is,jr,pq}^{\alpha,\beta,\gamma})||\leq\epsilon_{1}^{\prime}\frac{1}{\ell^{3}}|V^{\prime}_{i}||V^{\prime}_{j}||V^{\prime}_{p}|\text{
and }$ $\displaystyle||E(H^{\prime})\cap
K_{3}^{(2)}(R^{\prime})|-d|K_{3}^{(2)}(R^{\prime})||\leq\epsilon_{1}^{\prime}\frac{1}{\ell^{3}}|V^{\prime}_{i}||V^{\prime}_{j}||V^{\prime}_{p}|$

Since $i,j,p$ are distinct, we have that

$|K_{3}^{(2)}(R_{is,jr,pq}^{\alpha,\beta,\gamma}))|=|K_{3}^{(2)}(\Gamma_{is,jr,pq}^{\alpha,\beta,\gamma})|\text{
and }|K_{3}^{(2)}(R^{\prime}))|=|K_{3}^{(2)}(\Gamma^{\prime})|,$

and

$|E(H^{\prime})\cap K_{3}^{(2)}(R_{is,jr,pq}^{\alpha,\beta,\gamma})|=|E(G)\cap
K_{3}^{(2)}(\Gamma_{is,jr,pq}^{\alpha,\beta,\gamma})|\text{ and
}|E(H^{\prime})\cap K_{3}^{(2)}(R^{\prime})|=|E(G)\cap
K_{3}^{(2)}(\Gamma^{\prime})|.$

Consequently, if we let $d^{\prime}$ be such that $|E(G)\cap
K_{3}^{(2)}(\Gamma_{ijp}^{\alpha,\beta,\gamma})|=d^{\prime}|K_{3}^{(2)}(\Gamma_{ijp}^{\alpha,\beta,\gamma})|$,
then

$\displaystyle|d^{\prime}-d|\leq\epsilon_{1}^{\prime}\frac{1}{\ell^{3}}|V^{\prime}_{i}||V^{\prime}_{j}||V^{\prime}_{p}|(|K_{3}^{(2)}(\Gamma_{is,jr,pq}^{\alpha,\beta,\gamma})|)^{-1}$
$\displaystyle\leq\epsilon_{1}^{\prime}\frac{1}{\ell^{3}}|V_{i}^{\prime}||V_{j}^{\prime}||V_{p}^{\prime}|3\epsilon_{1}^{-2}$
$\displaystyle\leq\epsilon_{1}^{8}\frac{1}{\ell^{3}}|A_{is}||B_{jr}||C_{pq}|,$

where the second inequality is from Corollary 2.6 and the definition of
$\mathcal{Q}_{vert}$, and the last inequality is since
$\epsilon_{1}^{\prime}\ll\epsilon_{1}$. We also have from the above that

$||E(G)\cap
K_{3}^{(2)}(\Gamma^{\prime})|-d|K_{3}^{(2)}(\Gamma^{\prime})||\leq\epsilon_{1}^{\prime}\frac{1}{\ell^{3}}|V^{\prime}_{i}||V^{\prime}_{j}||V^{\prime}_{p}|\leq\epsilon_{1}^{8}\frac{1}{\ell^{3}}|A_{is}||B_{jr}||C_{pq}|,$

where the last inequality is since $\epsilon_{1}^{\prime}\ll\epsilon_{1}$ and
the definition of $\mathcal{Q}_{vert}$. Combining these, we have that

$||E(G)\cap
K_{3}^{(2)}(\Gamma^{\prime})|-d^{\prime}|K_{3}^{(2)}(\Gamma^{\prime})||\leq
2\epsilon_{1}^{8}\frac{1}{\ell^{3}}|A_{is}||B_{jr}||C_{pq}|,$

which shows that $\Gamma_{is,jr,pq}^{\alpha,\beta,\gamma}$ satisfies
$\textnormal{disc}_{2,3}(2\epsilon_{1}^{8},\epsilon_{2}(\ell))$ with respect
to $G$. We can conclude By Proposition 4.1, (since $G$ has VC-dimension at
most $8$) that

$|E(G)\cap
K_{3}[A_{is},B_{jr},C_{pq}]|/|C_{is}||B_{jr}||C_{pq}|\in[0,\epsilon_{1}^{2})\cup(1-\epsilon_{1}^{2},1].$

This shows that any triple form $\mathcal{Q}_{vert}$ avoiding
$\Sigma^{\prime}$ is $\epsilon^{2}_{1}$-homogeneous with respect to $G$. As
defined $\mathcal{Q}_{vert}$ may not be itself an equipartition, although its
parts will differ in size by at most $\epsilon_{1}^{2}n/|\mathcal{Q}_{vert}|$.
It is now not too difficult to show that one can redistribute some vertices to
make $\mathcal{Q}_{vert}$ into an equipartition without changing the densities
within any of the triads by very much. The result will be an
$\epsilon_{1}$-homogeneous equipartition of $G$ with binary error and at most
$T_{2}$ parts, a contradiction. ∎

We now prove as a Corollary 1.66, which says that a property admitting binary,
zero, or linear $\textnormal{disc}_{2,3}$-error is
$\textnormal{disc}_{2,3}$-homogeneous.

Proof of Corollary 1.66: Suppose $\mathcal{H}$ admits zero
$\textnormal{disc}_{2,3}$-error. By Corollary 4.6, there is $k$ such that
$\overline{H}(k)\notin\text{Trip}(\mathcal{H})$. By Fact 1.29, $\mathcal{H}$
has finite $\textnormal{VC}_{2}$-dimension, so by Theorem 1.31, it is
$\textnormal{disc}_{2,3}$-homogeneous. Suppose now $\mathcal{H}$ admits binary
$\textnormal{disc}_{2,3}$-error. By Theorem 1.60, there is $k\geq 1$ such that
$\textnormal{HP}(k)\notin\text{Trip}(\mathcal{H})$. By Fact 1.29,
$\mathcal{H}$ has finite $\textnormal{VC}_{2}$-dimension, so by Theorem 1.31,
it is $\textnormal{disc}_{2,3}$-homogeneous. Suppose now $\mathcal{H}$ admits
linear $\textnormal{disc}_{2,3}$-error. By Theorem 1.57, there is $k\geq 1$
such that $F(k)\notin\text{Trip}(\mathcal{H})$. By Fact 1.29, $\mathcal{H}$
has finite $\textnormal{VC}_{2}$-dimension, so by Theorem 1.31, it is
$\textnormal{disc}_{2,3}$-homogeneous. ∎

A similar argument will be important in our proof of Theorem 1.22. In
particular, we will use the following lemma.

######  Lemma 6.35.

There are $\epsilon_{1}>0$, $\epsilon_{2}:\mathbb{N}\rightarrow(0,1]$, and
$t_{0},\ell_{0}\geq 1$ such that for all $T$, $L$ and $N$, there is $n\geq N$
such that for all $t_{0}\leq t\leq T_{0}$, and $\ell_{0}\leq\ell\leq T_{0}$,
any $(t,\ell,\epsilon_{1},\epsilon_{2}(\ell))$-decomposition of
$V(\textnormal{HP}(n))$ which is $(\epsilon_{1},\epsilon_{2}(\ell))$-regular,
has a $\textnormal{disc}_{3}$-irregular triad.

###### Proof.

Since $\mathcal{H}_{\textnormal{HP}}$ has finite VC-dimension it is
$\textnormal{disc}_{2,3}$-homogeneous by Theorem 1.31. Suppose towards a
contradiction that for all $\epsilon_{1}>0$,
$\epsilon_{2}:\mathbb{N}\rightarrow(0,1]$, and $t_{0},\ell_{0}\geq 1$ there
are $T$, $L$ and $N$, such that for all $n\geq N$ there is $t_{0}\leq t\leq
T_{0}$, and $\ell_{0}\ell\leq L_{0}$, any
$(t,\ell,\epsilon_{2},\epsilon_{1})$-decomposition of $V(\textnormal{HP}(n))$
which is $(\epsilon_{1},\epsilon_{2})$-regular and has no
$\textnormal{disc}_{3}$-irregular triad. By Theorem 1.60, there are
$\mu_{1},\mu_{2},t_{0},\ell_{0}$ such that for all $T$, $L$ and $N$, there is
$n\geq N$ such that for all $t_{0}\leq t\leq T_{0}$, and $\ell\leq T_{0}$, any
$(t,\ell,\mu_{1},\mu_{2}(\ell))$-decomposition of $V(\textnormal{HP}(n))$
which is $(\mu_{1},\mu_{2}(\ell))$-regular, has non-binary
$\textnormal{disc}_{2,3}$-error.

By our assumption, and because $\mathcal{H}_{\textnormal{HP}}$ is
$\textnormal{disc}_{2,3}$-homogeneous, there are $T$, $L$ and $N$, so that for
all $n\geq N$ there is $t_{0}\leq t\leq T_{0}$, and $\ell_{0}\leq\ell\leq
L_{0}$, and a $(t,\ell,\mu_{1},\mu_{2}(\ell))$-decomposition of
$V(\textnormal{HP}(n))$ which is $(\mu_{1},\mu_{2}(\ell))$-regular, with no
$\textnormal{disc}_{3}$-irregular triads, and which is
$\textnormal{disc}_{2,3}$-homogeneous. Let $\Sigma$ be the set of pairs
$V_{i}V_{j}$ where at least $(\epsilon^{\prime}_{1})^{1/2}|V_{i}||V_{j}|$ of
the $xy\in K_{2}[V_{i}V_{j}]$ are in a $\textnormal{disc}_{2}$-irregular
$P\in\mathcal{P}_{edge}$. By assumption,
$|\Sigma|\leq(\epsilon_{1}^{\prime})^{1/2}t^{2}$. If
$V_{i}V_{j},V_{i}V_{k},V_{j}V_{k}\notin\Sigma$, then by Proposition 4.1,
$|E\cap
K_{3}[V_{i},V_{j},V_{k}]|/K_{3}[V_{i},V_{j},V_{k}]|\in[0,\epsilon_{1})\cup(1-\epsilon_{1},1]$.
But now $\mathcal{P}$ is $\textnormal{vdisc}_{3}$-homogeneous with binary
error, a contradiction. ∎

We now prove Theorem 1.22.

Proof of Theorem 1.22: Fix a hereditary $3$-graph property $\mathcal{H}$, and
assume is admits binary $\textnormal{disc}_{2,3}$-error. Fix $\epsilon_{1}>0$,
$\epsilon_{2}:\mathbb{N}\rightarrow(0,1]$ nonincreasing, and
$t_{0},\ell_{0}\geq 1$. Let $\epsilon_{1}^{\prime}=\epsilon_{1}^{2}$. By
assumption, there is $T$, $L$ and $N$ so that if $H\in\mathcal{H}$ has at
least $N$ vertices, then there exist $\ell_{0}\leq\ell\leq L$, $t_{0}\leq
t\leq T$, and $\mathcal{P}$ a
$(t,\ell,\epsilon^{\prime}_{1},\epsilon_{2}(\ell))$-decomposition of $V(H)$
which is $(\epsilon^{\prime}_{1},\epsilon_{2}(\ell))$-regular, with binary
$\textnormal{disc}_{2,3}$-error with respect to $H$. Say $\mathcal{P}$
consists of $\\{V_{i}:i\in[t]\\}$ and $\\{P_{ij}^{\alpha}:ij\in{[t]\choose
2},\alpha\leq\ell\\}$. Let $\Sigma\subseteq{[t]\choose 2}$ be such that every
$\textnormal{disc}_{2,3}$-irregular triad of $\mathcal{P}$ uses a pair
$V_{i}V_{j}$ with $ij\in\Sigma$, and where
$|\Sigma|\leq\epsilon_{1}^{\prime}t^{2}$.

Let $\ell_{1}=\lfloor\ell/2\rfloor$ and $\ell_{2}=\lceil\ell/2\rceil$. For
each $i\in[t]$, let $V_{i}=V_{i1}\cup V_{i2}$ be an equipartition. For each
$i<j$ with $ij\in\Sigma$, use Lemma 2.24 to choose partitions $V_{i1}\times
V_{j}=\bigcup_{\alpha\leq\ell_{1}}Q_{ij}^{\alpha}$ and $V_{i2}\times
V_{j}=\bigcup_{\ell_{1}+1\leq\alpha\leq\ell}Q_{ij}^{\alpha}$ so that for each
$1\leq\alpha\leq\ell_{1}$, $Q_{ij}^{\alpha}$ has
$\textnormal{disc}_{2}(\epsilon_{1}(\ell_{1}),1/\ell_{1})$ in $V_{i1}\times
V_{j}$, and for each $\ell_{1}+1\leq\alpha\leq\ell$, $Q_{ij}^{\alpha}$ has
$\textnormal{disc}_{2}(\epsilon_{1}(\ell_{2}),1/\ell_{2})$ in $V_{i1}\times
V_{j}$. Clearly each $Q_{ij}^{\alpha}$ fails
$\textnormal{disc}_{2}(\epsilon_{2}(\ell),1/\ell)$. Now define $\mathcal{Q}$
to have vertex partition $\\{V_{i}:i\in[t]\\}$ and edge partition

$\\{P_{ij}^{\alpha}:ij\in{[t]\choose
2}\setminus\Sigma,\alpha\leq\ell\\}\cup\\{Q_{ij}^{\alpha}:ij\in\Sigma,\alpha\leq\ell\\}.$

By construction, any triad from $\mathcal{Q}$ involving a pair
$V_{i}V_{j}\in\Sigma$ will be $\textnormal{disc}_{2}$-irregular, and thus
cannot be $\textnormal{disc}_{3}$-irregular. Any triad from $\mathcal{Q}$ not
involving a pair $V_{i}V_{j}$ from $\Sigma$ will be
$\textnormal{disc}_{2,3}$-regular, and thus cannot be
$\textnormal{disc}_{3}$-irregular. Thus $\mathcal{Q}$ has no
$\textnormal{disc}_{3}$-irregular triads.

Conversely, suppose $\mathcal{H}$ has the property that for all for all
$\ell_{0},t_{0}\geq 1$, $\epsilon_{1}>0$, all
$\epsilon_{2}:\mathbb{N}\rightarrow(0,1]$, there are $n_{0}$ and $T,L$ such
that for all $n\geq n_{0}$, every $G\in\mathcal{H}$ with at least $n_{0}$
vertices has an $(\epsilon_{1},\epsilon_{2})$-regular,
$(t,\ell,\epsilon_{2},\epsilon_{1})$-decomposition for some $t_{0}\leq t\leq
T$, and $\ell_{0}\leq\ell\leq L$, such that no triad of $\mathcal{P}$ is
$\textnormal{disc}_{3}$-irregular. By Lemma 6.35, there is $k$ such that
$\textnormal{HP}(k)\notin\text{Trip}(\mathcal{H})$, so by Fact 1.29,
$\mathcal{H}$ has finite $\textnormal{VC}_{2}$-dimension, and so by Theorem
1.31, $\mathcal{H}$ is $\textnormal{disc}_{2,3}$-homogeneous. Fix
$\epsilon_{1}>0$, a non-increasing $\epsilon_{2}:\mathbb{N}\rightarrow(0,1]$,
and $t_{0},\ell_{0}\geq 1$.

By above, there exist $n_{0}$, $L_{0}$ and $T_{0}$ so that for all $n\geq
n_{0}$, every $G\in\mathcal{H}$ with at least $n_{0}$ vertices, there are
$t_{0}\leq t\leq T_{0}$ and $\ell_{0}\leq\ell\leq L_{0}$ and a
$(t,\ell,\epsilon_{1},\epsilon_{2}(\ell))$-decomposition of $V(G)$ which is
$(\epsilon_{1},\epsilon_{2}(\ell))$-regular and
$\textnormal{disc}_{2,3}$-homogeneous with respect to $G$, and such that,
moreover, no triad from $\mathcal{P}$ is $\textnormal{disc}_{3}$-irregular
with respect to $G$.

Assume $n\geq n_{0}$ and $H=(V,E)\in\mathcal{H}_{n}$. By assumption, there
exists $t_{0}\leq t\leq T_{0}$, $\ell_{0}\leq\ell\leq L_{0}$ and
$\mathcal{P}$, a
$(t,\ell,\epsilon^{\prime}_{1},\epsilon_{2}^{\prime}(\ell))$-decomposition of
$V$ which is $(\epsilon_{1}^{\prime},\epsilon_{2}^{\prime}(\ell))$-regular and
$\textnormal{disc}_{2,3}$-homogeneous, and such that no triad of $\mathcal{P}$
is $\textnormal{disc}_{3}$-irregular with respect to $H$. Let $\Sigma$ be the
set of pairs $V_{i}V_{j}$ where at least
$(\epsilon^{\prime}_{1})^{1/2}|V_{i}||V_{j}|$ of the $xy\in K_{2}[V_{i}V_{j}]$
are in a $\textnormal{disc}_{2}$-irregular $P\in\mathcal{P}_{edge}$. By
assumption, $|\Sigma|\leq(\epsilon_{1}^{\prime})^{1/2}t^{2}$.

Set $s=\lceil(\epsilon_{1}^{\prime})^{1/2}\ell\rceil$. Fix $ij\notin\Sigma$.
By reindexing if necessary, we may assume that
$P_{ij}^{s+1},\ldots,P_{ij}^{\ell}$ all satisfy
$\textnormal{disc}_{2}(\epsilon_{2}^{\prime}(\ell),1/\ell)$. Set
$E^{\prime}_{0}=\bigcup_{i=1}^{s}P_{ij}^{\alpha}$, and for each $s+1\leq
u\leq\ell$, set $E^{\prime}_{u-s}=P_{ij}^{u}$. Note the density of
$E_{0}^{\prime}=\frac{s}{\ell}(1\pm s\epsilon^{\prime}_{2}(\ell))$.

Apply Lemma 2.24 to $E^{\prime}_{0}$ with $\epsilon=\delta=\epsilon_{2}(\ell)$
and $p=1/(\ell-s)$ to obtain $R_{ij}^{1},\ldots,R_{ij}^{\ell-s}$, where each
$R_{ij}^{u}$ has
$\textnormal{disc}_{2}(2s\epsilon^{\prime}_{2}(\ell)^{1/2},\frac{s}{\ell(\ell-s)})$.
For each $1\leq m\leq\ell-s$, let $Q_{ij}^{m}=S_{ij}^{m}\cup R_{ij}^{m}$. By
Fact 2.23, each $Q_{ij}^{m}$ has
$\textnormal{disc}_{2}(2s\epsilon^{\prime}_{2}(\ell)^{1/2},\frac{1}{\ell}+\frac{s}{\ell(\ell-s)})$.
It is not hard to check that
$\frac{1}{\ell}+\frac{s}{\ell(\ell-s)}=\frac{1}{\ell-s}$. Thus, each
$Q_{ij}^{m}$ has
$\textnormal{disc}_{2}(\epsilon_{2}(k^{\prime}),\frac{1}{k^{\prime}})$ (using
choice of $\epsilon_{2}^{\prime}$), where $k^{\prime}=\ell-s$. Given
$ij\notin\Sigma$, choose any partition $V_{i}\times V_{j}=\bigcup_{\alpha\leq
k^{\prime}}Q_{ij}^{\alpha}$.

Let $\mathcal{Q}$ consist of $\\{V_{1},\ldots,V_{t}\\}$, and
$\\{Q_{ij}^{\alpha}:ij\in{[t]\choose 2}\\}$. By construction, this is a
$(t,k^{\prime},\epsilon_{1},\epsilon_{2}(k^{\prime}))$-decomposition of $V$.
Suppose $ij,ik,jk\notin\Sigma$, and consider a triad of the form
$Q_{ijk}^{\alpha,\beta,\gamma}=(V_{i}\cup V_{j}\cup V_{k},Q_{ij}^{\alpha}\cup
Q_{ik}^{\beta}\cup Q_{jk}^{\gamma})$, for some $1\leq\alpha,\beta,\gamma\leq
k^{\prime}$. By construction, there was some triad of the form
$P_{ijk}^{\alpha^{\prime},\beta^{\prime},\gamma^{\prime}}$ which had
$\textnormal{disc}_{2}(\epsilon_{2}^{\prime}(\ell),1/\ell)$ such that

$|Q_{ij}^{\alpha}\setminus P_{ij}^{\alpha}|<\frac{s}{\ell
k^{\prime}}(1+2s\epsilon_{2}^{\prime}(\ell))|V_{i}||V_{j}|<\epsilon^{2}_{1}|Q_{ij}^{\alpha}|,$

where the inequality is because $s\leq(\epsilon_{1}^{\prime})^{1/2}\ell+1$ and
$\epsilon_{1}^{\prime}\ll\epsilon_{1}$. By assumption,
$P_{ijk}^{\alpha^{\prime},\beta^{\prime},\gamma^{\prime}}$ was a
$\textnormal{disc}_{2,3}$-regular triad of $\mathcal{P}$. We show
$Q_{ijk}^{\alpha,\beta,\gamma}$ is a $\textnormal{disc}_{2,3}$-regular triad
of $\mathcal{Q}$. By Proposition 2.22, it suffices to show the density on
$Q_{ijk}^{\alpha,\beta,\gamma}$ is in
$[0,\epsilon_{1}^{2})\cup(1-\epsilon_{1}^{2},1]$. Since
$P_{ijk}^{\alpha^{\prime},\beta^{\prime},\gamma^{\prime}}$ has
$\textnormal{disc}_{2}(\epsilon_{2}^{\prime}(\ell),1/\ell)$, it is by
assumption, $\textnormal{disc}_{2,3}$-regular, and thus also
$\textnormal{disc}_{2,3}$-homogeneous. Thus there is $u\in\\{0,1\\}$ such that

$|E^{u}\cap
K_{3}^{(2)}(P_{ijk}^{\alpha^{\prime},\beta^{\prime},\gamma^{\prime}})|\geq(1-\epsilon_{1}^{\prime})|K_{3}^{(2)}(P_{ijk}^{\alpha^{\prime},\beta^{\prime},\gamma^{\prime}})|.$

Then, using Corollary 2.6,

$\displaystyle|E^{u}\cap K_{3}^{(2)}(Q_{ijk}^{\alpha,\beta,\gamma})|$
$\displaystyle\geq|K_{3}^{(2)}(Q_{ijk}^{\alpha,\beta,\gamma})|-\epsilon_{1}^{\prime}|K_{3}^{(2)}(P_{ijk}^{\alpha^{\prime},\beta^{\prime},\gamma^{\prime}})|-\frac{9\epsilon_{1}^{2}}{(k^{\prime})^{3}}|V_{i}||V_{j}||V_{k}|$
$\displaystyle\geq\frac{|V_{i}||V_{j}||V_{k}|}{(k^{\prime})^{3}}\Big{(}1-\epsilon_{1}^{2}-\epsilon_{1}^{\prime}\frac{(k^{\prime})^{3}}{\ell^{3}}-9\epsilon_{1}^{2}\Big{)}$
$\displaystyle\geq(1-\epsilon_{1})|K_{3}^{(2)}(Q_{ijk}^{\alpha,\beta,\gamma})|,$

where the inequality is by our choice of
$\epsilon_{1}^{\prime}\ll\epsilon_{1}$ and since
$k^{\prime}\geq(1-\epsilon_{1})\ell$. Thus $Q_{ijk}^{\alpha,\beta,\gamma}$ has
$\textnormal{disc}_{2,3}(\epsilon_{1},\epsilon_{2}(k^{\prime}))$. Thus in
$\mathcal{Q}$ all irregular triads use a pair from $\Sigma$, so it has binary
$\textnormal{disc}_{2,3}$-error, as desired. ∎

##  Appendix A Facts about $\sim$-classes

This section shows various facts about $\sim$-classes. We begin with
Proposition 1.26, which says that all the decomposition properties of interest
in this paper are closed under $\sim$-classes. This boils down to the
following two lemmas.

######  Lemma A.1.

For all $\epsilon>0$ and $T\geq 1$, there is $\delta>0$ so that the following
holds. Suppose $H=(V,E)$, and $H^{\prime}=(V,E^{\prime})$ are two graphs on
the same vertex set $V$, and assume $H$ and $H^{\prime}$ are $\delta$-close.
Suppose $V_{1},\ldots,V_{t}$ is an equipartition of $V$ with $t\leq T$. If
$ijk\in{[t]\choose 3}$ and $V_{i}V_{j}V_{k}$ is has
$\textnormal{vdisc}_{3}(\epsilon)$ in $H$ with density $r$, then it has
$\textnormal{vdisc}_{3}(3\epsilon)$ in $H^{\prime}$ with density
$r\pm\epsilon$.

###### Proof.

Fix $\epsilon>0$ and $T\geq 1$. Define $\delta=\epsilon^{2}/T^{3}$ and
$N=\epsilon^{-1}T$. Suppose $H=(V,E)$, and $H^{\prime}=(V,E^{\prime})$ are two
graphs on the same vertex set $V$ of size $n\geq N$, and assume $H$ and
$H^{\prime}$ are $\delta$-close. Suppose $V_{1},\ldots,V_{t}$ is an
equipartition of $V$ with $t\leq T$. Suppose $ijk\in{[t]\choose 3}$ and
$V_{i}V_{j}V_{k}$ is has $\textnormal{vdisc}_{3}(\epsilon)$ in $H$ with
density $r$. Then

$|E^{\prime}\cap K_{3}[V_{i},V_{j},V_{k}]|=|E\cap
K_{3}[V_{i},V_{j},V_{k}]|\pm\delta|V|^{3}=r|V_{i}||V_{j}||V_{k}|\pm\delta
n^{3}=(r\pm\delta t^{3})|V_{i}||V_{j}||V_{k}|.$

By definition of $\delta$ and since $t\leq T$, this shows the density of
$V_{i}V_{j}V_{k}$ in $H^{\prime}$ is within $\epsilon$ of $r$. Suppose now
that $V_{i}^{\prime}\subseteq V_{i}$, $V_{j}^{\prime}\subseteq V_{j}$, and
$V_{k}^{\prime}\subseteq V_{k}$. Then, since $H$ and $H^{\prime}$ are $\delta$
close, and $V_{i}V_{j}V_{k}$ has $\textnormal{vdisc}_{3}(\epsilon)$ in $H$,

$\displaystyle|E^{\prime}\cap
K_{3}[V^{\prime}_{i},V^{\prime}_{j},V^{\prime}_{k}]|=|E\cap
K_{3}[V^{\prime}_{i},V^{\prime}_{j},V^{\prime}_{k}]|\pm\delta|V|^{3}$
$\displaystyle=(r\pm\epsilon)|V^{\prime}_{i}||V^{\prime}_{j}||V^{\prime}_{k}|\pm\delta
n^{3}$ $\displaystyle=(r\pm 2\epsilon)|V_{i}||V_{j}||V_{k}|.$

Since $V_{i}V_{j}V_{k}$ has density $r\pm\epsilon$, this shows
$V_{i}V_{j}V_{k}$ satisfies $\textnormal{vdisc}_{3}(3\epsilon)$ in
$H^{\prime}$. ∎

######  Lemma A.2.

For all $\epsilon>0$, there is $\epsilon^{*}_{2}:\mathbb{N}\rightarrow(0,1]$
such that for all $\epsilon_{2}:\mathbb{N}\rightarrow(0,1]$ satisfying
$\epsilon_{2}(x)\leq\epsilon_{2}^{*}(x)$ for all $x\geq 1$, and all $L,T\geq
1$, there is $\delta>0$ so that the following holds. Suppose $H=(V,E)$, and
$H^{\prime}=(V,E^{\prime})$ are two graphs on the same vertex set $V$ of size
$n\geq N$, such that $H$ and $H^{\prime}$ are $\delta$-close. Assume
$\mathcal{P}$ is a $(t,\ell,\epsilon_{1},\epsilon_{2}(\ell))$-decomposition of
$V$. Then for any
$G_{ijk}^{\alpha,\beta,\gamma}\in\operatorname{Triads}(\mathcal{P})$
satisfying $\textnormal{disc}_{2,3}(\epsilon_{1},\epsilon_{2}(\ell))$ with
respect to $H$ with density $r$, then $G_{ijk}^{\alpha,\beta,\gamma}$
satisfies $\textnormal{disc}_{2,3}(3\epsilon_{1},\epsilon_{2}(\ell))$ with
respect to $H^{\prime}$ with density $r\pm 2\epsilon_{1}$.

###### Proof.

Fix $\epsilon>0$. Define $\epsilon_{2}^{*}:\mathbb{N}\rightarrow(0,1]$ so that
$\epsilon_{2}^{*}(x)\ll\epsilon/x^{2}$ for all $x\geq 1$. Now suppose
$\epsilon_{2}:\mathbb{N}\rightarrow(0,1]$ satisfies
$\epsilon_{2}(x)\leq\epsilon_{2}^{*}(x)$ for all $x\geq 1$, and $L,T\geq 1$.
Choose $\delta\ll\epsilon_{1}^{4}\epsilon_{2}(L)^{2}L^{-3}T^{-3}$.

Suppose $H=(V,E)$, and $H^{\prime}=(V,E^{\prime})$ are two graphs on the same
vertex set $V$, and assume $H$ and $H^{\prime}$ are $\delta$-close. Suppose
$\mathcal{P}$ is a $(t,\ell,\epsilon_{1},\epsilon_{2}(\ell))$-decomposition of
$V$. Suppose $G\in\operatorname{Triads}(\mathcal{P})$ has
$\textnormal{disc}_{2,3}(\epsilon_{1},\epsilon_{2}(\ell))$ in $H$ with density
$r$. Then using Corollary 2.6,

$|(E\Delta E^{\prime})\cap K_{3}(G)|\leq\delta
n^{3}\leq\epsilon^{2}_{1}|K_{3}(G)|.$

Consequently, if $r^{\prime}$ is the density of $G$ with respect to
$H^{\prime}$, then $|r^{\prime}-r|\leq\frac{|(E\Delta E^{\prime})\cap
K_{3}(G)|}{|K_{3}(G)|}\leq\epsilon_{1}^{2}$. Now suppose $G^{\prime}\subseteq
G$ is a subgraph. Then since $G$ has
$\textnormal{disc}_{2,3}(\epsilon_{1},\epsilon_{2}(\ell))$ with respect to $H$
with density $r$,

$\displaystyle\Big{|}|E\cap
K_{3}^{(2)}(G^{\prime})|-r|K_{3}^{(2)}(G^{\prime})|\Big{|}\leq\epsilon_{1}\frac{n^{3}}{\ell^{3}t^{3}}.$

Thus

$\displaystyle||E^{\prime}\cap
K_{3}^{(2)}(G^{\prime})|-r^{\prime}|K_{3}^{(2)}(G^{\prime})||$
$\displaystyle\leq||E^{\prime}\cap K_{2}^{(2)}(G^{\prime})|-|E\cap
K_{3}^{(2)}(G^{\prime})||+||E\cap
K_{3}^{(2)}(G^{\prime})|-r^{\prime}|K_{3}^{(2)}(G^{\prime})||$
$\displaystyle\leq\delta n^{3}+||E\cap
K_{2}^{(2)}(G^{\prime})|-r|K_{3}^{(2)}(G^{\prime})||+|r-r^{\prime}||K_{3}^{(2)}(G^{\prime})|$
$\displaystyle\leq\delta
n^{3}+\epsilon_{1}\frac{n^{3}}{\ell^{3}t^{3}}+\epsilon_{1}^{2}|K_{3}^{(2)}(G^{\prime})|$
$\displaystyle\leq 3\epsilon_{1}\frac{n^{3}}{\ell^{3}t^{3}}.$

This shows that $G$ has
$\textnormal{disc}_{2,3}(3\epsilon_{1},\epsilon_{2}(\ell))$ with respect to
$H^{\prime}$ with density $r^{\prime}$. ∎

Proof of Proof of Proposition 1.26: Assume $\mathcal{H}$ and
$\mathcal{H}^{\prime}$ are hereditary $3$-graph properties and $\mathcal{H}$
is close to $\mathcal{H}^{\prime}$. Suppose $\mathcal{H}^{\prime}$ satisfies
one of the following.

  1. (a)

$\mathcal{H}^{\prime}$ is $\textnormal{vdisc}_{3}$-homogeneous.

  2. (b)

$\mathcal{H}^{\prime}$ admits binary $\textnormal{vdisc}_{3}$-error.

  3. (c)

$\mathcal{H}^{\prime}$ admits zero $\textnormal{vdisc}_{3}$-homogeneous.

  4. (d)

$\mathcal{H}^{\prime}$ is $\textnormal{disc}_{2,3}$-homogeneous.

  5. (e)

$\mathcal{H}^{\prime}$ admits linear $\textnormal{vdisc}_{3}$-error.

  6. (f)

$\mathcal{H}^{\prime}$ admits binary $\textnormal{vdisc}_{3}$-error.

  7. (g)

$\mathcal{H}^{\prime}$ admits zero $\textnormal{vdisc}_{3}$-error.

Then we show $\mathcal{H}$ satisfies each of these, respectively. Assume first
that (a), (b), or (c) hold. Fix $\epsilon>0$ and $t_{0}\geq 1$. By assumption,
there exist $T=T(\epsilon/2,t_{0})$, $N=N(\epsilon/2,t_{0})$ be such that for
every $n\geq N$, the following holds. For every
$G\in\mathcal{H}^{\prime}_{n}$, there is a decomposition
$V(G)=V_{1}\cup\ldots\cup V_{t}$ for some $t_{0}\leq t\leq T$, such that the
following holds (respectively).

  1. (1)

There is $\Sigma\subseteq{[t]\choose 3}$ such that $|\Sigma|\leq\epsilon
t^{3}/5$ and for all $ijk\notin\Sigma$, $V_{i}V_{j}V_{k}$ is
$\epsilon/5$-homogeneous with respect to $G$.

  2. (2)

There is $\Gamma\subseteq{[t]\choose 2}$ such that $|\Gamma|\leq\epsilon
t^{2}/5$ and for all $ijk\in{[t]\choose 3}$ with $ij,jk,ik\notin\Gamma$,
$(V_{i},V_{j},V_{k})$ has $\textnormal{vdisc}_{3}(\epsilon/5)$ with respect to
$G$.

  3. (3)

For all $ijk\in{[t]\choose 3}$, $V_{i}V_{j}V_{k}$ is satisfies
$\textnormal{vdisc}_{3}(\epsilon/5)$ with respect to $G$.

Let $\delta$ be as in Lemma A.1 for $\epsilon/5$ and $T$. Choose $N^{\prime}$
sufficiently large so that for every $n\geq N^{\prime}$ and
$G\in\mathcal{H}_{n}$, there is $G^{\prime}\in\mathcal{H}^{\prime}_{n}$ such
that $G$ and $G^{\prime}$ are $\delta$-close. Now assume $n\geq N^{\prime}$
and $G=(V,E)\in\mathcal{H}$ with $|V|=n$. Then there is
$G^{\prime}=(V,E^{\prime})\in\mathcal{H}^{\prime}$ which is $\delta$-close to
$G$. Further, there are $t_{0}\leq t\leq T$ and an equipartition
$V=V_{1}\cup\ldots\cup V_{t}$ such that the following holds (respectively).

  1. (1)

There is $\Sigma\subseteq{[t]\choose 3}$ such that $|\Sigma|\leq\epsilon
t^{3}/5$ and for all $ijk\notin\Sigma$, $V_{i}V_{j}V_{k}$ is
$\epsilon/5$-homogeneous with respect to $G$.

  2. (2)

There is $\Gamma\subseteq{[t]\choose 2}$ such that $|\Gamma|\leq\epsilon
t^{2}/5$ and for all $ijk\in{[t]\choose 3}$ with $ij,jk,ik\notin\Gamma$,
$(V_{i},V_{j},V_{k})$ has $\textnormal{vdisc}_{3}(\epsilon/5)$ with respect to
$G$.

  3. (3)

For all $ijk\in{[t]\choose 3}$, $V_{i}V_{j}V_{k}$ satisfies
$\textnormal{vdisc}_{3}(\epsilon/5)$ with respect to $G$.

By Lemma A.1, the following holds (respecitvely).

  1. (1)

For all $ijk\notin\Sigma$, $V_{i}V_{j}V_{k}$ is $\epsilon$-homogeneous with
respect to $G^{\prime}$.

  2. (2)

For all $ijk\in{[t]\choose 3}$ with $ij,jk,ik\notin\Gamma$,
$(V_{i},V_{j},V_{k})$ has $\textnormal{vdisc}_{3}(\epsilon)$ with respect to
$G^{\prime}$.

  3. (3)

For all $ijk\in{[t]\choose 3}$, $V_{i}V_{j}V_{k}$ satisfies
$\textnormal{vdisc}_{3}(\epsilon)$ with respect to $G^{\prime}$.

Thus we have shown that $\mathcal{H}$ satisfies (a), (b), or (c),
respectively.

Assume now that (d), (e), (f), or (g) hold, respectively. Fix
$\epsilon_{1}>0$, $\epsilon_{2}:\mathbb{N}\rightarrow(0,1]$, and
$t_{0},\ell_{0}\geq 1$. Let $\epsilon_{2}^{*}$ be as in Lemma A.2 for
$\epsilon_{1}/5$. Let
$\epsilon_{2}^{\prime}(x)=\min\\{\epsilon_{2}(x),\epsilon_{2}^{*}(x)\\}$.
Given $\ell_{0},t_{0}\geq 1$, choose $N,T,L$ such that for every
$G=(V,E)\in\mathcal{H}^{\prime}$ on at least $N$ vertices, there are
$t_{0}\leq t\leq T$ and $\ell_{0}\leq\ell\leq L$ and an
$(\epsilon_{1}/5,\epsilon^{\prime}_{2}(\ell),t,\ell)$-decomposition
$\mathcal{P}$ of $V$ such that the following hold (respectively).

  1. (1)

There is $\Sigma\subseteq{[t]\choose 3}$ such that
$|\Sigma|\leq\epsilon_{1}t^{3}/5$ and for all $ijk\notin\Sigma$, every triad
$P\in\operatorname{Triads}(\mathcal{P})$ is $\epsilon_{1}/5$-homogeneous with
respect to $G$.

  2. (2)

There is $\Sigma\subseteq{[t]\choose 3}$ such that
$|\Sigma|\leq\epsilon_{1}t^{3}/5$ and for all $ijk\in{[t]\choose
3}\setminus\Sigma$, every triad $P\in\operatorname{Triads}(\mathcal{P})$
satisfies $\textnormal{disc}_{2,3}(\epsilon_{1}/5,\epsilon_{2}(\ell))$ with
respect to $G$.

  3. (3)

There is $\Gamma\subseteq{[t]\choose 2}$ such that
$|\Gamma|\leq\epsilon_{1}t^{2}/5$ and for all $ijk\in{[t]\choose 3}$ with
$ij,jk,ik\notin\Gamma$, every triad $P\in\operatorname{Triads}(\mathcal{P})$
satisfies $\textnormal{disc}_{2,3}(\epsilon_{1}/5,\epsilon_{2}(\ell))$ with
respect to $G$.

  4. (4)

Every triad $P\in\operatorname{Triads}(\mathcal{P})$ satisfies
$\textnormal{disc}_{2,3}(\epsilon_{1}/5,\epsilon_{2}(\ell))$ with respect to
$G$.

Let $\delta$ be as in Lemma A.2 for $e_{1}/5$, $\epsilon^{\prime}_{2}$, $T$
and $L$. Let $N$ be such that any $G\in\mathcal{H}$ on at least $N$ vertices
is $\delta$-close to some element of $\mathcal{H}^{\prime}$. Now assume $n\geq
N$ and $G=(V,E)\in\mathcal{H}$ with $|V|=E$. Then there is
$G^{\prime}=(V,E^{\prime})\in\mathcal{H}^{\prime}$ which is $\delta$-close to
$G$. By assumption there are $t_{0}\leq t\leq T$ and $\ell_{0}\leq\ell\leq L$
and a $(t,\ell,\epsilon_{1}/5,\epsilon^{\prime}_{2}(\ell))$-decomposition
$\mathcal{P}$ of $V$ such that the following hold (respectively).

  1. (1)

There is $\Sigma\subseteq{[t]\choose 3}$ such that
$|\Sigma|\leq\epsilon_{1}t^{3}/5$ and for all $ijk\notin\Sigma$, every triad
$P_{ijk}^{\alpha,\beta,\gamma}\in\operatorname{Triads}(\mathcal{P})$ is
$\epsilon_{1}/5$-homogeneous with respect to $G^{\prime}$.

  2. (2)

There is $\Sigma\subseteq{[t]\choose 3}$ such that
$|\Sigma|\leq\epsilon_{1}t^{3}/5$ and for all $ijk\in{[t]\choose
3}\setminus\Sigma$, every triad $P\in\operatorname{Triads}(\mathcal{P})$
satisfies
$\textnormal{disc}_{2,3}(\epsilon_{1}/5,\epsilon^{\prime}_{2}(\ell))$ with
respect to $G^{\prime}$.

  3. (3)

There is $\Gamma\subseteq{[t]\choose 2}$ such that
$|\Gamma|\leq\epsilon_{1}t^{2}/5$ and for all $ijk\in{[t]\choose 3}$ with
$ij,jk,ik\notin\Gamma$, every triad $P\in\operatorname{Triads}(\mathcal{P})$
satisfies
$\textnormal{disc}_{2,3}(\epsilon_{1}/5,\epsilon^{\prime}_{2}(\ell))$ with
respect to $G^{\prime}$.

  4. (4)

Every triad $P\in\operatorname{Triads}(\mathcal{P})$ satisfies
$\textnormal{disc}_{2,3}(\epsilon_{1}/5,\epsilon^{\prime}_{2}(\ell))$ with
respect to $G^{\prime}$.

By Lemma A.2, the following hold (respectively).

  1. (1)

For all $ijk\notin\Sigma$, every $P\in\operatorname{Triads}(\mathcal{P})$ is
$\epsilon_{1}$-homogeneous with respect to $G^{\prime}$.

  2. (2)

For all $ijk\in{[t]\choose 3}\setminus\Sigma$, every
$P\in\operatorname{Triads}(\mathcal{P})$ satisfies
$\textnormal{disc}_{2,3}(\epsilon_{1},\epsilon^{\prime}_{2}(\ell))$ with
respect to $G^{\prime}$.

  3. (3)

For all $ijk\in{[t]\choose 3}$ with $ij,jk,ik\notin\Gamma$, every
$P\in\operatorname{Triads}(\mathcal{P})$ satisfies
$\textnormal{disc}_{2,3}(\epsilon_{1},\epsilon^{\prime}_{2}(\ell))$ with
respect to $G^{\prime}$.

  4. (4)

Every $P\in\operatorname{Triads}(\mathcal{P})$ satisfies
$\textnormal{disc}_{2,3}(\epsilon_{1}/5,\epsilon^{\prime}_{2}(\ell))$ with
respect to $G^{\prime}$.

This shows that $\mathcal{H}$ has (d), (e), (f), or (g), respectively. ∎

We now prove Theorem 1.38, whose proof is very similar to that of Theorem
1.48.

Proof of Theorem 1.38: Suppose $\text{Trip}(\mathcal{H})$ contains
$\overline{U}(n)$ for all $n$. Fix a WNIP property $\mathcal{H}^{\prime}$. We
show $\mathcal{H}$ is far from $\mathcal{H}^{\prime}$. By assumption, there is
some $k$ so that $U^{*}(k)\notin\text{Trip}(\mathcal{H}^{\prime})$. Let
$\epsilon=(1/2k)^{2^{k}+k+1}/|\mathcal{B}(U^{*}(k))|$ and let $N\gg
2^{k}\epsilon^{-1}$. For all $n\geq N$, there is $G=(V,E)\in\mathcal{H}$ such
that $\text{Trip}(G)$ contains $\overline{U}(n)$ and an induced sub-$3$-graph.
This means there are $\\{a_{i},c_{i}:i\in[n]\\}\subseteq V$ and
$\\{b_{S}:S\subseteq\\{c_{1},\ldots,c_{n}\\}\\}\subseteq V$ such that
$a_{i}b_{S}c_{t}\in E$ if and only if $c_{t}\in S$. Set $n_{1}=\lfloor
n/k\rfloor$ and choose $C_{1},\ldots,C_{k}$ to be disjoint subsets of
$\\{c_{1},\ldots,c_{kn_{1}}\\}$ of size $n_{1}$. For each $X\subseteq[k]$, let

$B_{X}=\\{b_{S}:\text{ for each }i\in X,C_{i}\subseteq S\text{ and for each
}i\notin X,C_{i}\cap S=\emptyset\\}.$

Note $|B_{X}|\geq 2^{n-kn_{1}}$, so we can take $B_{X}^{\prime}\subseteq
B_{X}$ of size $n_{1}$. We construct many induced subgraphs of $G$ as follows.

  1. (1)

Choose $a_{i}$ for some $i\in[n]$. There are $n$ choices.

  2. (2)

Choose some $(c_{i_{1}},\ldots,c_{i_{k}})\in C_{1}\times\ldots\times C_{k}$.
There are $n_{1}^{k}$ choices.

  3. (3)

For each $X\subseteq[k]$, choose some $d_{X}\in B^{\prime}_{X}$. There are
$n_{1}^{2^{k}}$ choices.

  4. (4)

Put
$G[\\{a_{i}\\}\cup\\{c_{i_{1}},\ldots,c_{i_{k}}\\}\cup\\{d_{X}:X\subseteq[k]\\}]$
in $S$.

By construction, every element of $S$ is isomorphic to some element in
$\mathcal{B}(U^{*}(k))$ and

$|S|\geq n_{1}^{k+2^{k}+1}>\epsilon|\mathcal{B}(U^{*}(k))|n^{k+2^{k}+1},$

where the inequality is by definition of $n_{1}$ and $\epsilon$. By the
pigeonhole principle, there is some $G(n)\in\mathcal{B}(U^{*}(k))$ so that $S$
contains at least $\epsilon n^{k+2^{k}+1}$ elements isomorphic to $G(n)$. By
the pigeonhole principle, there is $G^{\prime}\in\mathcal{B}(U^{*}(k))$ so
that $G^{\prime}=G(n)$ for arbitrarily large $n$. By definition, this implies
$G^{\prime}\in\Delta(\mathcal{H})$. Clearly
$G^{\prime}\notin\Delta(\mathcal{H}^{\prime})$ (since
$U^{*}(k)\notin\text{Trip}(\mathcal{H}^{\prime})$), so $\mathcal{H}$ is far
from $\mathcal{H}^{\prime}$.

Conversely, suppose $\mathcal{H}$ is far from every WNIP property
$\mathcal{H}^{\prime}$. By Lemma 2.31, $\mathcal{H}^{\prime}$ is WNIP if and
only if, for some $k\geq 1$, $\mathcal{H}^{\prime}$ contains no clean copies
of $U^{*}(k)$. Thus, since $\mathcal{H}$ is far from every WNIP property, we
know that for all $k\geq 1$, there is $\delta>0$ so that for arbitrarily large
$n$, there is $G(n)\in\mathcal{H}$ and $\Gamma(n)\in\mathcal{B}(U^{*}(k))$ so
that $G(n)$ is not $\delta/|\mathcal{B}(U^{*}(k))|$-close to being
$\Gamma(n)$-free. For each $\Gamma\in\mathcal{B}(U^{*}(k))$, let
$c_{k}(\Gamma)$, $N_{k}(\Gamma)$ be as in Theorem 2.14 for $\Gamma$ and
$\delta/|\mathcal{B}(U^{*}(k))|$-close. Then set
$c_{k}=\min\\{c_{k}(\Gamma):\Gamma\in\mathcal{B}(U^{*}(k))\\}$ and
$N_{k}=\max\\{N_{k}(\Gamma):\Gamma\in\mathcal{B}(U^{*}(k))\\}$. Choose any
$N>N_{k}$. Then there is some $n\geq N$, so that that $G(n)$ is not
$\delta$-close to being $\Gamma(n)$-free. Say
$V(\Gamma(n))=\\{a,b_{i},c_{S}:i\in[k],S\subseteq[k]\\}$ and $ab_{i}c_{S}\in
E(\Gamma(n))$ if and only if $i\in S$. By Theorem 2.14, $G$ contains at least
$c_{k}n^{k+1+2^{k}}$ induced sub-$3$-graphs isomorphic to $\Gamma(n)$. Let $S$
be the set of these induced sub-$3$-graphs. For each $H\in S$, there is a
vertex $a_{H}$ and sets $D_{H}=\\{d^{H}_{i}:i\in[k]\\}$,
$E_{H}=\\{e_{S}^{H}:S\subseteq[k]\\}$, such that $a_{H}d_{H}^{i}e_{S}^{H}\in
E$ if and only if $i\in S$. Since $|S|\geq c_{k}n^{k+1+2^{k}}$, there are sets
$D$ and $E$ and $X\subseteq S$ of size at least $c_{k}n/k!(2^{k})!$ such that
$(D,E)=(D_{H},E_{H})$ for all $H\in X$. Then we must have that $\\{a_{H}:H\in
X\\}|=|X|$. Let $Y\subseteq\\{a_{H}:H\in X\\}$ any set of size $k$. Then
$G[Y\cup D\cup E]\in\mathcal{H}$ and $\text{Trip}(G[Y\cup D\cup
E])\cong\overline{U}(k)$. Thus $\overline{U}(k)\in\text{Trip}(\mathcal{H})$. ∎

##  Appendix B Lemmas about combining and refining decompositions

In this section, we prove the results stated in Section 2.2. We will also
prove Theorem 3.1 here, as it uses some of these lemmas.

We begin with the proof of Corollary 2.6.

Proof of Corllary 2.6: Fix $t\geq 2$, $\epsilon>0$ and $r\in(0,1]$. Without
loss of generality, assume $\epsilon\leq 1/2$. Choose
$\mu\ll_{t}\gamma\ll_{t}\epsilon,r$.

Now assume $V=U_{1}\cup\ldots\cup U_{t}$ and $G=(V,E)$ is a $t$-partite graph
with vertex partition $U_{1},\ldots,U_{t}$, such that for each $1\leq i<j\leq
t$, $G[U_{i},U_{j}]$ has $\textnormal{disc}_{2}(\mu,r)$. For each $1\leq
i<j\leq t$, let $d_{ij}$ be such that $|E\cap
K_{2}[U_{i},U_{j}]|=d_{ij}|U_{i}||U_{j}|$. By assumption, each
$d_{ij}=r\pm\mu$. By Proposition 2.5,

$\Big{|}K_{t}(G)|-\prod_{ij\in{[t]\choose
2}}d_{ij}\prod_{i=1}^{t}|U_{i}|\Big{|}\leq\gamma\prod_{i=1}^{t}|U_{i}|.$

Let $d=\prod_{ij\in{[t]\choose 2}}d_{ij}$. Note $d=(1\pm\mu)^{t\choose
2}r^{t\choose 2}=(1\pm\epsilon/2)r^{t\choose 2}$, where the last equality is
since $\mu\ll\epsilon$. Thus

$|K_{t}(G)|=(d\pm\gamma)\prod_{i=1}^{t}|U_{i}|=d\Big{(}1\pm\gamma
d^{-1}\Big{)}\prod_{i=1}^{t}|U_{i}|$

Since $d=(1\pm\epsilon/2)r^{t\choose 2}$ and $\gamma\ll r,\epsilon$, $\gamma
d^{-1}\in(-2\epsilon^{2},2\epsilon^{2})$. Thus

$|K_{t}(G)|=(1\pm 2\epsilon^{2})d\prod_{i=1}^{t}|U_{i}|=(1\pm
2\epsilon^{2})(1\pm\epsilon/2)r^{t\choose 2}\prod_{i=1}^{t}|U_{i}|.$

Since $\epsilon\leq 1/2$ this is equal to $(1\pm\epsilon)r^{t\choose
2}\prod_{i=1}^{t}|U_{i}|$, as desired. ∎

We now prove Lemma 2.19.

Proof of Lemma 2.19: Fix $k\geq 1$ and $\delta_{3}>0$. Let
$\delta_{3}^{\prime}=\delta_{3}/32k^{3}$. Suppose now $d_{2},d_{3}\in(0,1]$
and $0<\delta_{2}\leq d_{2}^{3}/8$. Set $\gamma=\delta_{2}/2k^{3}$ and let
$\mu=\mu(3,\gamma,d_{2})$ and $N_{1}=N_{1}(3,\gamma,d_{2})$ as in Proposition
2.5. Let
$\delta^{\prime}_{2}\ll\mu/4k^{2},\delta_{2}/4k^{2},d_{2}\delta_{2}/(6k^{4})$,
and choose $N\gg k,N_{1}$.

Suppose $V=V_{1}\cup V_{2}\cup V_{3}$ is a vertex set of size $n\geq N$, and
$G=(V_{1}\cup V_{2}\cup V_{3},E)$ is a $3$-partite graph. Assume $H=(V,R)$ is
a $3$-graph, and let $H^{\prime}=(V,R\cap K_{3}^{(2)}(G))$. Assume that for
each $1\leq i<j\leq 3$, $G[V_{i},V_{j}]$ has
$\textnormal{disc}_{2}(\delta^{\prime}_{2},d_{2})$, and $(H^{\prime},G)$ has
$\textnormal{disc}_{2,3}(\delta^{\prime}_{2},\delta^{\prime}_{3})$ with
density $d_{3}$. Suppose that for each $i\in[3]$, $V_{i}^{\prime}\subseteq
V_{i}$ satisfies $|V_{i}^{\prime}|=m^{\prime}_{i}\geq m_{i}/k$, where
$m_{i}:=|V_{i}|$. Set
$G^{\prime}=G[V^{\prime}_{1},V^{\prime}_{2},V^{\prime}_{3}]$ and
$H^{\prime\prime}=(V_{1}^{\prime}\cup V_{2}^{\prime}\cup V_{3}^{\prime},R\cap
K_{3}^{(2)}(G^{\prime}))$.

For each $1\leq i<j\leq 3$, let $d_{ij}$ be the density of $G[V_{i},V_{j}]$.
By assumption $d_{ij}=d_{2}\pm\delta_{2}^{\prime}$. By Lemma 2.18, for each
$ij\in{[3]\choose 2}$, $G^{\prime}[V_{i},V_{j}]$ has
$\textnormal{disc}_{2}(2k^{2}\delta^{\prime}_{2},d^{\prime}_{ij})$ for some
$d^{\prime}_{ij}=d_{ij}\pm k^{2}\delta^{\prime}_{2}$. Since
$\delta_{2}^{\prime}\ll\delta_{2}/4k^{2},\mu$, this means
$G^{\prime}[V_{i}^{\prime},V_{j}^{\prime}]$ has
$\textnormal{disc}_{2}(\mu,d_{2})$. Thus, by Proposition 2.5, we have

$\displaystyle|K_{3}^{(2)}(G^{\prime})|=d_{2}^{3}(1\pm\gamma)m^{\prime}_{1}m^{\prime}_{2}m^{\prime}_{3}.$

Since $(H^{\prime},G)$ has
$\textnormal{disc}_{2,3}(\delta^{\prime}_{2},\delta^{\prime}_{3})$,

$||R\cap
K_{3}^{(2)}(G^{\prime})|-d_{3}|K_{3}^{(2)}(G^{\prime})||\leq\delta^{\prime}_{3}d_{2}^{3}m_{1}m_{2}m_{3}.$

Therefore if $d_{3}^{\prime}$ is such that $|R\cap
K_{3}^{(2)}(G^{\prime})|=d_{3}^{\prime}|K_{3}^{(2)}(G^{\prime})|$, then

$\Big{|}d_{3}^{\prime}-d_{3}\Big{|}\leq\frac{\delta^{\prime}_{3}d_{2}^{3}m_{1}m_{2}m_{3}}{|K_{3}^{(2)}(G^{\prime})|}\leq\frac{\delta_{3}^{\prime}d_{2}^{3}m_{1}m_{2}m_{3}}{d_{2}^{3}(1-\gamma)m^{\prime}_{1}m^{\prime}_{2}m^{\prime}_{3}}\leq
2\delta_{3}^{\prime},$

where the last inequality is by assumption, because $\gamma\leq 1/2$, and
because each $m_{i}^{\prime}\geq m_{i}/k$. Suppose $G^{\prime\prime}\subseteq
G^{\prime}$. Since $(H^{\prime},G)$ has
$\textnormal{disc}_{2,3}(\delta_{2}^{\prime},\delta_{3}^{\prime})$,

$\Big{|}|R\cap
K_{3}^{(2)}(G^{\prime\prime})|-d_{3}|K_{3}^{(2)}(G^{\prime\prime})|\Big{|}\leq\delta^{\prime}_{3}d_{2}^{3}m_{1}m_{2}m_{3}\leq\delta_{3}d_{2}^{3}m^{\prime}_{1}m^{\prime}_{2}m^{\prime}_{3}/2,$

where the equality is by definition of $\delta_{3}^{\prime}$ and since each
$m_{i}\geq km_{0}$. Thus

$\displaystyle\Big{|}|R\cap
K_{3}^{(2)}(G^{\prime\prime})|-d_{3}^{\prime}|K_{3}^{(2)}(G^{\prime\prime})|\Big{|}$
$\displaystyle\leq\delta_{3}d_{2}^{3}m^{\prime}_{1}m^{\prime}_{2}m^{\prime}_{3}/2+\Big{|}d_{3}|K_{3}^{(2)}(G^{\prime\prime})|-d_{3}^{\prime}|K_{3}^{(2)}(G^{\prime\prime})|\Big{|}$
$\displaystyle\leq\delta_{3}d_{2}^{3}m^{\prime}_{1}m^{\prime}_{2}m^{\prime}_{3}/2+2\delta_{3}^{\prime}|K_{3}^{(2)}(G^{\prime\prime})|$
$\displaystyle\leq\delta_{3}d_{2}^{3}m^{\prime}_{1}m^{\prime}_{2}m^{\prime}_{3}/2+2\delta_{3}^{\prime}d_{2}^{3}(1+\gamma)m^{\prime}_{1}m^{\prime}_{2}m^{\prime}_{3}$
$\displaystyle\leq\delta_{3}d_{2}^{8}m^{\prime}_{1}m^{\prime}_{2}m^{\prime}_{3},$

where the last inequality is by definition of $\delta_{2}^{\prime}$ and
$\gamma$. This finishes our verification that $(H^{\prime\prime},G^{\prime})$
has $\textnormal{disc}_{2,3}(\delta_{3},\delta_{2})$. ∎

Proof of Fact 2.23: Assume $E_{1},E_{2}$ are disjoint subsets of $K_{2}[U,V]$.
We begin with part (a). Assume $(U\cup V,E_{1})$ has
$\textnormal{disc}_{2}(\epsilon_{1},d_{1})$, $(U\cup V,E_{2})$ has
$\textnormal{disc}_{2}(\epsilon_{2},d_{2})$. We show $(U\cup V,E_{1}\cup
E_{2})$ has $\textnormal{disc}_{2}(\epsilon_{1}+\epsilon_{2},d_{1}+d_{2})$.
Suppose $U^{\prime}\subseteq U$ and $V^{\prime}\subseteq V$. By assumption,
$||E_{1}\cap
K_{2}[U^{\prime},V^{\prime}]|-d_{1}|U^{\prime}||V^{\prime}||\leq\epsilon_{1}|U|V|$,
and $||E_{2}\cap
K_{2}[U^{\prime},V^{\prime}]|-d_{2}|U^{\prime}||V^{\prime}||\leq\epsilon|U||V|$.
Then since $E_{1}\cap E_{2}=\emptyset$,

$\displaystyle|(E_{1}\cup E_{2})\cap K_{2}[U^{\prime},V^{\prime}]|$
$\displaystyle=|E_{1}\cap K_{2}[U^{\prime},V^{\prime}]|+|E_{2}\cap
K_{2}[U^{\prime},V^{\prime}]|-|(E_{1}\cap E_{2})\cap
K_{2}[U^{\prime},V^{\prime}]|$ $\displaystyle=|E_{1}\cap
K_{2}[U^{\prime},V^{\prime}]|+|E_{2}\cap K_{2}[U^{\prime},V^{\prime}]|.$

By above, this is at most
$(d_{1}+d_{2})|U^{\prime}||V^{\prime}|+\epsilon_{1}|U||V|+\epsilon_{2}|U||V|$
and at least
$(d_{1}+d_{2})|U^{\prime}||V^{\prime}|-\epsilon_{1}|U||V|-\epsilon_{2}|U||V|$
since $(U\cup V,E_{1})$ has $\textnormal{disc}_{2}(\epsilon_{1},d_{1})$,
$(U\cup V,E_{2})$ has $\textnormal{disc}_{2}(\epsilon_{2},d_{2})$. Thus
$||(E_{1}\cup E_{2})\cap
K_{2}[U^{\prime},V^{\prime}]|-(d_{1}+d_{2})|U^{\prime}||V^{\prime}||\leq(\epsilon_{1}+\epsilon_{2})|U||V|$,
as desired.

We now show (b). Assume $(U\cup V,E_{1}\cup E_{2})$ has
$\textnormal{disc}_{2}(\epsilon,d)$, $(U\cup V,E_{1})$ has
$\textnormal{disc}_{2}(\epsilon_{1},d_{1})$. We show $(U\cup V,E_{2})$ has
$\textnormal{disc}_{2}(\epsilon+\epsilon_{2},d-d_{1})$. Suppose
$U^{\prime}\subseteq U$ and $V^{\prime}\subseteq V$. Then

$\displaystyle\Big{|}|E_{2}\cap
K_{2}[U^{\prime},V^{\prime}]|-(d-d_{1})|U^{\prime}||V^{\prime}|\Big{|}$
$\displaystyle=\Big{|}|(E_{1}\cup E_{2})\cap
K_{2}[U^{\prime},V^{\prime}]|-|E_{1}\cap
K_{2}[U^{\prime},V^{\prime}]|-(d-d_{1})|U^{\prime}||V^{\prime}|\Big{|}$
$\displaystyle\leq\Big{|}|(E_{1}\cup E_{2})\cap
K_{2}[U^{\prime},V^{\prime}]|-d|U^{\prime}||V^{\prime}|\Big{|}+\Big{|}|E_{1}\cap
K_{2}[U^{\prime},V^{\prime}]|-d_{1}|U^{\prime}||V^{\prime}|\Big{|}.$

By assumption, this is at most
$\epsilon|U||V|+\epsilon_{1}|U||V|=(\epsilon+\epsilon_{1})|U||V|$. This shows
$(U\cup V,E_{2})$ has $\textnormal{disc}_{2}(\epsilon+\epsilon_{2},d-d_{1})$.
∎

Our next goal is to prove Lemma 2.27. This will require two additional tools.
The first is a multi-colored version of Szemerédi’s regularity lemma (see e.g.
[30, 23]).

######  Theorem B.1 (Multi-colored regularity lemma).

For all $r\geq 1$, $\epsilon>0$, and $m\geq 1$, there is $M=M(\epsilon,m)$
such that the following holds. Suppose $G=(V,E_{1},\ldots,E_{r})$ where
$|V|\geq M$ and $E_{1},\ldots,E_{r}$ are disjoint subsets of ${V\choose 2}$.
Then for any equipartition $\mathcal{P}=\\{V_{1},\ldots,V_{m}\\}$ of $V$,
there is are $m^{\prime}\leq M$ and an equipartition,
$\mathcal{P}^{\prime}=\\{V_{1}^{\prime},\ldots,V_{m^{\prime}}^{\prime}\\}$
which refines $\mathcal{P}$, such that all but at most
$\epsilon(m^{\prime})^{2}$ pairs $(V_{i}^{\prime},V_{j}^{\prime})$,
$(V_{i}^{\prime}\cup V_{j}^{\prime},E_{u})$ satisfies
$\textnormal{disc}_{2}(\epsilon)$ for all $1\leq u\leq r$.

Note that $M=M(\epsilon,m)$ does not depend on the number of colors. In fact,
it is the same bound as in the usual regularity lemma. Indeed, it is
straightforward to prove Theorem B.1 by following the usual proof of the
regularity lemma, with a slightly altered mean square density. The mean square
density increases at each step in an identical way to the usual proof, so the
bound ends up identical. We now give a sketch of this proof, as we could not
find this explicitly in the literature.

We will follow closely the proof of the usual regularity lemma (see, for
example [2]). First, suppose that $r\geq 1$, for each $u\in[r]$, $(V,E_{u})$
is a graph on the vertex set $V$, where $|V|=n$, and $u\neq v$ implies
$E_{u}\cap E_{v}=\emptyset$. Given $X,Y\subseteq V$, define

$d_{u}(X,Y)=\frac{|E_{u}\cap K_{2}[X,Y]|}{|X||Y|}.$

Note that $d_{1}(X,Y)+\ldots+d_{r}(X,Y)\leq 1$. We then define, for each
$u\in[r]$,

$\textnormal{msd}_{u}(X,Y)=\frac{|X||Y|}{n^{2}}d^{2}_{u}(X,Y).$

Here, msd stands for “mean square density.” Note this is just the usual mean
square density for the graph $(V,E_{u})$. We then define

$\textnormal{msd}(X,Y)=\sum_{u=1}^{r}\textnormal{msd}_{u}(X,Y)=\frac{|X||Y|}{n^{2}}\sum_{u=1}^{r}d^{2}_{u}(X,Y).$

Note that since $0\leq d_{1}(X,Y)+\ldots+d_{r}(X,Y)\leq 1$,
$\sum_{u=1}^{r}d_{u}^{2}(X,Y)\leq 1$, so
$\textnormal{msd}(X,Y)\leq\frac{|X||Y|}{n^{2}}$. If $\mathcal{P}_{X}$ and
$\mathcal{P}_{Y}$ are partitions of $X$ and $Y$, define, for each $u\in[r]$,

$\textnormal{msd}_{u}(\mathcal{P}_{X},\mathcal{P}_{Y})=\sum_{U\in\mathcal{P}_{X}}\sum_{W\in\mathcal{P}_{Y}}\textnormal{msd}_{u}(U,W),$

and set

$\textnormal{msd}(\mathcal{P}_{X},\mathcal{P}_{Y})=\sum_{u=1}^{r}\textnormal{msd}_{u}(\mathcal{P}_{X},\mathcal{P}_{Y}).$

For a partition $\mathcal{P}=\\{V_{1},\ldots,V_{k}\\}$ of $V$, let
$\textnormal{msd}_{u}(\mathcal{P})=\textnormal{msd}_{u}(\mathcal{P},\mathcal{P})$
and $\textnormal{msd}(\mathcal{P})=\textnormal{msd}(\mathcal{P},\mathcal{P})$.
Note

$\textnormal{msd}(\mathcal{P})=\sum_{i=1}^{k}\sum_{j=1}^{k}\frac{|V_{i}||V_{j}|}{n^{2}}(\sum_{u=1}^{r}d^{2}_{u}(V_{i},V_{j}))\leq\sum_{i=1}^{k}\sum_{j=1}^{k}\frac{|V_{i}||V_{j}|}{n^{2}}=1$

######  Lemma B.2.

For any partitions $\mathcal{P}_{X}$ of $X$ and $\mathcal{P}_{Y}$ of $Y$,
$\textnormal{msd}(\mathcal{P}_{X},\mathcal{P}_{Y})\geq\textnormal{msd}(X,Y)$.

###### Proof.

It is well known that for each $1\leq u\leq r$,
$\textnormal{msd}_{u}(\mathcal{P}_{X},\mathcal{P}_{Y})\geq\textnormal{msd}_{u}(X,Y)$
(see e.g. [25, Corollary 3.7]). By definition, this implies
$\textnormal{msd}(\mathcal{P}_{X},\mathcal{P}_{Y})\geq\textnormal{msd}(X,Y)$.
∎

######  Lemma B.3.

If $(X\cup Y,E_{u}\cap K_{2}[X,Y])$ does not satisfy
$\textnormal{disc}_{2}(\epsilon)$, then there are $X_{1}\subseteq X$ and
$Y_{1}\subseteq Y$, such that

$\textnormal{msd}(\\{X_{1},X\setminus X_{1}\\},\\{Y_{1},Y\setminus
Y_{1}\\})>\textnormal{msd}(X,Y)+\epsilon^{4}\frac{|X||Y|}{n^{2}}.$

###### Proof.

Suppose $(X\cup Y,E_{u}\cap K_{2}[X,Y])$ fails
$\textnormal{disc}_{2}(\epsilon)$. Then it is easy to check that $(X,Y)$ is
not $\epsilon$-regular, say this is witnessed by $X_{1}\subseteq X$ and
$Y_{1}\subseteq Y$. It is well known this implies that
$\textnormal{msd}_{u}(\\{X_{1},X\setminus X_{1}\\},\\{Y_{1},Y\setminus
Y_{1}\\})>\textnormal{msd}_{u}(X,Y)+\epsilon^{4}\frac{|X||Y|}{n^{2}}$ (see
e.g. [25]). So

$\displaystyle\textnormal{msd}(\\{X_{1},X\setminus
X_{1}\\},\\{Y_{1},Y\setminus
Y_{1}\\})=\sum_{s=1}^{r}\textnormal{msd}_{s}((\\{X_{1},X\setminus
X_{1}\\},\\{Y_{1},Y\setminus Y_{1}\\})$
$\displaystyle>\textnormal{msd}_{u}(X,Y)+\epsilon^{4}\frac{|X||Y|}{n^{2}}+\sum_{s\in[r]\setminus\\{u\\}}\textnormal{msd}_{s}(\\{X_{1},X\setminus
X_{1}\\},\\{Y_{1},Y\setminus Y_{1}\\})$
$\displaystyle\geq\textnormal{msd}_{u}(X,Y)+\epsilon^{4}\frac{|X||Y|}{n^{2}}+\sum_{s\in[r]\setminus\\{u\\}}\textnormal{msd}_{s}(X,Y)$
$\displaystyle=\textnormal{msd}(X,Y)+\epsilon^{4}\frac{|X||Y|}{n^{2}},$

where the last inequality is due to Lemma B.3. ∎

One can now deduce Theorem B.1 exactly as in usual proofs of the regularity
lemma (see e.g. [45], [2]). The second tool used in the proof of Lemma 2.27 is
Lemma B.4 below, which is a corollary of Lemma 2.24.

######  Lemma B.4.

Suppose $\epsilon_{1}>0$, $\ell\geq 1$, and
$0<\epsilon_{2}<\epsilon_{1}/(64\ell^{\prime})$, where
$\ell^{\prime}:=[32\ell^{2}\epsilon_{1}^{-2}]$. There is
$m_{0}=m_{0}(\epsilon_{1},\epsilon_{2},\ell,\delta)$ such that the following
holds. Suppose $|U|=|V|=m\geq m_{0}$, $s\leq\ell$, and
$K_{2}(U,V)=E_{0}\cup\ldots\cup E_{s}$ is a partition such that for each
$i\in[s]$, $(U\cup V,E_{i})$ has $\textnormal{disc}(\epsilon_{2})$, and