2.1 Averaging and symmetry

This section contains two crucial lemmas. The first is a simple averaging lemma for “dense” subsets.

Proof. Suppose towards a contradiction that $|\bigcup _{Y\in \Sigma }Y|\lt (1-b)|X|$ . Then

\begin{equation*} |X\setminus A|\geq \sum _{Y\in \mathcal{P}\setminus \Sigma }|Y\setminus A|\gt \sum _{Y\in \mathcal{P}\setminus \Sigma }a|Y|=a\sum _{Y\in \mathcal{P}\setminus \Sigma }|Y|\geq ab|X|=\epsilon |X|, \end{equation*}

a contradiction.

We will also use the analogue of Lemma 2.1 for very sparse sets. It is obtained immediately by applying Lemma 2.1 to complements.

The second important lemma is a “symmetry lemma” for $3$ -partite $3$ -graphs We begin by stating Lemma 2.4 below, which is a simpler symmetry lemma in the setting of graphs. This will involve an adaptation of the notion of “good sets”, first defined in [Reference Malliaris and Shelah16].

Definition 2.3. Suppose $G=(A\cup B, E)$ is a bipartite graph and $\epsilon \gt 0$ . We say a subset $X\subseteq B$ is almost $\epsilon$ -good with respect to $G$ if for at least $(1-\epsilon )|A|$ many $a\in A$ ,

\begin{equation*} \frac {|N_G(a)\cap X|}{|X|}\in [0,\epsilon )\cup (1-\epsilon, 1]. \end{equation*}

The symmetry lemma for graphs, Lemma 2.4 below, says that if $G=(A\cup B, E)$ is a bipartite graph, and both $A$ and $B$ are almost $\epsilon$ -good with respect to $G$ , then $d_G(A,B)$ is close to $0$ or $1$ . A proof appears in [Reference Terry and Wolf19] (see Lemma 4.9 there).

Our goal is to prove a ternary analogoue of Lemma 2.4. We begin with an analogue of Definition 2.3.

Definition 2.5. Suppose $H=(V_1\cup V_2\cup V_3,E)$ is a $3$ -partite $3$ -graph and $\{i_1,i_2,i_3\}=\{1,2,3\}$ . A set $X\subseteq V_{i_1}$ is almost $\epsilon$ -good with respect to $H$ if at least $(1-\epsilon )|V_{i_2}||V_{i_3}|$ many $(y,z)\in V_{i_2}\times V_{i_3}$ satisfy

\begin{equation*} \frac {|N_H(yz)\cap X|}{|X|}\in [0,\epsilon )\cup (1-\epsilon, 1]. \end{equation*}

We now state and prove our symmetry lemma for $3$ -graphs, which says that a tripartite $3$ -graph in which all three parts are almost $\epsilon$ -good has density close to $0$ or $1$ .

Proof. Given $i,j,k$ satisfying $\{i,j,k\}=\{1,2,3\}$ , define

\begin{equation*} E_{ij}=\{xy\in K_2[V_i,V_j]\, : \,|N_H(xy)|\leq \epsilon |V_k|\text{ or }|N_H(xy)|\geq (1-\epsilon )|V_k|\}. \end{equation*}

Our assumption implies that for each $ij\in {\binom{[3]}{2}}$ , $|E_{ij}|\geq (1-\epsilon )|V_i||V_j|$ . Consider now the bipartite graph $\Gamma$ with vertex set $V_1\cup K_2[V_2,V_3]$ and edge set

\begin{equation*} E(\Gamma )=\{(x, yz)\in V_1\cup K_2[V_2,V_3]\, : \,xyz\in H\}. \end{equation*}

It suffices to show $d_{\Gamma }(V_1,K_2[V_2,V_3])\in [0,4\epsilon ^{1/16})\cup (1-4\epsilon ^{1/16},1]$ . We will show this by applying Lemma 2.4 to $\Gamma$ . To do this, we need to verify the relevant hypotheses.

Since $|E_{23}|\geq (1-\epsilon )|K_2[V_2,V_3]|$ , we already know $V_1$ is almost $\epsilon$ -good with respect to $\Gamma$ . Our next goal is to show $K_2[V_2,V_3]$ is almost $2\epsilon ^{1/4}$ -good with respect to $\Gamma$ . We begin by defining the following subsets of $E_{12}$ .

\begin{align*} E_{12}^1&=\{xy \in K_2[V_1,V_2]\, : \,|N_H(xy)|\geq (1-\epsilon )|V_3| \}\text{ and } \\[3pt] E_{12}^0 &=\{xy \in K_2[V_1,V_2]\, : \,|N_H(xy)|\leq \epsilon |V_3| \}. \end{align*}

Note $E_{12}=E_{12}^1\sqcup E_{12}^0$ . Consider the following subset of $V_1$ (recall notation equation (1)).

\begin{equation*} V_1'=\{x\in V_1\, : \,|N_{E_{12}}(x)|\geq (1-\epsilon ^{1/2})|V_2|\text{ and }|N_{E_{13}}(x)|\geq (1-\epsilon ^{1/2})|V_3|\}. \end{equation*}

Since $|E_{12}|\geq (1-\epsilon )|V_1||V_2|$ and $|E_{13}|\geq (1-\epsilon )|V_1||V_3|$ , we conclude by two applications of Lemma 2.1 that $|V_1'|\geq (1-2\epsilon ^{1/2})|V_1|$ .

Claim 2.7. For each $x\in V_1'$ , either $|N_{E_{12}^1}(x)|\geq (1-\epsilon ^{1/4})|V_2|$ or $|N_{E_{12}^0}(x)|\geq (1-\epsilon ^{1/4})|V_2|$ .

Proof. Suppose towards a contradiction there is some $x\in V_1'$ so that

\begin{equation*} \max \{|N_{E^1_{12}}(x)|,|N_{E^0_{12}}(x)|\}\lt (1-\epsilon ^{1/4})|V_2|. \end{equation*}

Combining this with the fact that $x\in V_1'$ , and since $N_{E_{12}}(x)=N_{E_{12}^0}(x)\cup N_{E_{12}^1}(x)$ by definition, we observe that

\begin{equation*} \min \{|N_{E^1_{12}}(x)|,|N_{E^0_{12}}(x)|\}\geq (\epsilon ^{1/4}-\epsilon ^{1/2})|V_2|. \end{equation*}

To ease notation, set

\begin{align*} V_2^1=N_{E^1_{12}}(x)\text{ and }V_2^0=N_{E^0_{12}}(x). \end{align*}

Then $V_2^1\cup V_2^0\subseteq V_2$ and $\min \{|V_2^1|,|V_2^0|\}\geq (\epsilon ^{1/4}-\epsilon ^{1/2})|V_2|$ . Let $H_x$ be the slice graph of $H$ at $x$ , i.e. the graph with vertex set $V(H)$ and edge set $\{yz\in {\binom{V}{2}}\, : \,xyz\in E(H)\}$ . By definition of $V_2^1$ and $V_2^0$ , the following hold.

(2) \begin{align} |E(H_x)\cap K_2[V_2^1, V_3]|&=\sum _{y\in V_2^1}|N_H(xy)|\geq (1-\epsilon )|V^1_2||V_3|\text{ and }\\[-10pt] \nonumber \end{align}

(3) \begin{align} |K_2[V_2^0, V_3]\setminus E(H_x)|&= \sum _{y\in V_2^0}|V_3\setminus N_H(xy)|\geq (1-\epsilon )|V^0_2||V_3|. \\[8pt] \nonumber \end{align}

Define

\begin{align*} V_3^1&=\{z\in V_3\, : \,|N_H(xz)\cap V_2^1|\geq (1-\epsilon ^{1/2})|V_2^1|\}\text{ and }\\[3pt] V_3^0&=\{z\in V_3\, : \,| V_2^0\setminus N_H(xz)|\geq (1-\epsilon ^{1/2})|V_2^0|\}. \end{align*}

By equations (2) and (3), and Lemma 2.1, we have $|V_3^1|\geq (1-\epsilon ^{1/2})|V_3|$ and $|V_3^0|\geq (1-\epsilon ^{1/2})|V_3|$ . Consequently, using again that $x\in V_1'$ , we have

\begin{equation*} |V_3^1\cap V_3^0\cap N_{E_{13}}(x)|\geq (1-3\epsilon ^{1/2})|V_3|\gt 0, \end{equation*}

where the last inequality is because $\epsilon \lt 1/9$ . From this, we conclude there exists some $z\in V_3^1\cap V_3^0\cap N_{E_{13}}(x)$ . Since $z\in V_3^1$ ,

\begin{equation*} |N_H(xz)|\geq (1-\epsilon ^{1/2})|V_2^1|\geq (1-\epsilon ^{1/2})(\epsilon ^{1/4}-\epsilon ^{1/2})|V_2|\gt \epsilon |V_2|, \end{equation*}

where the last inequality uses that $\epsilon$ is sufficiently small. On the other hand, since $z\in V_3^0$ ,

\begin{equation*} |V_2\setminus N_H(xz)|\geq (1-\epsilon ^{1/2})|V_2^0|\geq (1-\epsilon ^{1/2})(\epsilon ^{1/4}-\epsilon ^{1/2})|V_2|\gt \epsilon |V_2|. \end{equation*}

But this contradicts that $xz\in E_{13}$ . This finishes the proof of Claim 2.7.

By Claim 2.7, we have that for every $x\in V_1'$ , either $|N_{E_{12}^0}(x)|\geq (1-\epsilon ^{1/4})|V_2|$ , or $|N_{E_{12}^1}(x)|\geq (1-\epsilon ^{1/4})|V_2|$ . Given $x\in V_1'$ , if $|N_{E_{12}^1}(x)|\geq (1-\epsilon ^{1/4})|V_2|$ , then

\begin{align*} |N_H(x)\cap K_2[V_2,V_3]|\geq \sum _{y\in N_{E_{12}^1}(x)}|N_H(xy)|\geq |N_{E_{12}^1}(x)|(1-\epsilon )|V_3|&\geq (1-\epsilon ^{1/4})(1-\epsilon )|V_2||V_3|\\[2pt] &\gt (1-2\epsilon ^{1/4})|V_2||V_3|. \end{align*}

On the other hand, if $x\in V_1'$ and $|N_{E_{12}^0}(x)|\geq \epsilon ^{1/4}|V_2|$ , then a similar argument shows

\begin{equation*} |K_2[V_2,V_3]\setminus N_H(x)|\gt (1-2\epsilon ^{1/4})|V_2||V_3|. \end{equation*}

We have shown that $|V_1'|\geq (1-2\epsilon ^{1/2})$ , and for all $x\in V_1'$ , either $|N_{\Gamma }(x)|\gt (1-2\epsilon ^{1/4})|V_2||V_3|$ or $|N_{\Gamma }(x)|\lt 2\epsilon ^{1/4}|V_2||V_3|$ . In other words, $K_2[V_2,V_3]$ is almost $2\epsilon ^{1/4}$ -good in $\Gamma$ . We can thus conclude, by Lemma 2.4, that $d_{\Gamma }(V_1,K_2[V_2,V_3])\in [0,4\epsilon ^{1/16})\cup (1-4\epsilon ^{1/16},1]$ . This finishes the proof.

2.2 VC-dimension and homogeneous partitions of graphs

In this section we discuss VC-dimension and homogeneous partitions for graphs. We begin with the definition of VC-dimension of a graph.

We now define homogeneous partitions for graphs.

As mentioned in the introduction, work of Alon–Fischer–Newman, Lovász–Szegedy, and Fox–Pach–Suk have shown that graphs of small VC-dimension admit homogeneous partitions with efficient bounds (see Theorem1.1 in the introduction). We will require a slightly more complicated version of Theorem1.1, which allows us to find homogeneous equipartitions of bipartite graphs which also refine a distinguished bipartition. The proof follows from Theorem1.1 via standard arguments (which we include in the appendix for completeness).

2.3 Slicewise VC-dimension and homogeneous partitions of $3$ -graphs

We begin with the definition of a “slice graph” associated to a $3$ -graph.

Definition 2.11. Suppose $H$ is a $3$ -graph. For each $x\in V(H)$ , the slice graph of $H$ at $x$ , denoted $H_x$ , is the graph with vertex set $V(H_x)=V(H)$ and edge set

\begin{equation*} E(H_x)=\Big \{yz\in {\binom{V(H)}{2}}\, : \,xyz\in E(H)\Big \}. \end{equation*}

We now define the slicewise VC-dimension of a $3$ -graph to be the maximum VC-dimension of its associated slice graphs.

Definition 2.12. Suppose $H=(V,E)$ is a $3$ -graph. The slicewise VC-dimension of $H$ is

\begin{equation*} \text{SVC}(H)\, :\!= \, \max \{\text{VC}(H_x)\, : \,x\in V\}. \end{equation*}

We now define homogeneous partitions for $3$ -graphs in analogy to Definition 2.9.

It is known that $3$ -graphs of small slicewise VC-dimension admit homogeneous partitions (see Theorem1.3 in the introduction). The goal of this paper is to prove they admit homogeneous partitions with a relatively small number of parts. A crucial tool in this proof will be the notion of an almost $\epsilon$ -good partition, which we now define (recall Definition 2.5 as well).

Definition 2.14. Suppose $H=(V_1\cup V_2\cup V_3,E)$ is a $3$ -partite $3$ -graph and $\{i_1,i_2,i_3\}=\{1,2,3\}$ . A partition $\mathcal{P}$ of $V_{i_1}$ is almost $\epsilon$ -good with respect to $H$ if

\begin{equation*} \bigg |\bigcup _{X\in \mathcal{P}'}X\bigg |\geq (1-\epsilon )|V_{i_1}|^3, \end{equation*}

where $\mathcal{P}'=\{X\in \mathcal{P}\, : \,X\; \text{is}\;\text{almost}\; \epsilon -\text{good}\;\text{with}\;\text{respect}\;\text{to}\;H\}$ .

We now extend Definition 2.14 to partitions of the whole vertex set of a tripartite $3$ -graph.

We now show that an almost $\epsilon$ -good partition of a tripartite $3$ -graph is automatically homogeneous. This relies crucially on our symmetry lemma, Lemma 2.6.

Proof. To ease notation, let $\mathcal{P}_1=\mathcal{P}|_{V_1}$ , $\mathcal{P}_2=\mathcal{P}|_{V_2}$ , and $\mathcal{P}_3=\mathcal{P}|_{V_3}$ . Define

\begin{align*} \Gamma _{1}&=\bigcup _{Y\in \mathcal{P}_1}\Big \{xyz\in K_2[V_1,V_2,V_3]\, : \,\frac {|N_H(yz)\cap Y|}{|Y|}\in [0,\epsilon )\cup (1-\epsilon, 1]\Big \},\\[3pt] \Gamma _{2}&=\bigcup _{Y\in \mathcal{P}_2}\Big \{xyz\in K_2[V_1,V_2,V_3]\, : \,\frac {|N_H(xz)\cap Y|}{|Y|}\in [0,\epsilon )\cup (1-\epsilon, 1]\Big \},\text{ and }\\[3pt] \Gamma _{3}&=\bigcup _{Y\in \mathcal{P}_3}\Big \{xyz\in K_2[V_1,V_2,V_3]\, : \,\frac {|N_H(xy)\cap Y|}{|Y|}\in [0,\epsilon )\cup (1-\epsilon, 1]\Big \}. \end{align*}

By assumption, each of $\Gamma _1$ , $\Gamma _2$ , and $\Gamma _3$ have size at least $(1-\epsilon )|V_1||V_2||V_3|$ . Thus if we set

\begin{equation*} \Gamma \, :\!= \, \Gamma _1\cap \Gamma _2\cap \Gamma _3, \end{equation*}

then $|\Gamma |\geq (1-3\epsilon )|V_1||V_2||V_3|$ . Let

\begin{equation*} \Sigma =\{(X,Y,Z)\in \mathcal{P}_1\times \mathcal{P}_2\times \mathcal{P}_3\, : \,|K_3[X,Y,Z]\cap \Gamma |\geq (1-\sqrt {3\epsilon })|X||Y||Z|\}. \end{equation*}

By the lower bound above for $|\Gamma |$ and Lemma 2.1,

\begin{equation*} \bigg |\bigcup _{(X,Y,Z)\in \Sigma }K_3[X,Y,Z]\bigg |\geq (1-\sqrt {3\epsilon })|V_1||V_2||V_3|. \end{equation*}

Thus it suffices to show that each $(X,Y,Z)\in \Sigma$ is $5\epsilon ^{1/64}$ -homogeneous with respect to $H$ . To this end, fix a triple $(X,Y,Z)\in \Sigma$ . Let

\begin{equation*} E_{XY}=\{xy\in K_2[X,Y]\, : \,|N_{\Gamma }(xy)\cap Z|\geq (1-(3\epsilon )^{1/4})|Z|\}. \end{equation*}

Since $(X,Y,Z)\in \Sigma$ , Lemma 2.1 implies $|E_{XY}|\geq (1-(3\epsilon )^{1/4})|X||Y|$ . For all $xy\in E_{XY}$ , since $N_{\Gamma }(xy)\cap Z\neq \emptyset$ , we have by definition of $\Gamma$ that $|N_H(xy)\cap Z|/|Z|\in [0,\epsilon )\cup (1-\epsilon, 1]$ . Combining with the lower bound on $E_{XY}$ , we have shown that $Z$ is almost $(3\epsilon )^{1/4}$ -good with respect to $H[X,Y,Z]$ . A symmetric argument shows both $X$ and $Y$ are also almost $(3\epsilon )^{1/4}$ -good with respect to $H[X,Y,Z]$ . By Lemma 2.6, and since $4((3\epsilon )^{1/4})^{1/16}\leq 5 \epsilon ^{1/64}$ , we have that $(X,Y,Z)$ is $5\epsilon ^{1/64}$ -homogeneous with respect to $H$ , as desired.

2.4 Tripartite decompositions

In this section we define tripartite decompositions. These will play an important role in the proof of Theorem4.1. They are essentially tripartite versions of more general decompositions typically used in a strong form of regularity for $3$ -graphs. Our notation is largely adapted from [Reference Frankl and Rödl10].

We begin by introducing the notion of a triad, which for us will be simply any tripartite graph.

Given a triad $G=(X\cup Y\cup Z, E)$ , we let $K_3^{(2)}(G)$ denote the set of triangles from $G$ , i.e. we define

\begin{align*} K_3^{(2)}(G)=\{xyz\in K_3[X,Y,Z]\, : \,xy, yz, xz\in E\}. \end{align*}

The notion of density of a triad, relative to a $3$ -graph, is crucial for our proofs.

Definition 2.18. Suppose $H$ is a $3$ -graph, $X,Y,Z$ are disjoint subsets of $V(H)$ , and $G=(X\cup Y\cup Z, E)$ is a triad. Define

\begin{align*} d_H(G)\, :\!= \, \frac {|E(H)\cap K_3^{(2)}(G)|}{| K_3^{(2)}(G)|}. \\[-10pt] \end{align*}

We now define homogeneous triads relative to a $3$ -graph.

Definition 2.19. Suppose $H$ is a $3$ -graph, $X,Y,Z$ are disjoint subsets of $V(H)$ , and $G=(X\cup Y\cup Z, E)$ is a triad. We say $G$ is $\epsilon$ -homogeneous with respect to $H$ if

\begin{equation*} d_H(G)\in [0,\epsilon )\cup (1-\epsilon, 1]. \end{equation*}

We now define the notion of a tripartite decomposition.

In Definition 2.20, we will sometimes call $\mathcal{P}$ simply a tripartite decomposition of $V$ when the relevant partition $A\sqcup B\sqcup C$ is clear from context. Tripartite decompositions come equipped with an associated collection of triads, which we now define.

Using the notation of Definition 2.21, we see that a tripartite decomposition $\mathcal{P}$ induces a partition

\begin{equation*} K_3[A,B,C]=\bigcup _{G\in \text{Tri}(\mathcal{P})}K_3^{(2)}(G). \end{equation*}

We now define homogeneous tripartite decompositions.

Definition 2.22. Suppose $V=A\sqcup B\sqcup C$ , $H=(A\cup B\cup C, E)$ is a tripartite $3$ -graph, and $\mathcal{P}$ is a tripartite $(A,B,C)$ -decomposition of $V$ . We say $\mathcal{P}$ is $\epsilon$ -homogeneous with respect to $H$ if

\begin{equation*} \sum _{G\in \Sigma }|K_3^{(2)}(G)|\geq (1-\epsilon )|A||B||C|, \end{equation*}

where $\Sigma =\{G\in\;\text{Tri}(\mathcal{P})\, : \,G\; \text{is}\;\epsilon -\text{homogeneous with respect to}\;H\}$ .

We note that there are major differences between a homogeneous tripartite decomposition in the sense of Definition 2.22 and a homogeneous partition in the sense of Definition 2.13. In particular, Definition 2.13 deals only with triples of sets from a vertex partition, while Definition 2.22 deals with tripartite graphs built from partitions of both vertices and pairs of vertices.

4.1 Accomplishing step 3

In this section, we prove the main ingredient, Proposition 4.2, which is required to execute Step 3 of the strategy outlined above. The goal of Proposition 4.2 is to give a structure theorem for any tripartite $3$ -graph $H=(U\cup V\cup W,F)$ with slicewise VC-dimension less than $k$ , under the assumption that there exists a single bipartite edge-coloured graph $\mathcal{G}$ so that for all $x\in U$ , $\mathcal{G}$ arises as the reduced graph associated to a homogeneous partition of $H_x$ .

Proposition 4.2. For all $k\geq 1$ , there exist constants $C=C(k)\geq 1$ , $D=D(k)\geq 1$ , and $\epsilon ^*=\epsilon ^*(k)\gt 0$ so that the following holds. Fix $0\lt \epsilon \lt \epsilon ^*$ and let $r,s,\ell$ be positive integers with $s\leq \ell$ and $r\leq \ell$ , and assume the following hold.

1. (1) $H=(U\cup V\cup W,E)$ is a sufficiently large tripartite $3$ -graph satisfying $\text{SVC}(H)\lt k$ and $|U|=|V|=|W|$ ,

2. (2) $\mathcal{G}=(P\cup Q, F_0,F_1,F_2)$ is a bipartite edge-coloured graph with $P=\{p_0,\ldots, p_r\}$ and $Q=\{q_0,\ldots, q_s\}$ ,

3. (3) For all $x\in U$ , there is a partition $V=B_x^0\cup \cdots \cup B_x^r$ and $W=C_x^0\cup \cdots \cup C_x^s$ so that the following hold, where $E(H)^1\, :\!= \, E(H)$ and $E(H)^0\, :\!= \, {\binom{V(H)}{3}}\setminus E(H)$ .

   1. (a) For each $\alpha \in \{0,1\}$ and $p_iq_j\in F_{\alpha }$ , $|E(H_x)^{\alpha }\cap K_2[B_x^i,C_x^j]|\geq (1-\epsilon )|B_x^i||C_x^j|$ ,

   2. (b) For each $1\leq i\leq r$ , $||B_x^i|-\frac {|V|}{\ell }|\leq 1$ and for all $1\leq j\leq s$ , $||C_x^j|-\frac {|W|}{\ell }|\leq 1$ ,

   3. (c) $|B_x^0|\leq \epsilon |V|$ and $|C_x^0|\leq \epsilon |W|$ .

4. (4) For all $1\leq i\leq r$ and $1\leq j\leq s$ , $|N_{F_2}(p_i)|\leq \epsilon \ell$ and $|N_{F_2}(q_j)|\leq \epsilon \ell$ .

Then there exists a partition $\mathcal{P}_V$ of $V$ which is almost $C\epsilon ^{1/D}$ -good with respect to $H$ satisfying

\begin{equation*} |\mathcal{P}_V|\leq \epsilon ^{-O_k(\ell ^{\ell +1}\epsilon ^{-\ell })}. \end{equation*}

It is important to note that hypotheses (3b) and (3c) imply $r$ and $s$ are both close to $\ell$ . Consequently, one can check hypotheses (3) and (4) (along with the assumptions that $|V|=|W|$ are sufficiently large and $\epsilon$ is sufficiently small) imply that for each $x\in U$ , the partition $\{B_x^0\cup \cdots \cup B_x^r,C_x^0\cup \cdots \cup C_x^s\}$ is a $2\epsilon$ -homogeneous partition for the slice graph $H_x$ . Before proving Proposition 4.2, we require two lemmas. The first, Lemma 4.3 below, tells us that if $G=(A\cup B,E)$ is a bipartite graph, then we can cover most of $A$ with sets which are either contained the neighbourhood of some element in $G$ , or incident to few edges in $G$ .

The proof of Lemma 4.3 a simple greedy algorithm, and appears in the appendix. The second lemma, Lemma 4.4, is about refinements of almost $\epsilon$ -good partitions. It is essentially a corollary of Lemma 2.1.

Proof. Let $\mathcal{P}_{\textrm {good}}$ be the set of almost $\epsilon$ -good sets in $\mathcal{P}$ . Since, by assumption, $\mathcal{P}$ is almost $\epsilon$ -good with respect to $H$ , we have $|\bigcup _{X\in \mathcal{P}_{\textrm {good}}}X|\geq (1-\epsilon )|V_{i_1}|$ . For each $X\in \mathcal{P}_{\textrm {good}}$ , let

\begin{align*} \Gamma _1(X)&=\{yz\in K_3[V_{i_2},V_{i_3}]\, : \,|N_H(yz)\cap X|\geq (1-\epsilon )|X|\}\text{ and }\\[3pt] \Gamma _0(X)&=\{yz\in K_3[V_{i_2},V_{i_3}]\, : \,|N_H(yz)\cap X|\leq \epsilon |X|\}. \end{align*}

and then set

\begin{equation*} \Omega (X)=\bigg (\bigcup _{yz\in \Gamma _1(X)}K_3[\{y\},\{z\},N_H(yz)\cap X]\bigg )\cup \bigg (\bigcup _{yz\in \Gamma _0(X)}K_3[\{y\},\{z\},X\setminus N_H(yz)]\bigg ). \end{equation*}

Note that for all $X\in \mathcal{P}_{\textrm {good}}$ , $|\Omega (X)|\geq (1-\epsilon )|X||V_{i_2}||V_{i_3}|$ . Consequently, if we let

\begin{equation*} \Omega =\bigcup _{X\in \mathcal{P}_{\textrm {good}}}\Omega (X), \end{equation*}

then $|\Omega |\geq (1-\epsilon )|V_{i_1}||V_{i_2}||V_{i_3}|$ . Define

\begin{equation*} \mathcal{S}=\{S\in \mathcal{Q}\, : \,|\Omega \cap K_3[S,V_{i_2},V_{i_3}]|\geq (1-\epsilon ^{1/2})|S||V_{i_2}||V_{i_3}|\}. \end{equation*}

By Lemma 2.1, $|\bigcup _{S\in \mathcal{S}}S|\geq (1-\epsilon ^{1/2})|V_{i_1}|$ . We show every $S\in \mathcal{S}$ is almost $\epsilon ^{1/4}$ -good with respect to $H$ , which will finish the proof. To this end, fix $S\in \mathcal{S}$ . By Lemma 2.1, if we define

\begin{equation*} \mathcal{G}(S)\, :\!= \, \{(y,z)\in V_{i_2}\times V_{i_3}\, : \,|N_{\Omega }(yz)\cap S|\geq (1-\epsilon ^{1/4})|S|\}, \end{equation*}

then $|\mathcal{G}(S)|\geq (1-\epsilon ^{1/4})|S|$ . By definition of $\Omega$ , and since $S\subseteq X$ for some $X\in \mathcal{P}_{\textrm {good}}$ , we know that for all $(y,z)\in \mathcal{G}(S)$ , $N_{\Omega }(yz)\cap S\subseteq N_H(yz)\cap S$ or $N_{\Omega }(yz)\cap S\subseteq S\setminus N_H(yz)$ . Thus, for every $(y,z)\in \mathcal{G}(S)$ , we either have $|N_H(yz)\cap S|\geq (1-\epsilon ^{1/4})|S|$ or $|S\setminus N_H(yz)|\geq (1-\epsilon ^{1/4})|S|$ . This finishes the proof.

We now prove Proposition 4.2.

Proof of Proposition 4.2. Fix $k\geq 1$ . Let $\delta _0$ , $C_1=C_1(k)$ and $C_2=C_2(k)$ be as in Proposition 3.5. Let $C,D\geq 1$ be the constants such that for all $x\in (0,1)$ ,

(4) \begin{align} Cx^{1/D}=5\cdot 6^{1/256}\cdot (2C^{-1}_1 \cdot (4x^{1/16})^{1/(4k+4)})^{1/16384}. \end{align}

Let $\epsilon ^*\gt 0$ be sufficiently small compared to $C_1^k$ , $C_2^{-k}$ , and $\delta _0^D$ (note these constants all depend only on $k$ ). Fix $0\lt \epsilon \lt \epsilon ^*$ and $1\leq s,r\leq \ell$ .

Assume $H=(U\cup V\cup W,E)$ is a sufficiently large tripartite $3$ -graph and $\mathcal{G}=(P\cup Q, F_0,F_1,F_2)$ is an edge-coloured bipartite graph so that $H$ and $\mathcal{G}$ satisfy the hypotheses (1)–(4) of Proposition 4.2. Throughout, the edge-coloured bipartite graph serves a similar role as a “reduced graph” or “quotient graph” would in traditional applications of the regularity lemma. To emphasize this, we will refer to it as the auxiliary structure, $\mathcal{G}$ . Observe that hypotheses (3b) and (3c), along with the assumption that $|V|=|W|$ is sufficiently large compared to $\ell$ , imply

(5) \begin{align} \min \{r,s\}\geq (1-2\epsilon )\ell . \end{align}

We start by defining partitions of $K_2[U,V]$ and $K_2[U,W]$ using the sets appearing in hypothesis (3). In particular, for each $0\leq u\leq r$ , $0\leq v\leq s$ , let

\begin{align*} P_u=\{xy\in K_2[U,V]\, : \,y\in B^u_x\}\text{ and }Q_v=\{xy\in K_2[U,W]\, : \,y\in C^v_x\}. \end{align*}

Note that $K_2[U,V]=P_0\cup \cdots \cup P_r$ and $K_2[U,W]=Q_0\cup \cdots \cup Q_s$ . By hypothesis (3c), we have that for all $x\in U$ ,

\begin{equation*} |N_{P_0}(x)|\leq \epsilon |V|\text{ and }|N_{Q_0}(x)|\leq \epsilon |W|, \end{equation*}

and consequently,

(6) \begin{align} |P_0|\leq \epsilon |U||V|\text{ and }|Q_0|\leq \epsilon |U||W|. \end{align}

We will refer to the sets of the form $P_u$ , $Q_v$ as edge colours, and we will think of $P_0$ and $Q_0$ as the “error colours.” Using these edge colours, we now define a tripartite $(U,V,W)$ -decomposition $\mathcal{D}=(\mathcal{D}_1,\mathcal{D}_2)$ of $V(H)$ . Let $\mathcal{D}_1=(\mathcal{D}_U,\mathcal{D}_V,\mathcal{D}_W)$ , where $\mathcal{D}_U=\{U\}$ , $\mathcal{D}_W=\{W\}$ , $\mathcal{D}_V=\{V\}$ . Then let $\mathcal{D}_2=\{\mathcal{D}_{VW},\mathcal{D}_{UV},\mathcal{D}_{UW}\}$ , where

\begin{equation*} \mathcal{D}_{VW}=\{K_2[V,W]\},\text{ }\mathcal{D}_{UV}=\{P_u:0\leq u\leq r\},\text{ and }\mathcal{D}_{UW}=\{Q_v:0\leq v\leq s\}. \end{equation*}

A triad from $\mathcal{D}$ is then a $3$ -partite graph of the following form, where $0\leq u\leq r$ and $0\leq v\leq s$ .

\begin{equation*} T_{uv}=(U\cup V\cup W, P_u\cup Q_v\cup K_2[V,W]). \end{equation*}

We now show that certain triads from $\mathcal{D}$ are homogeneous with respect to $H$ in the sense of Definition 2.22.

Given $0\leq u\leq r$ and $0\leq v\leq s$ , let $t(u,v)\in \{0,1,2\}$ be such that, in the auxiliary structure $\mathcal{G}$ , $p_uq_v\in F_{t(u,v)}$ . For $1\leq u\leq r$ and $1\leq v\leq s$ , we have by hypothesis (3b) that

\begin{equation*} |U|\Big (\frac {|V|}{\ell }-1\Big )\Big (\frac {|W|}{\ell }-1\Big )\leq |K_3^{(2)}(T_{uv})|=\sum _{x\in U}|N_{P_u}(x)||N_{Q_v}(x)|\leq |U|\Big (\frac {|V|}{\ell }+1\Big )\Big (\frac {|W|}{\ell }+1\Big ). \end{equation*}

For any $0\leq u\leq r$ and $0\leq v\leq s$ , if $t(u,v)\in \{0,1\}$ , we have by hypothesis (3a),

\begin{equation*} |d_H(T_{uv})-t(u,v)|=\Big |\frac {|E(H)\cap K_3^{(2)}(T_{uv})|}{|K_3^{(2)}(T_{uv})|}-t(u,v)\Big |\leq \epsilon . \end{equation*}

Using the notation $E(H)^1=E(H)$ and $E(H)^0=K_3[U,V,W]\setminus E(H)$ , we can restate the above inequality as follows.

(7) \begin{align} |E(H)^{t(u,v)}\cap K_3^{(2)}(T_{uv})|\geq (1-\epsilon )|K_3^{(2)}(T_{uv})|. \end{align}

We now define a crucial object for the rest of the proof. Let $\Gamma$ be the $3$ -partite $3$ -graph with vertex set $U\cup V\cup W$ and edge set

\begin{equation*} E(\Gamma )\, :\!= \, \bigcup _{p_uq_v\in F_0\cup F_1}\Big (K^{(2)}_3(T_{uv})\cap E(H)^{t(u,v)}\Big ). \end{equation*}

Roughly speaking, $E(\Gamma )$ is the set of triples from $K_3[U,V,W]$ which are in a homogeneous triad from $\mathcal{D}$ , and which are moreover “correct” for their triad. Note that for any $xyz\in E(\Gamma )$ , we can decide whether or not $xyz$ is an edge in $H$ by looking at which triad $T_{uv}$ contains $xyz$ and then whether we have $p_uq_v\in F_0$ or $p_uq_v\in F_1$ in $\mathcal{G}$ .

Our next goal is to prove a consequence of the assumption that $\text{SVC}(H)\lt k$ . To state this, we must define some auxiliary edge colours, which are obtained by grouping together the existing edge colours between $U$ and $V$ , based on properties of $\mathcal{G}$ . Given $1\leq v\leq s$ , define

(8) \begin{align} P_{v}^1=\bigcup _{p_u\in N_{F_1}(q_v)}P_u,\text{ }P_{v}^0=\bigcup _{p_u\in N_{F_0}(q_v)}P_u,\text{ and }P_{v}^2=K_2[U,V]\setminus (P_{v}^1\cup P_{v}^0), \end{align}

where we note that the sets $N_{F_1}(q_v)$ and $N_{F_0}(q_v)$ are computed in auxiliary structure $\mathcal{G}$ . This yields a new bipartite edge-coloured graph for each $v\in [r]$ , namely

\begin{equation*} G_{v}\, :\!= \, (U\cup V, P_{v}^0, P_{v}^1, P_{v}^2). \end{equation*}

We now show there are restrictions on copies of $U(k)$ appearing in such a $G_v$ (see Definition 3.3).

The goal of the rest of the proof to create situations where we can use Observation 4.5. We give an informal (and slightly inaccurate) outline of the steps we will take. The reader may choose to skip the outline, and merely refer back to it for reference.

1. (I) Throw away edges and vertices which do not behave well with respect to $\Gamma$ . This is necessary for part (b) in Observations 4.5.

2. (II) Build a partition $\mathcal{X}$ of $U$ so that for all $A\in \mathcal{X}$ , and any $1\leq v\leq s$ , there exists some $c\in W$ so that $A\subseteq N_{Q_v}(c)$ . This will allow us to satisfy part (a) of Observation 4.5 when we restrict ourselves to $H[A\cup V\cup W]$ for each $A\in \mathcal{X}$ .

3. (III) For each $A\in \mathcal{X}$ and most $v\in [s]$ , use Observation 4.5 to define a bipartite edge-coloured graph $(A\cup V,\mathbf{P}_{v,A}^0\cup \mathbf{P}_{v,A}^1\cup \mathbf{P}_{v,A}^2)$ so that $ \mathbf{P}_{v,A}^2$ is small, so that there is no $\mathbf{P}_{v,A}^0/\mathbf{P}_{v,A}^1$ -copy of $U(k)$ , and so that the triads of the form

   \begin{align*} (A\cup V\cup W, Q_v\cup \mathbf{P}_{v,A}^{0}\cup K_2[V,W])\text{ and }(A\cup V\cup W, Q_v\cup \mathbf{P}_{v,A}^{1}\cup K_2[V,W]) \end{align*}
   are homogeneous with respect to $H$ in the sense of Definition 2.22.

4. (IV) For each $A\in \mathcal{X}$ and $v\in [s]$ as in the previous step, apply Proposition 3.5 to $(A\cup V, \mathbf{P}_{v,A}^0, \mathbf{P}_{v,A}^1, \mathbf{P}_{v,A}^2)$ to obtain vertex partitions $\mathcal{P}^A_{v,A}$ of $A$ and $\mathcal{P}_{v,A}^V$ of $V$ so that $(\mathcal{P}_{v,A}^A,\mathcal{P}_{v,A}^V)$ is homogeneous with respect to $\{\mathbf{P}_{v,A}^0, \mathbf{P}_{v,A}^1\}$ in the sense of Definition 3.4.

5. (V) For each $A\in \mathcal{X}$ , define a tripartite decompositions $\mathcal{D}^A$ of $A\cup V\cup W$ as follows. Let $\mathcal{D}_W^A=\{W\}$ be the trivial partition, and let $\mathcal{D}^A_A$ and $\mathcal{D}_V^A$ be the partitions of $A$ and $V$ respectively, generated by taking the coarsest common refinements of the partitions of the form $\mathcal{P}_{v,A}^A$ and $\mathcal{P}_{v,A}^V$ from the preceding step, as $v$ ranges over most elements of $[s]$ . For each $X\in \mathcal{D}_A^A$ , this decomposition will include partitions of $K_2[X,W]$ roughly equal to $\{Q_v\cap K_2[X,W]\, : \,1\leq v\leq s\}$ . All other elements in $\mathcal{D}^A_2$ are trivial partitions. Show each $\mathcal{D}^A$ is homogenous with respect to $H[A,V,W]$ in the sense of Definition 2.22.

6. (VI) Show each partition $\mathcal{D}_V^A$ of $V$ from the previous step is almost good with respect to $H[A,V,W]$ in the sense of Definition 2.5.

7. (VII) Take the coarsest common refinement of the partitions $\mathcal{D}_V^A$ of $V$ , as $A$ ranges over the elements in $\mathcal{X}$ . Conclude the result is a partition of $V$ which is almost good with respect to $H$ using Lemma 4.4.

Step I. In this step, we restrict our vertex set and adjust the edge colours to ensure good behaviour with respect to $\Gamma$ . We first observe that by definition of $\Gamma$ and equation (7),

(9) \begin{align} |E(\Gamma )\cap K_3[U,V,W]|&= \sum _{p_uq_v\in F_0\cup F_1}| K_3^{(2)}(T_{uv})\cap E(H)^{t(u,v)}|\nonumber \\[3pt] &\geq (1-\epsilon )\sum _{p_uq_v\in F_0\cup F_1}|K_3^{(2)}(T_{uv})|\nonumber \\[3pt] &=(1-\epsilon )(|U||V||W|-\sum _{p_uq_v\in F_2}|K_3^{(2)}(T_{uv})|). \end{align}

Note that by inequality equation (6) and hypotheses (3b) and (4), we have that

\begin{align*} \sum _{p_uq_v\in F_2}|K_3^{(2)}(T_{uv})|&\leq |P_0||W|+|Q_0||V|+\sum _{x\in U}\sum _{u=1}^r\sum _{q_v\in N_{F_2}(p_u)}|N_{P_u}(x)||N_{Q_v}(x)|\\[3pt] &\leq 2\epsilon |U||V||W|+r\epsilon \ell |U| \Big (\frac {|V|}{\ell }+1\Big )\Big (\frac {|W|}{\ell }+1\Big )\\[3pt] &\leq 6\epsilon |U||V|||W|, \end{align*}

where the last inequality uses that $r\leq \ell$ and $|W|$ and $|V|$ are large. Combining with equation (9) yields

(10) \begin{align} |E(\Gamma )\cap K_3[U,V,W]|\geq (1-\epsilon )(1-6\epsilon )|U||V||W|\geq (1-7\epsilon )|U||V||W|. \end{align}

Crucially, this means $\Gamma$ covers almost all triples from $K_3[U,V,W]$ . We will restrict our attention to vertices which are sufficiently well behaved with respect to $\Gamma$ . First, we set

\begin{align*} V_{\textrm {good}}&=\{b\in V\;:\;|N_{\Gamma }(b)|\geq (1-\epsilon ^{1/2})|U||W|\},\text{ and }\\[3pt] W_{\textrm {good}}&=\{c\in W\, : \,|N_{\Gamma }(c)|\geq (1-\epsilon ^{1/2})|U||V|\}. \end{align*}

Inequality equation (10) along with Lemma 2.1 implies

(11) \begin{align} |V_{\textrm {good}}|\geq (1-7\epsilon ^{1/2})|V|\text{ and }|W_{\textrm {good}}|\geq (1-7\epsilon ^{1/2})|W|. \end{align}

We now define $G^{\textrm {good}}$ to be the tripartite graph with vertex set $U\cup V_{\textrm {good}}\cup W_{\textrm {good}}$ , and edge set

\begin{align*} E(G^{\textrm {good}})= &\{xy\in K_2[U,V_{\textrm {good}}]\, : \,|N_{\Gamma }(xy)|\geq (1-\epsilon ^{1/4})|W_{\textrm {good}}|\} \\[3pt] &\cup \{xz\in K_2[U,W_{\textrm {good}}]\, : \,|N_{\Gamma }(xz)|\geq (1-\epsilon ^{1/4})|V_{\textrm {good}}|\}. \end{align*}

Using the definition of $V_{\textrm {good}}$ and equation (11), we have

\begin{align*} |E(\Gamma )\cap K_3[U,V_{\textrm {good}},W_{\textrm {good}}]|&\geq \sum _{v\in V_{\textrm {good}}}|N_{\Gamma }(v)\cap K_2[U,W_{\textrm {good}}]|\\[3pt] &\geq \sum _{v\in V_{\textrm {good}}}|N_{\Gamma }(v)|-\sum _{v\in V_{\textrm {good}}} |K_2[U,W\setminus W_{\textrm {good}}]|\\[3pt] &\geq |V_{\textrm {good}}|(1-\sqrt {\epsilon })|U||W|-|V_{\textrm {good}}||U||W\setminus W_{\textrm {good}}|\\[3pt] &\geq |V_{\textrm {good}}|(1-\sqrt {\epsilon })|U||W|-7\epsilon ^{1/2}|V_{\textrm {good}}||U||W|\\[3pt] &=(1-8\sqrt {\epsilon })|V_{\textrm {good}}||U||W|\\[3pt] &\geq (1-8\sqrt {\epsilon })|V_{\textrm {good}}||U||W_{\textrm {good}}|. \end{align*}

Combining this with the definition of $E(G^{\textrm {good}})$ and Lemma 2.1 yields

(12) \begin{align} |E(G^{\textrm {good}})\cap K_2[U,V_{\textrm {good}}]|&\geq (1-8\epsilon ^{1/4})|U||V|. \end{align}

A symmetric argument shows

(13) \begin{align} |E(G^{\textrm {good}})\cap K_2[U,W_{\textrm {good}}]|&\geq (1-8\epsilon ^{1/4})|U||W|. \end{align}

We now collect the remaining the pairs outside $E(G^{\textrm {good}})$ and add them to $P_0,Q_0$ to make slightly larger “error colours.” In particular, let

\begin{align*} P^{\textrm {bad}}=P_0\cup \Big (K_2[U,V]\setminus E(G^{\textrm {good}})\Big )\text{ and }Q^{\textrm {bad}}=Q_0\cup \Big (K_2[U,W]\setminus E(G^{\textrm {good}})\Big ). \end{align*}

By inequalities equations (6), (12), and (13),

(14) \begin{align} |P^{\textrm {bad}}|\leq 9\epsilon ^{1/4}|U||V|\text{ and }|Q^{\textrm {bad}}|\leq 9\epsilon ^{1/4}|U||W|. \end{align}

We now restrict ourselves to vertices in $U$ which mostly avoid $Q^{\textrm {bad}}$ and $P^{\textrm {bad}}$ . Let

(15) \begin{align} U_{\textrm {good}}=\{x\in U\, : \,|N_{Q^{\textrm {bad}}}(x)|\leq \epsilon ^{1/8}|W_{\textrm {good}}|\text{ and }|N_{P^{\textrm {bad}}}(x)|\leq \epsilon ^{1/8}|V_{\textrm {good}}|\}. \end{align}

By inequality equation (14) and Lemma 2.1, $|U_{\textrm {good}}|\geq (1-9\epsilon ^{1/8})|U|$ . Finally, we will restrict the edge colours between $U$ and $W$ to the “good” pairs. Specifically, for each $1\leq v\leq s$ , let

\begin{align*} Q_v^{\textrm {good}}&=Q_v \cap E(G^{\textrm {good}}). \end{align*}

Note that by construction, $K_2[U,W]=Q^{\textrm {bad}}\cup Q_1^{\textrm {good}}\cup \cdots \cup Q_s^{\textrm {good}}$ . This finishes Step I.

Step II. Our next goal is to partition most of $U_{\textrm {good}}$ into pieces that are covered by neighbourhoods of the form $Q^{\textrm {good}}_v(c)$ for some $c\in W_{\textrm {good}}$ . We will do this for each edge colour $Q_v^{good}$ individually and then intersect the resulting partitions. We begin by defining

(16) \begin{align} \delta =\frac {\epsilon }{(2\ell )^8}. \end{align}

Now, for each $1\leq v\leq s$ , apply Lemma 4.3, to $(U_{\textrm {good}}\cup W_{\textrm {good}},Q_v^{\textrm {good}})$ to obtain an integer $0\leq t_{v}\leq \delta ^{-1/2}$ and a partition $\mathcal{X}_{Q_v}=\{X_v(\textrm {err}), X_{v}(0),\ldots, X_{v}(t_{v})\}$ of $U_{\textrm {good}}$ so that the following hold.

1. (i) $|X_v(\textrm {err})|\leq \delta ^{1/8}|U_{\textrm {good}}|$ ,

2. (ii) For each $1\leq j\leq t_v$ , there is some $c_{v,j}\in W_{\textrm {good}}$ so that $X_v(j)\subseteq N_{Q^{\textrm {good}}_v}(c_{v,j})$ and $|X_v(j)|=\lceil \delta ^{1/2}|U_{\textrm {good}}|\rceil$ ,

3. (iii) For all $x\in X_v(0)$ , $|N_{Q^{\textrm {good}}_v}(x)\cap W_{\textrm {good}}|\leq \delta ^{1/8}|W_{\textrm {good}}|$ .

Let $\mathcal{X}$ be the partition of $U_{\textrm {good}}$ obtained by taking the coarsest common refinement the partitions of the form $\mathcal{X}_{Q_v}$ for $v\in [s]$ . Note

(17) \begin{align} |\mathcal{X}|\leq (\delta ^{-1/2}+2)^{s}\leq (\delta ^{-1})^s\leq \delta ^{-\ell }\leq (2\ell )^{\ell }\epsilon ^{-\ell }, \end{align}

where the second inequality is because $\delta \lt \epsilon$ and $\epsilon$ is sufficiently small, the third is because $s\leq \ell$ , and the last is by definition of $\delta$ . We now collect certain elements from $\mathcal{X}$ which we need to throw away. First, set

\begin{align*} \mathcal{X}_{\textrm {err}}=\{A\in \mathcal{X}\, : \,|A|\leq \epsilon |U_{\textrm {good}}|/|\mathcal{X}|\}&\cup \{A\in \mathcal{X}\, : \,\text{ for some }v\in [s], A\subseteq X_v(\textrm {err})\}. \end{align*}

Now let

(18) \begin{align} U_{\textrm {err}}=\Big (U\setminus U_{\textrm {good}}\Big )\cup \Big (\bigcup _{A\in \mathcal{X}_{\textrm {err}}}A\Big )\text{ and }U_{\textrm {good}}'=U\setminus U_{\textrm {err}}. \end{align}

Since $|U_{\textrm {good}}|\geq (1-9\epsilon ^{1/8})|U|$ , and by definition of $\mathcal{X}_{\textrm {err}}$ , we have the following upper bound on $|U_{\textrm {err}}|$ .

(19) \begin{align} |U_{\textrm {err}}|\leq 9\epsilon ^{1/8}|U|+\epsilon |U|+\sum _{v\in [s]}|X_v(\textrm {err})|\leq 9\epsilon ^{1/8}|U|+\epsilon |U|+\ell \delta ^{1/8}|U|\leq 10\epsilon ^{1/8} |U|, \end{align}

where the last inequality is by definition of $\delta$ (see equation (16)) and because $\epsilon$ is sufficiently small. This finishes Step II.

Step III. We now prove a structure theorem for $H[A,V,W]$ for each $A\in \mathcal{X}\setminus \mathcal{X}_{\textrm {err}}$ . We do this in Claim 4.6 below. Roughly speaking, Claim 4.6 says we can group together edge colours to make several homogeneous decompositions for $H[A,V,W]$ , one for most elements of $[s]$ .

Proof. Fix $A\in \mathcal{X}\setminus \mathcal{X}_{\textrm {err}}$ . We begin by defining the distinguished sets of edge colours $\mathcal{S}^A$ for $A$ . In particular, define

\begin{align*} &\mathcal{S}^A=\{v\in [s]\, : \,A\cap X_{v}(0)=\emptyset \}\text{ and }\mathcal{S}^A_{\textrm {err}}=\{v\in [s]\, : \,A\subseteq X_{v}(0)\}. \end{align*}

Since $A\notin \mathcal{X}_{\textrm {err}}$ , we have $\mathcal{S}^A\cup \mathcal{S}^A_{\textrm {err}}=[s]$ . For each $v\in \mathcal{S}^A$ , define

\begin{equation*} \mathbf{Q}^A_v= Q_v^{\textrm {good}}\cap K_2[A,W], \end{equation*}

and then let $\mathbf{Q}_0^A=K_2[A, W]\setminus (\bigcup _{v\in [s]}\mathbf{Q}_v^A)$ . Using that $A\subseteq U_{\textrm {good}}'\subseteq U_{\textrm {good}}$ (recall their definitions from equations (18) and (15)), the definition of $\mathcal{S}^A_{\textrm {err}}$ , the bound for $W_{\textrm {good}}$ from equation (11), and property (iii) from the construction of the sets $X_v(0)$ in Step II, we have that for all $x\in A$ ,

(20) \begin{align} |N_{\mathbf{Q}^A_0}(x)|&\leq |N_{Q^{\textrm {bad}}}(x)|+\Big |\sum _{v\in \mathcal{S}^A_{\textrm {err}}}N_{Q^{\textrm {good}}_v}(x)\cap W_{\textrm {good}}\Big |+|W\setminus W_{\textrm {good}}|\nonumber \\[3pt] &\leq \epsilon ^{1/8} |W|+|\mathcal{S}^A_{\textrm {err}}|\delta ^{1/8}|W|+7\epsilon ^{1/2}|W|\nonumber \\[3pt] &\leq (2\epsilon ^{1/8}+\ell \delta ^{1/8})|W|\nonumber \\[3pt] &\leq 3\epsilon ^{1/8}|W|, \end{align}

where the last inequality is by definition of $\delta$ (see equation (16)), and the second to last inequality uses that $\epsilon$ is sufficiently small. Thus we have shown conclusion (1) of Claim 4.6. Note this implies $|\mathbf{Q}_0^A|\leq 3\epsilon ^{1/8}|A||W|$ , and therefore, we now know that most of $K_2[A,W]$ is covered by the sets of the form $\mathbf{Q}^A_v$ for $v\in \mathcal{S}^A$ .

Our next goal is to define the edge colours $\mathbf{P}_{v,A}^0,\mathbf{P}_{v,A}^1,\mathbf{P}_{v,A}^2$ for each $v\in \mathcal{S}^A$ . By definition of $\mathcal{S}^A$ , we have that for each $v\in \mathcal{S}^A$ , $A\subseteq X_v(j_v)\subseteq N_{Q_v^{\textrm {good}}}(c_{v,j_v})$ for $1\leq j_v\leq t_v$ . We let $\mathcal{C}^A$ denote the set of these vertices $c_{v,j_v}$ , i.e. define

\begin{align*} \mathcal{C}^A\, :\!= \, \{c_{v,j_v}\, : \,v\in \mathcal{S}^A \}. \end{align*}

We now define two special subsets of $\mathcal{C}^A$ based on behaviour in the auxiliary structure $\mathcal{G}$ .

\begin{align*} \mathcal{C}^A_0=\{c_{v,j_v}\in \mathcal{C}^A\, : \,|N_{F_1}(q_v)|\leq \epsilon ^{1/16}r\},\text{ and }\mathcal{C}^A_1=\{c_{v,j_v}\in \mathcal{C}^A\, : \,|N_{F_0}(q_v)|\leq \epsilon ^{1/16} r\}. \end{align*}

We do not expect $\mathcal{C}^A_0\cup \mathcal{C}_1^A$ to necessarily cover all of $\mathcal{C}^A$ . Recall that by hypothesis (4), we know that for every $v\in [s]$ , $|N_{F_2}(q_v)|\leq \epsilon \ell$ . Consequently, since $\epsilon$ is sufficiently small, and by inequality equation (5), we can conclude that $\mathcal{C}^A_0\cap \mathcal{C}^A_1=\emptyset$ . We will next define the partition $K_2[A,V]=\mathbf{P}_{v,A}^0\cup \mathbf{P}_{v,A}^1\cup \mathbf{P}_{v,A}^2$ for each $v\in \mathcal{S}^A$ . How we define this partition depends on whether $c_{v,j_v}$ is in one of $\mathcal{C}^A_1$ , $\mathcal{C}^A_0$ , or neither (cases (a), (b), and (c) below). This definition will also make use of the edge-colours $P_v^0,P_v^1,P_v^2$ which were defined in equation equation (8).

1. (a) If $c_{v,j_v}\in \mathcal{C}^A_1$ , let $\mathbf{P}_{v,A}^0=\emptyset$ , and define

   \begin{align*} \mathbf{P}_{v,A}^1&=P_v^1\cap E(G^{\textrm {good}})\cap N_{\Gamma }(c_{v,j_v}),\text{ and }\\[3pt] \mathbf{P}_{v,A}^2&=K_2[A,V]\setminus \mathbf{P}_{v,A}^1. \end{align*}

2. (b) If $c_{v,j_v}\in \mathcal{C}^A_0$ , let $\mathbf{P}_{v,A}^1=\emptyset$ and define

   \begin{align*} \mathbf{P}_{v,A}^0&=P_v^0\cap E(G^{\textrm {good}})\cap N_{\Gamma }(c_{v,j_v}),\text{ and }\\[3pt] \mathbf{P}_{v,A}^2&=K_2[A,V]\setminus \mathbf{P}_{v,A}^0. \end{align*}

3. (c) If $c_{v,j_v}\in \mathcal{C}^A\setminus (\mathcal{C}^A_0\cup \mathcal{C}^A_1)$ , let

   \begin{align*} \mathbf{P}_{v,A}^0&=P_v^0\cap E(G^{\textrm {good}})\cap N_{\Gamma }(c_{v,j_v}),\\[3pt] \mathbf{P}_{v,A}^1&=P_v^1\cap E(G^{\textrm {good}})\cap N_{\Gamma }(c_{v,j_v}),\text{ and }\\[3pt] \mathbf{P}_{v,A}^2&=K_2[A,V]\setminus \Big (\mathbf{P}_{v,A}^1\cup \mathbf{P}_{v,A}^0\Big ). \end{align*}

To show these definitions work to satisfy the conclusions of Claim 4.6, we will need to compute the sizes of the edge colours above. For this, we will use the the following fact. By definition of $P^{\tau }_v$ (see equality equation (8)) and hypothesis (3b), we have that for all $x\in A$ , $v\in \mathcal{S}^A$ and $\tau \in \{0,1,2\}$ ,

(21) \begin{align} \Big (\frac {|V|}{\ell }-1\Big )|N_{F_{\tau }}(q_v)|\leq |N_{P^{\tau }_{v}}(x)|\leq |N_{F_{\tau }}(q_v)|\Big (\frac {|V|}{\ell }+1\Big ), \end{align}

where $N_{F_{\tau }}(q_v)$ is computed in the auxiliary structure $\mathcal{G}$ . We show that in all three cases, (a), (b), and (c), conclusion (2) of Claim 4.6 holds. Suppose first we are in case (a). Then by construction we have that for all $x\in A$ ,

\begin{align*} |N_{\mathbf{P}_{v,A}^2}(x)|&\leq |V\setminus N_{\Gamma }(xc_{v,j_v})|+|N_{P^{\textrm {bad}}}(x)|+\sum _{p_u\in N_{F_0}(q_v)\cup N_{F_2}(q_v)}|N_{P_u}(x)|\\[2pt] &\leq |V\setminus N_{\Gamma }(xc_{v,j_v})|+|N_{P^{\textrm {bad}}}(x)|+|N_{F_0}(q_v)\cup N_{F_2}(q_v)|\Big (\frac {|V|}{\ell }+1\Big ), \end{align*}

where the last inequality is by equation (21). Since $A\subseteq N_{Q_v^{\textrm {good}}}(c_{v,j_v})$ , we have that for all $x\in A$ ,

\begin{equation*} |V\setminus N_{\Gamma }(xc_{v,j_v})|\leq \epsilon ^{1/4}|V|. \end{equation*}

Since $A\subseteq U_{\textrm {good}}'$ , we have for all $x\in A$ , $|N_{P^{\textrm {bad}}}(x)|\leq \epsilon ^{1/8} |V_{\textrm {good}}|$ . Since we are in case (a), $c_{v,j_v}\in \mathcal{C}_A^1$ implies $|N_{F_0}(q_v)|\leq \epsilon ^{1/16}r$ . Hypothesis (4) implies $|N_{F_2}(q_v)|\leq \epsilon \ell$ . Combining these facts, we have that

\begin{align*} |N_{\mathbf{P}_{v,A}^2}(x)|&\leq \epsilon ^{1/4}|V|+\epsilon ^{1/8}|V_{\textrm {good}}|+(\epsilon \ell +\epsilon ^{1/16}r)\Big (\frac {|V|}{\ell }+1\Big ) \leq 4\epsilon ^{1/16}|V|, \end{align*}

where the last inequality uses that $r\leq \ell$ , the fact that $|V|$ is sufficiently large, and the fact that $\epsilon$ is sufficiently small. A similar computation shows that in case (b), we have for all $x\in A$ , $|N_{\mathbf{P}_{v,A}^2}(x)|\leq 4\epsilon ^{1/16}|V|$ . Suppose now we are in case (c). Then via a similar argument to the above, we have that for all $x\in A$ ,

\begin{align*} |N_{\mathbf{P}_{v,A}^2}(x)|\leq |V\setminus N_{\Gamma }(xc_{v,j_v})|+|N_{P^{\textrm {bad}}}(x)|+|N_{F_2}(q_v)|\Big (\frac {|V|}{\ell }+1\Big )&\leq \epsilon ^{1/4}|V|+\epsilon ^{1/8}|V|+2\epsilon |V|\\[3pt] &\leq 4\epsilon ^{1/16}|V|, \end{align*}

where the second to last inequality uses that $r\leq \ell$ and $|V|$ is sufficiently large. This finishes our verification of conclusion (2) of Claim 4.6.

We next verify conclusion (3) of Claim 4.6. Let $v\in \mathcal{S}^A$ . We want to show there is no $\mathbf{P}_{v,A}^0/\mathbf{P}_{v,A}^1$ -copy of $U(k)$ in $(A\cup V, \mathbf{P}_{v,A}^0,\mathbf{P}_{v,A}^1,\mathbf{P}_{v,A}^2)$ . If we are in cases (a) or (b), then $c_{v,j_v}\in \mathcal{C}^A_0\cup \mathcal{C}^A_1$ implies one of $\mathbf{P}_{v,A}^0$ or $\mathbf{P}_{v,A}^1$ is empty, so there is clearly no $\mathbf{P}_{v,A}^0/\mathbf{P}_{v,A}^1$ copy of $U(k)$ in $(A\cup V, \mathbf{P}_{v,A}^0,\mathbf{P}_{v,A}^1,\mathbf{P}_{v,A}^2)$ .

Assume now we are in case (c), so $c_{v,j_v}\in \mathcal{C}^A\setminus (\mathcal{C}^A_0\cup \mathcal{C}^A_1)$ . Suppose towards a contradiction there is a $\mathbf{P}_{v,A}^0/\mathbf{P}_{v,A}^1$ copy of $U(k)$ in $(A\cup V, \mathbf{P}_{v,A}^0,\mathbf{P}_{v,A}^1,\mathbf{P}_{v,A}^2)$ . This means there exist vertices $\{x_1,\ldots, x_{k}\}\cup \{y_S\, : \,S\subseteq [k]\}\subseteq A\cup V$ such that for all $1\leq j\leq k$ and $S\subseteq [k]$ , if $j\in S$ , then $x_jy_S\in P_v^{1}\cap N_{\Gamma }(c_{v,j_v})$ and if $j\notin S$ , then $x_jy_S\in P_{v}^{0}\cap N_{\Gamma }(c_{v,j_v})$ . However, since $A\subseteq N_{Q_v}(c_{v,j_v})$ , this contradicts Observation 4.5. This finishes our verification of conclusion (3) of Claim 4.6.

We just have left to show conclusion (4) of Claim 4.6. For each $v\in \mathcal{S}^A$ and $\tau \in \{0,1,2\}$ define the triad

\begin{align*} T(\mathbf{P}_{v,A}^{\tau },\mathbf{Q}^A_v)=(A\cup V\cup W, \mathbf{P}_{v,A}^{\tau }\cup \mathbf{Q}_v^A\cup K_2[V,W]). \\[-10pt] \end{align*}

Fix $v\in \mathcal{S}^A$ and $\tau \in \{0,1\}$ , and assume $\mathbf{P}_{v,A}^{\tau }\neq \emptyset$ . We want to show $T(\mathbf{P}_{v,A}^{\tau },\mathbf{Q}^A_v)$ is $2\epsilon ^{3/16}$ -homogeneous with respect to $H$ . Since $A\subseteq N_{Q_v^{\textrm {good}}}(c_{v,j_v})$ , we have that for all $x\in A$ , $xc_{v,j_v}\in E(G^{\textrm {good}})$ , and consequently,

\begin{align*} |N_{\Gamma }(c_{v,j_v})\cap K_2[\{x\},V]|\geq (1-\epsilon ^{1/4})|V|. \\[-10pt] \end{align*}

Combining this with the fact $A\subseteq U_{\textrm {good}}'$ , we have that for all $x\in A$ ,

(22) \begin{align} |N_{\textbf {P}_{v,A}^{\tau }}(x)|\geq |N_{P_{v}^{\tau }}(x)|{-}|N_{P^{\textrm {bad}}}(x)|{-}|V\setminus N_{\Gamma }(xc_{v,j_v})|&\geq |N_{F_{\tau }}(q_v)|\Big (\frac {|V|}{\ell }-1\Big )-\epsilon ^{1/8}|V_{\textrm {good}}|-\epsilon ^{1/4}|V|\nonumber \\[3pt] &\geq \epsilon ^{1/16}r\Big (\frac {|V|}{\ell }-1\Big )-3\epsilon ^{1/8}|V|\nonumber \\[3pt] &\geq \frac {\epsilon ^{1/16}|V|}{2}, \end{align}

where the inequalities use equation (21), the fact that $\mathbf{P}_{v,A}^{\tau }\neq \emptyset$ implies $|N_{F_{\tau }}(q_v)|\geq \epsilon ^{1/16}r$ , inequality equation (5), the fact that $|V|$ is sufficiently large, and the fact that $\epsilon$ is sufficiently small. We now have the following, where we recall $E(H)^1=E(H)$ and $E(H)^0={\binom{V(H)}{3}}\setminus E(H)$ .

\begin{align*} |E(H)^{\tau }\cap K_3^{(2)}(T(\mathbf{P}_{v,A}^{\tau },\mathbf{Q}^A_v))|&\geq \sum _{x\in A} |N_{\Gamma }(x)\cap K_2[N_{\mathbf{P}_{v,A}^{\tau }}(x),N_{\mathbf{Q}^A_v}(x)]|\\[3pt] &=\sum _{x\in A}\bigg (\sum _{w\in N_{\mathbf{Q}_v^A}(x)}|N_{\Gamma }(xw)\cap N_{\mathbf{P}_{v,A}^{\tau }}(x)|\bigg ) \\[3pt] &\geq \sum _{x\in A}\bigg (\sum _{w\in N_{\mathbf{Q}_v^A}(x)}(|N_{\mathbf{P}_{v,A}^{\tau }}(x)|-|V\setminus N_{\Gamma }(xw)|)\bigg )\\[3pt] &\geq \sum _{x\in A}\bigg (\sum _{w\in N_{\mathbf{Q}_v^A}(x)}(|N_{\mathbf{P}_{v,A}^{\tau }}(x)|- \epsilon ^{1/4}|V|)\bigg ), \end{align*}

where the last inequality uses $\mathbf{Q}_v^A\subseteq Q_v^{\textrm {good}}$ . Using equation (22), this is at least

\begin{align*} \sum _{x\in A}\sum _{w\in N_{\mathbf{Q}_v^A}(x)}|N_{\mathbf{P}_{v,A}^{\tau }}(x)|(1- 2\epsilon ^{3/16})&=(1-2\epsilon ^{3/16})\sum _{x\in A}|N_{\mathbf{Q}_v^A}(x)||N_{\mathbf{P}_{v,A}^{\tau }}(x)|\\[3pt] &=(1-2\epsilon ^{3/16})|K_3^{(2)}(T(\mathbf{P}_{v,A}^{\tau },\mathbf{Q}^A_v))|, \end{align*}

where the last inequality uses equation (22). This finishes our verification of conclusion (4), and thus we have finished proving Claim 4.6.