Hypergraph regularity - Higher-order Uniformity and Applications

2 Hypergraph regularity

Proposition 2.1. Let $X, Y, Z$ be sets and let $f : X \times Y \times Z \to [- 1, 1]$ be a function. Then the following are equivalent:

(i) $𝔼_{x_{0}, x_{1} \in X} 𝔼_{y_{0}, y_{1} \in Y} 𝔼_{z_{0}, z_{1} \in Z} \prod_{(i, j, k) \in {0, 1}^{3}} f (x_{i}, y_{j}, z_{k}) \leq c_{1}$ .
(ii) $| 𝔼_{x \in X, y \in Y, z \in Z} f (x, y, z) u (x, y) v (x, z) w (y, z) | \leq c_{2}$ for any $u : X \times Y \to [- 1, 1]$ , $v : X \times Z \to [- 1, 1]$ , $w : Y \times Z \to [- 1, 1]$ .
(iii) For any tripartite graph $G$ on $X \cup Y \cup Z$ , the average of $f$ restricted to $△ (G) : triangles in G$ is at most $c_{3}$ in absolute value.

The objects we count in (i) are octahedra:

Proof. Omitted (but the proof is the same as the proof of Proposition 1.5, only with more Cauchy Schwarzing). □

Definition 2.2. Say $f : X \times Y \times Z \to [- 1, 1]$ is $𝜀$ -quasirandom if it satisfies Proposition 2.1(i) with $c_{1} = 𝜀^{8}$ . A $3$ -partite $3$ -uniform hypergraph $H$ on $X \cup Y \cup Z$ of density $δ$ is $𝜀$ -quasirandom if $f (x, y, z) = 𝟙_{H} (x, y, z) - δ$ is $𝜀$ -quasirandom.

Proposition 2.3. Let $H$ be a $4$ -partite $3$ -uniform hypergraph on vertex set $X \cup Y \cup Z \cup W$ . Suppose $H (X, Y, Z), H (X, Z, W), H (X, Y, W), H (Y, Z, W)$ are all $𝜀$ -quasirandom of densities $δ_{X Y Z}, δ_{X Z W}, δ_{X Y W}, δ_{Y Z W}$ respectively. Then

| 𝔼_{x, y, z, w} 𝟙_{H} (x, y, z) 𝟙_{H} (x, y, w) 𝟙_{H} (x, z, w) 𝟙_{H} (y, z, w) - δ_{X Y Z} δ_{X Y W} δ_{X Z W} δ_{Y Z W} | \leq 10 𝜀 .

Proof. Omitted (see Example Sheet). □

But this notion is too strong to facilitate a regularity lemma.

Example 2.4. Let $G$ be a random tripartite graph on $X \cup Y \cup Z$ of edge density $\frac{1}{2}$ . Let $H$ be the $3$ -uniform hypergraph consisting of all triangles in $G$ . The edge density of $H$ is $\frac{1}{8}$ . The proportion of octahedra: ${(\frac{1}{2})}^{12}$ . But, if $H$ were quasirandom, we would expect ${(\frac{1}{2})}^{8}$ .

Not only does $H$ fail to be quasirandom, so does any induced subhypergraph.

Example 2.5. Let $G$ be a tripartite graph $X \cup Y \cup Z$ with each part $G (X, Y), G (X, Z), G (Y, Z)$ quasirandom, of edge density $δ_{X Y}, δ_{X Z}, δ_{Y Z}$ respectively. Let $H$ be a random hypergraph chosen with $ℙ = δ$ from the $3$ -hypergraph formed by $△ (G)$ .

Then the expected number of octahedra in $H$ is

{(δ_{X Y} δ_{X Z} δ_{Y Z})}^{4} δ^{8} | X |^{2} | Y |^{2} | Z |^{2} .

Definition 2.6. Let $G$ be a $3$ -partite graph on vertex set $X \cup Y \cup Z$ , and let $f : X \times Y \times Z \to [- 1, 1]$ be a function supported on $△ (G)$ . We say $f$ is $𝜀$ -quasirandom relative to $G$ if

𝔼_{\begin{array}{c} x_{0}, x_{1} \in X \\ y_{0}, y_{1} \in Y \\ z_{0}, z_{1} \in Z \end{array}} \prod_{(i, j, k) \in {0, 1}^{3}} f (x_{i}, y_{j}, z_{k}) \leq 𝜀^{8} {(δ_{X Y} δ_{X Z} δ_{Y Z})}^{4} .

Let $H$ be a $3$ -partite $3$ -uniform hypergraph on $X \cup Y \cup Z$ , and suppose $H \subseteq △ (G)$ , $| H | = δ | △ (G) |$ . We say $H$ is $𝜀$ -quasirandom relative to $G$ if

f (x, y, z) = {\begin{matrix} 𝟙_{H} (x, y, z) - δ & if (x, y, z) \in △ (G) \\ 0 & otherwise \end{matrix}

is $𝜀$ -quasirandom relative to $G$ .

Proposition 2.7. Let $G$ be a $4$ -partite graph on $X \cup Y \cup Z \cup W$ with all six bipartite parts $𝜀$ -quasirandom. Let $f : X \times Y \times Z \to [- 1, 1]$ , $g : X \times Y \times W \to [- 1, 1]$ , $h : X \times Z \times W \to [- 1, 1]$ , $k : Y \times Z \times W \to [- 1, 1]$ , all supported on $△ (G)$ . Suppose that $f$ is $η$ -quasirandom relative to $G (X, Y, Z)$ . Then provided $𝜀^{\frac{1}{4}} \leq 2^{- 38} {(η δ)}^{8}$ ,

| 𝔼_{x, y, z, w} f (x, y, z) g (x, y, w) h (x, z, w) k (y, z, w | \leq 2 η δ,

where

δ : = δ_{X Y} δ_{X Z} δ_{X W} δ_{Y Z} δ_{Y W} δ_{Z W} .

Note that this proposition is much easier to prove if we use the much stronger notion of quasirandomness that was introduced at the beginning of this section.

Notation.

\begin{array}{l} δ_{Z W} & = \frac{| G (Z, W) |}{| Z | | W |} \\ δ_{Y Z W} & = \frac{number of triangles in G (Y, Z, W)}{| Y | | Z | | W |} \\ δ_{Y} (x, x^{'}) & = \frac{number of y \in Y such that x \sim y, x^{'} \sim y}{| Y |} \\ δ_{Z W} (x, x^{'}) & = \frac{number of edges z w in G (Z, W) such that x \sim z, x \sim w, x^{'} \sim z, x^{'} \sim w}{| Z | | W |} \end{array}

Proof.

\begin{array}{l} | 𝔼_{y, z, w} k (y, z, w) 𝔼_{x} f (x, y, z) g (x, y, w) h (x, z, w) |^{8} \\ \leq {(𝔼_{y, z, w} k {(y, z, w)}^{2})}^{4} {(𝔼_{y, z, w} | 𝔼_{x} f (x, y, z) g (x, y, w) h (x, z, w) |^{2})}^{4} \\ \leq δ_{Y Z W}^{4} {(𝔼_{x, x^{'}} 𝔼_{y, z, w} \underset{f (x, y, z) f (x^{'}, y, z)}{\underset{⏟}{f_{x, x^{'}} (y, z)}} g_{x, x^{'}} (y, w) h_{x, x^{'}} (z, w))}^{4} \\ \leq δ_{Y Z W}^{4} 𝔼_{x, x^{'}} {(𝔼_{y, z, w} f_{x, x^{'}} (y, z) g_{x, x^{'}} (y, w) h_{x, x^{'}} (z, w))}^{4} \\ = δ_{Y Z W}^{4} 𝔼_{x, x^{'}} {(𝔼_{z, w} h_{x, x^{'}} (z, w) 𝔼_{y} f_{x, x^{'}} (y, z) g_{x, x^{'}} (y, w))}^{4} \end{array}

So far, we haven’t done anything difficult, but the first tricky step comes now. It will be important that we do not (immediately) separate $h_{x, x^{'}} (z, w)$ from the rest of the expression, because it will be important that we use the fact that $h_{x, x^{'}} (z, w)$ is only supported on triangles of $G$ .

\begin{array}{l} δ_{Y Z W}^{4} 𝔼_{x, x^{'}} {(𝔼_{z, w} h_{x, x^{'}} (z, w) 𝔼_{y} f_{x, x^{'}} (y, z) g_{x, x^{'}} (y, w))}^{4} \\ = δ_{Y Z W}^{4} 𝔼_{x, x^{'}} {(𝔼_{z, w} h_{x, x^{'}} (z, w) 𝟙_{G} (z, w) 𝔼_{y} f_{x, x^{'}} (y, z) g_{x, x^{'}} (y, w))}^{4} \\ \leq δ_{Y Z W}^{4} 𝔼_{x, x^{'}} {(𝔼_{z, w} h_{x, x^{'}} {(z, w)}^{2})}^{2} {(𝔼_{z, w} 𝟙_{G} (z, w) {(𝔼_{y} f_{x, x^{'}} (y, z) g_{x, x^{'}} (y, w))}^{2})}^{2} \\ \leq δ_{Y Z W}^{4} 𝔼_{x, x^{'}} δ_{Z W} {(x, x^{'})}^{2} {(𝔼_{y, y^{'}} 𝔼_{z, w} \underset{: = f_{x, x^{'}} (y, z) f_{x, x^{'}} (y^{'}, z)}{\underset{⏟}{f_{x, x^{'}, y, y^{'}} (z)}} g_{x, x^{'}, y, y^{'}} (w) 𝟙_{G} (z, w))}^{2} \\ \leq δ_{Y Z W}^{4} 𝔼_{x, x^{'}} δ_{Z W} {(x, x^{'})}^{2} {(𝔼_{y, y^{'}} 𝔼_{w} g_{x, x^{'}, y, y^{'}} (w) 𝔼_{z} f_{x, x^{'}, y, y^{'}} (z) 𝟙_{G} (z, w))}^{2} \\ = δ_{Y Z W}^{4} 𝔼_{x, x^{'}} δ_{Z W} {(x, x^{'})}^{2} {(\underset{= 𝔼_{y, y^{'}} \prod 𝟙_{G} (x, y) 𝔼_{z, w} f_{x, x^{'}, y, y^{'}} (z) g_{x, x^{'}, y, y^{'}} (w) 𝟙_{G} (z, w)}{\underset{⏟}{𝔼_{y, y^{'}} 𝔼_{w} g_{x, x^{'}, y, y^{'}} (w) 𝟙_{G} (x, q) 𝟙_{G} (x^{'}, y) 𝟙_{G} (x, y^{'}) 𝟙_{G} (x^{'}, y^{'}) 𝔼_{z} f_{x, x^{'}, y, y^{'}} (z) 𝟙_{G} (z, w)}})}^{2} \\ \leq δ_{Y Z W}^{4} 𝔼_{x, x^{'}} δ_{Z W} {(x, x^{'})}^{2} (𝔼_{y, y^{'}} \prod 𝟙_{G}) (𝔼_{y, y^{'}} | 𝔼_{z, w} f_{x, x^{'}, y, y^{'}} (z) g_{x, x^{'}, y, y^{'}} (w) 𝟙_{G} (z, w) |^{2}) \\ = δ_{Y Z W}^{4} 𝔼_{x, x^{'}} δ_{Z W} {(x, x^{'})}^{2} δ_{Y} {(x, x^{'})}^{2} 𝔼_{y, y^{'}} {(𝔼_{w} g_{x, x^{'}, y, y^{'}} (w) 𝟙_{G} (w, x) 𝟙_{G} (w, x^{'}) 𝟙_{G} (w, y) 𝟙_{G} (w, y^{'}) 𝔼_{z} f_{x, x^{'}, y, y^{'}} (z) 𝟙_{G} (z, w))}^{2} \\ \leq δ_{Y Z W}^{4} 𝔼_{x, x^{'}} δ_{Z W} {(x, x^{'})}^{2} δ_{Y} {(x, x^{'})}^{2} 𝔼_{y, y^{'}} (\underset{= : δ_{W} (x, x^{'}, y, y^{'})}{\underset{⏟}{𝔼_{w} 𝟙_{u g} (w, x) 𝟙_{G} (w, x^{'}) 𝟙_{G} (w, y) 𝟙_{G} (w, y^{'})}}) 𝔼_{w} | 𝔼_{z} f_{x, x^{'}, y^{'}, y^{'}} (z) 𝟙_{G} (z, w) |^{2} \\ = 𝔼_{x, x^{'}, y, y^{'}, z, z^{'}} \underset{f_{x, x^{'}, y, y^{'}} (z) f_{x, x^{'}, y, y^{'}} (z^{'})}{\underset{⏟}{f_{x, x^{'}, y, y^{'}, z, z^{'}}}} ϕ (x, x^{'}, y, y^{'}, z, z^{'}) \\ = 𝔼_{x, x^{'}, y, y^{'}, z, z^{'}} F (x, x^{'}, y, y^{'}, z, z^{'} ϕ (x, x^{'}, y, y^{'}, z, z^{'}) \\ = ⟨ F, ϕ ⟩ \end{array}

where

\begin{array}{l} ϕ (x, x^{'}, y, y^{'}, z, z^{'}) & = δ_{Y Z W}^{4} δ_{Z W} {(x, x^{'})}^{2} δ_{Y} {(x, x^{'})}^{2} δ_{W} (x, x^{'}, y, y^{'}) δ_{W} (x, x^{'}, y, y^{'}, z, z^{'}) \\ F (x, x^{'}, y, y^{'}, z, z^{'}) & = f_{x, x^{'}, y, y^{'}, z, z^{'}} \end{array}

Note that $ϕ$ only depends on the underlying graph, which we assumed was $𝜀$ -quasirandom. We can compute

𝔼_{x, x^{'}, y, y^{'}, z, z^{'}} ϕ (x, x^{'}, y, y^{'}, z, z^{'}) = {(δ_{Y Z} δ_{Y Z} δ_{Z W})}^{4} \dots = {(δ_{X Y} δ_{Y Z} δ_{X Z})}^{4} {(δ_{X W} δ_{Y W} δ_{Z W})}^{8} = : 𝜃 .

Want to show:

⟨ u f, ϕ ⟩ \approx ⟨ F, 𝜃 ⟩ = 𝜃 \underset{\leq η^{8} {(δ_{X Y} δ_{X Z} δ_{Y Z})}^{4}}{\underset{⏟}{⟨ F, 1 ⟩}} .

Claim 2.8. Suppose $2^{38} 𝜀^{\frac{1}{4}} \leq σ 𝜃$ . Then $ϕ (x, x^{'}, y, y^{'}, z, z^{'})$ differs from $𝜃$ by more than $σ 𝜃$ for at most a $σ 𝜃$ -proportion of $(x, x^{'}, y, y^{'}, z, z^{'}) \in X^{2} \times Y^{2} \times Z^{2}$ .

Proof: See Example Sheet 1.

Let $σ = η^{8} {(δ_{X Y} δ_{X Z} δ_{Y Z})}^{4}$ . Call $(x, x^{'}, y, y^{'}, z, z^{'})$ bad if $| ϕ (x, x^{'}, y, y^{'}, z, z^{'}) - 𝜃 | > σ 𝜃$ , and good otherwise. Let

\tilde{ϕ} (x, x^{'}, y, y^{'}, z, z^{'}) = {\begin{matrix} ϕ (x, x^{'}, y, y^{'}, z, z^{'}) & if (x, x^{'}, y, y^{'}, z, z^{'}) is good \\ 𝜃 & otherwise \end{matrix}

By the claim, $∥ ϕ - \tilde{ϕ} ∥_{1} \leq 2 σ 𝜃$ and $∥ \tilde{ϕ} - σ ∥_{\infty} \leq σ 𝜃$ , and also $∥ F ∥_{1} \leq 1$ , $∥ F ∥_{\infty} \leq 1$ . Hence

\begin{array}{l} | ⟨ F, ϕ ⟩ - ⟨ F, 𝜃 ⟩ | & \leq | ⟨ F, ϕ - \tilde{ϕ} ⟩ | + | ⟨ F, \tilde{ϕ} - 𝜃 ⟩ | \\ \leq ∥ F ∥_{\infty} ∥ ϕ - \tilde{ϕ} ∥_{1} + ∥ F ∥_{1} ∥ \tilde{ϕ} - 𝜃 ∥_{\infty} \\ \leq 3 σ 𝜃 \\ = 3 η^{8} \cdot δ^{8} \end{array}

But

| ⟨ F, 𝜃 ⟩ | \leq 𝜃 η^{8} {(δ_{X Y} δ_{X Z} δ_{Y Z})}^{4} = η^{8} \cdot δ^{8}

| 𝔼_{x, y, z, w} f (x, y, z) g (x, y, w) h (x, z, w) k (y, z, w) |^{8} \leq | ⟨ F, ϕ ⟩ | \leq | ⟨ F, ϕ ⟩ | + 3 η^{8} δ^{8} \leq 4 {(η δ)}^{8} . □

Corollary 2.9 (Simplex counting lemma). Let $G$ be a $4$ -partite graph on $X_{1} \cup X_{2} \cup X_{3} \cup X_{4}$ , with all six bipartite graphs $𝜀$ -quasirandom of densities $δ_{i j}$ respectively. Let $H_{i j k}$ be a $3$ -partite $3$ -uniform hypergraph on $X_{i} \cup X_{j} \cup X_{k}$ which is $η$ -quasirandom relative to $△ (G (X_{i}, X_{j}, X_{k}))$ , of relative density $δ_{i j k}$ . Let $H = H_{123} \cup H_{134} \cup H_{124} \cup H_{234}$ . Then

| 𝔼_{x_{1}, x_{2}, x_{3}, x_{4}} 𝟙_{H} (x_{1}, x_{2}, x_{3}) 𝟙_{H} (x_{1}, x_{2}, x_{4}) 𝟙_{H} (x_{1}, x_{3}, x_{4}) 𝟙_{H} (x_{2}, x_{3}, x_{4}) - \prod δ_{i j k} \prod δ_{i j} | \leq 8 η \prod δ_{i j} .

Proof. Let

f (x_{1}, x_{2}, x_{3}) = 𝟙_{H} (x_{1}, x_{2}, x_{3}) - δ_{123} 𝟙_{G} (x_{1}, x_{2}) 𝟙_{G} (x_{1}, x_{3}) 𝟙_{G} (x_{2}, x_{3}) t

and consider

𝔼_{x_{1}, x_{2}, x_{3}, x_{4}} f (x_{1}, x_{2}, x_{3}) 𝟙_{H} (x_{1}, x_{2}, x_{4}) 𝟙_{H} (x_{1}, x_{3}, x_{4}) 𝟙_{H} (x_{2}, x_{3}, x_{4}) .

By Proposition 2.7, this is at most $2 η \prod δ_{i j}$ (in absolute value). Iterate. □

Definition 2.10 (Relative msd). Let $U$ be a set, let $f : U \to ℝ$ , and let $U = B_{1} \cup B_{2} \cup \dots \cup B_{r}$ be a partition of $U$ . Then the mean square density (msd) of $f$ relative to this partition is

\sum_{i = 1}^{r} \frac{| B_{i} |}{| U |} | 𝔼_{x \in B_{i}} f (x) |^{2} .

Lemma 2.11. Let $U$ be a set, $f, g : U \to [- 1, 1]$ , $U = B_{1} \cup B_{2} \cup \dots \cup B_{r}$ . Suppose $g$ is constant on each $B_{i}$ . Then the mean square density of $f$ relative to the partition is $\geq \frac{{⟨ f, g ⟩}^{2}}{∥ g ∥_{2}^{2}}$ .

Definition 2.12. Let $G$ be a $3$ -partite graph on $X \cup Y \cup Z$ , and suppose that $G (X, Y)$ , $G (X, Z)$ , $G (Y, Z)$ are partitioned into $⋃_{i} G_{i} (X, Y)$ , $⋃_{j} G_{j} (X, Z)$ , $⋃_{k} G_{k} (Y, Z)$ , respectively. For each $(x, y, z) \in △ (G)$ , let its index be the triple $(i, j, k)$ such that $x y \in G_{i} (X, Y)$ , $x z \in G_{j} (X, Z)$ , $y z \in G_{k} (Y, Z)$ .

The induced partition of $△ (G)$ is the partition of triples in $△ (G)$ according to their index.

[A typical cell of this partition looks like $△ (G_{i} (X, Y) \cup G_{j} (X, Z) \cup G_{k} (Y, Z))$ .]

If $f : X \times Y \times Z \to [- 1, 1]$ , then the msd of $f$ relative to the partitions $⋃_{i} G_{i} (X, Y)$ , $⋃_{j} G_{j} (X, Z)$ , $⋃_{k} G_{k} (Y, Z)$ is defined to be the msd of $f$ relative to the induced partition.

Lemma 2.13. Let $G$ be a $3$ -partite graph on $X \cup Y \cup Z$ with bipartite parts of densities $δ_{X Y}, δ_{X Z}, δ_{Y Z}$ , respectively. Let $δ = δ_{X Y} δ_{X Z} δ_{Y Z}$ , and suppose all bipartite parts are $𝜀$ -quasirandom. Let $H$ be a $3$ -partite $3$ -uniform hypergraph on $X \cup Y \cup Z$ , and let the relative density of $H$ in $△ (G)$ be $γ$ . Suppose $2^{21} 𝜀 < δ^{7}$ , and suppose $H$ is not $η$ -quasirandom relative to $△ (G)$ . Then there are partitions $G (X, Y) = G_{1} (X, Y) \cup \dots \cup G_{l} (X, Y)$ , $G (X, Z) = G_{1} (X, Z) \cup \dots \cup G_{m} (X, Z)$ , $G (Y, Z) = G_{1} (Y, Z) \cup \dots \cup G_{n} (Y, Z)$ relative to which the msd of $H$ is $\geq γ^{2} + 2^{- 11} η^{16}$ . Moreover, $l, m, n \leq 3^{3 δ^{- 2}}$ .

Proof. Let

f (x, y, z) = (𝟙_{H} (x, y, z) - γ) 𝟙_{G} (x, y) 𝟙_{G} (x, z) 𝟙_{G} (y, z) .

The hypothesis amounts to

𝔼_{x, x^{'}, y, y^{'}, z, z^{'}} f_{x, x^{'}, y, y^{'}, z, z^{'}} \geq η^{8} δ^{4} . (†)

For each $(x, y, z) \in △ (G)$ , let

F_{x y z} (x^{'}, y^{'}, z^{'}) = \frac{f_{x, x^{'}, y, y^{'}, z, z^{'}}}{f (x^{'}, y^{'}, z^{'})}

and let

F (x^{'}, y^{'}, z^{'}) = 𝔼_{x, y, z} F_{x y z} (x^{'}, y^{'}, z^{'}) .

Then (†) becomes

𝔼_{x, x^{'}, y, y^{'}, z, z^{'}} F_{x y z} (x^{'}, y^{'}, z^{'}) f (x^{'}, y^{'}, z^{'}) = 𝔼_{x, y, z} \underset{𝔼_{x^{'}, y^{'}, z^{'}}}{\underset{⏟}{⟨}} f, F_{x y z} ⟩ .

Note that each of the $F_{x y z}$ can be written as a product

u (x^{'}, y^{'}) v (y^{'}, z^{'}) w (x^{'}, z^{'}),

where each of $u, v, w \to [- 1, 1]$ .

For each $(x, y, z) \in △ (G)$ and each pair $(x^{'}, y^{'})$ , define $ũ (x^{'}, y^{'})$ as follows:

If $u (x^{'}, y^{'}) > 0$ , then
$ũ (x^{'}, y^{'}) = {\begin{matrix} 1 & with probability u (x^{'}, y^{'}) \\ 0 & otherwise \end{matrix}$
If $u (x^{'}, y^{'}) < 0$ , then
$ũ (x^{'}, y^{'}) = {\begin{matrix} - 1 & with probability - u (x^{'}, y^{'}) \\ 0 & otherwise \end{matrix}$
If $u (x^{'}, y^{'}) = 0$ , then $ũ (x^{'}, y^{'}) = 0$ .

Same for $v, w$ .

Finally, let

{\tilde{F}}_{x y z} (x^{'}, y^{'}, z^{'}) = ũ (x^{'}, y^{'}) ṽ (x^{'}, z^{'}) \tilde{w} (y^{'}, z^{'}),

and observe that the expectation (in the random choices of $ũ, ṽ, \tilde{w}$ described above) of ${\tilde{F}}_{x y z} (x^{'}, y^{'}, z^{'})$ is $F_{x y z} (x^{'}, y^{'}, z^{'})$ . Let $\tilde{F} (x^{'}, y^{'}, z^{'}) = 𝔼_{x, y, z} {\tilde{F}}_{x y z} (x^{'}, y^{'}, z^{'})$ . Since the expectation of $⟨ f, {\tilde{F}}_{x y z} ⟩$ equals $⟨ f, F_{x y z} ⟩$ , we can make random choices so that $⟨ f, \tilde{F} ⟩ \geq η^{8} δ^{4}$ (so from now on, “expectation” no longer refers to expectation over the possible random choices of $ũ, ṽ, \tilde{w}$ ).

Let $r \geq δ^{- 2}$ , choose ${\tilde{F}}_{1}, \dots, {\tilde{F}}_{r}$ at random from ${\tilde{F}}_{x y z}$ and let $D = \frac{1}{r} \sum_{i \in [r]} {\tilde{F}}_{i}$ . For each $i \in [r]$ , the expectation of $⟨ f, {\tilde{F}}_{i} ⟩$ is at least $\frac{1}{δ_{X Y Z}} ⟨ f, \tilde{F} ⟩$ , where $δ_{X Y Z} = \frac{| △ (G) |}{| X | | Y | | Z |}$ . So the expectation of $⟨ f, D ⟩$ is at least $\geq \frac{η^{8} δ^{4}}{δ_{X Y Z}}$ . By Counting Lemma, and the upper bound on $𝜀$ , $\frac{δ}{2} \leq δ_{X Y Z} \leq 2 δ$ . So the expectation of $⟨ f, D ⟩$ is at least $\frac{η^{8} δ^{2}}{δ_{X Y Z}} \cdot δ^{2} \geq \frac{η^{8} δ^{2}}{4} δ_{X Y Z}$ .

Note that

\begin{array}{l} ∥ \tilde{F} ∥_{2}^{2} & = 𝔼_{x^{'}, y^{'}, z^{'}} | 𝔼_{x, y, z} {\tilde{F}}_{x y z} (x^{'}, y^{'}, z^{'}) |^{2} \\ \leq 𝔼_{x^{'}, y^{'}, z^{'}} | 𝔼_{x, y, z} \underset{as a graph}{\underset{⏟}{𝟙_{K_{2, 2, 2}}}} (x, x^{'}, y, y^{'}, z, z^{'}) |^{2} \\ = 𝔼_{x^{'}, y^{'}, z^{'}} 𝔼_{\begin{array}{c} x_{1}, y_{1}, z_{1} \\ x_{2}, y_{2}, z_{2} \end{array}} 𝟙_{K_{2, 2, 2}} (x_{1}, x^{'}, y_{1}, y^{'}, z_{1}, z^{'}) 𝟙_{K_{2, 2, 2}} (x_{2}, x^{'}, y_{2}, y^{'}, z_{2}, z^{'}) \end{array}

So we are counting a $3$ -partite graph on $X \cup Y \cup Z$ with $3$ vertices in each part and $7$ edges between each part.

By a generalisation of Counting Lemma and the upper bound on $𝜀$ , $∥ \tilde{F} ∥_{2}^{2} \leq 2 δ^{7} \leq 16 δ^{4} δ_{X Y Z}^{3}$ , since $\frac{δ}{2} \leq δ_{X Y Z}$ . By Example Sheet 1 Problem 11, the expectation of $∥ D ∥_{2}^{2}$ is at most $2 δ_{X Y Z}^{- 2} ∥ \tilde{F} ∥_{2}^{2} \leq 32 δ^{4} δ_{X Y Z}$ , provided $r \geq δ^{- 2}$ . Hence the expectation of $256 δ^{2} ⟨ f, D ⟩ - η^{8} ∥ D ∥_{2}^{2}$ is at least $32 η^{8} δ^{4} δ_{X Y Z}$ . It follows that there is a choice of ${\tilde{F}}_{1}, \dots, {\tilde{F}}_{r}$ such that

⟨ f, D ⟩ \geq \frac{η^{8} δ^{2} δ_{X Y Z}}{8}

and $∥ D ∥_{2}^{2} \leq 256 δ^{2} η^{- 8} ⟨ f, D ⟩$ . For such $D$ ,

\frac{⟨ f, D ⟩}{∥ D ∥_{2}^{2}} \geq \frac{η^{8} δ^{2} δ_{X Y Z}}{8 \cdot 2^{8} δ^{2} η^{- 8} \underset{\leq δ_{X Y Z}}{\underset{⏟}{⟨ f, D ⟩}}} \geq \frac{η^{16}}{2^{11}} . □

Definition 2.14. An $r$ -partite chain is a $(G, H)$ , where $G$ is an $r$ -partite graph, $H$ an $r$ -partite hypergraph on the same vertex set as $G$ and $H \subseteq △ (G)$ . Let $ψ (η, δ)$ be a polynomial in $η$ and $δ$ which vanishes when either is $0$ .

A $4$ -partite chain $(G, H)$ is $(η, ψ)$ -quasirandom if

All four $3$ -partite parts of $H$ are $η$ -quasirandom relative to $G$
all six bipartite parts of $G$ are $ψ (η, δ)$ -quasirandom, where $δ$ is the product of the densities of the bipartite parts of $G$ . Shall use this with $ψ (η, δ) = {(2^{- 38} η^{8} 8^{8})}^{32}$ .

Remark. We call it a chain because when generalised to $4$ -uniform, $5$ -uniform etc, we would use $(G, H, K, \dots)$ rather than $(G, H)$ .

Definition 2.15. Let $X_{1}, X_{2}, X_{3}, X_{4}$ be four sets. Then a decomposition of the complete $4$ -partite graph $K (X_{1} \cup X_{2} \cup X_{3} \cup X_{4})$ consists of the following:

For each $X_{i}$ a partition into subsets $X_{i}^{(1)} \cup \dots \cup X_{i}^{(n_{i})}$ .
For each $K (X_{i} \cup X_{j})$ , a partition into subgraphs
$G_{i j}^{(1)} \cup \dots G_{i j}^{(m_{i j})} .$

A typical graph $G$ in this decomposition will have vertex sets $X_{i}^{(r)}, X_{j}^{(s)}, X_{k}^{(t)}$ and edge set

G_{i j}^{(u)} (X_{i}^{(r)} \cup X_{j}^{(s)}) \cup G_{i j}^{(v)} (X_{i}^{(r)} \cup X_{k}^{(t)}) \cup G_{j k}^{(w)} (X_{j}^{(s)} \cup X_{k}^{(t)}) . (†)

Given a $4$ -partite $3$ -uniform hypergraph $H$ on $X_{1} \cup X_{2} \cup X_{3} \cup X_{4}$ , we obtain an induced $3$ -partite $3$ -uniform hypergraph on $X_{i}^{(r)} \cup X_{j}^{(s)} \cup X_{t}^{(t)}$ with edges given by $E (H) \cap △ (†)$ .

The pair $(G, H)$ is a chain. The associated chain decomposition (ACD) of $H$ is the set of all chains arising from a given decomposition.

Definition 2.16. Let $H$ be a $4$ -partite $3$ -uniform hypergraph on $X_{1} \cup X_{2} \cup X_{3} \cup X_{4}$ , and suppose we have a decomposition of $K (X_{1} \cup X_{2} \cup X_{3} \cup X_{4})$ . Then the associated chain decomposition of $H (X_{i} \cup X_{j} \cup X_{k})$ is said to be $(𝜀, η, ψ)$ -quasirandom if for all but $𝜀 | X_{i} | | X_{j} | | X_{k} |$ edges $(x_{i}, x_{j}, x_{k})$ , the associated tripartite chain in which $(x_{i}, x_{j}, x_{k})$ lies is $(η, ψ)$ -quasirandom. The associated chain decomposition of $H$ is $(𝜀, η, ψ)$ -quasirandom if all four parts (e.g. $H (X_{1} \cup X_{2} \cup X_{3})$ ) are.

Theorem 2.17. Let $H$ be a $4$ -partite $3$ -uniform hypergraph on $X \cup Y \cup Z \cup W$ , and let $𝜀, η > 0$ . Then there is a decomposition of $K (X \cup Y \cup Z \cup W)$ such that the associated chain decomposition of $H$ is $(𝜀, η, ψ)$ -quasirandom. Moreover the number of bipartite graphs in the decomposition is bounded by a function of $𝜀$ and $η$ only, and the number of sets in the partitions of $X, Y, Z, W$ depends on $𝜀, η, ψ$ .