= Solution
Uniform <expectations> require nonempty <finite sets>; assume this throughout the analytic argument. For <real-valued functions> on $X\times Y$, define the <box norm> by
$$
\boxed{\|f\|_{\square}=
\left(\mathbb E_{x_0,x_1\in X\atop y_0,y_1\in Y}
\prod_{i,j=0}^1f(x_i,y_j)\right)^{1/4}.}
$$
All four variables are sampled as <independent random variables> with replacement, so repeated coordinates are included. The defining fourth power equals
$$
\mathbb E_{y_0,y_1}\left(\mathbb E_xf(x,y_0)f(x,y_1)\right)^2\geq0.
$$
If it vanishes, every summand vanishes. In particular, the terms $y_0=y_1=y$ give $\mathbb E_x f(x,y)^2=0$ for each $y$, so $f=0$. <Absolute homogeneity of a norm> follows directly: $\|af\|_{\square}=|a|\|f\|_{\square}$.
For the <triangle inequality>, prove the mixed <box Cauchy-Schwarz inequality>. Write
$$
\Lambda(f_{00},f_{01},f_{10},f_{11})=
\mathbb E_{x_0,x_1,y_0,y_1}\prod_{i,j=0}^1f_{ij}(x_i,y_j).
$$
Separating the two $y$ averages and applying the <Cauchy-Schwarz inequality> in $(x_0,x_1)$ gives
$$
|\Lambda|\leq A(f_{00},f_{10})^{1/2}A(f_{01},f_{11})^{1/2},
\quad A(f,g)=\mathbb E_{x,x'}\left(\mathbb E_y f(x,y)g(x',y)\right)^2.
$$
Expanding the square and reversing the order of finite sums,
$$
A(f,g)=\mathbb E_{y,y'}
\left(\mathbb E_xf(x,y)f(x,y')\right)
\left(\mathbb E_xg(x,y)g(x,y')\right)
\leq\|f\|_{\square}^2\|g\|_{\square}^2,
$$
by a second <Cauchy-Schwarz inequality>. Thus $|\Lambda|\leq\prod_{i,j}\|f_{ij}\|_{\square}$. Expand $\Lambda(f+g,f+g,f+g,f+g)$ into its sixteen multilinear terms and apply this bound to each term. Their upper bounds sum to $(\|f\|_{\square}+\|g\|_{\square})^4$. Taking fourth roots yields the <triangle inequality>. Together with <definiteness of a norm> and <absolute homogeneity of a norm>, this proves \b[the <box norm> is a <norm>.] Complex <functions> require conjugates and are outside the printed real-valued convention.
For the <bilinear correlation bound for the box norm>, use the normalized <L2 norm>: let $B=\mathbb E_{x,y}f(x,y)u(x)v(y)$ and $\|u\|_2^2=\mathbb E_xu(x)^2$, $\|v\|_2^2=\mathbb E_yv(y)^2$. The <Cauchy-Schwarz inequality> in $y$ gives
$$
|B|^2\leq\|v\|_2^2\mathbb E_y\left(\mathbb E_x f(x,y)u(x)\right)^2.
$$
The remaining factor is $\mathbb E_{x,x'}u(x)u(x')\mathbb E_y f(x,y)f(x',y)$. By the <Cauchy-Schwarz inequality> in $(x,x')$, its magnitude is at most
$$
\left(\mathbb E_{x,x'}u(x)^2u(x')^2\right)^{1/2}
\left(\mathbb E_{x,x'}\left(\mathbb E_yf(x,y)f(x',y)\right)^2\right)^{1/2}
=\|u\|_2^2\|f\|_{\square}^2.
$$
Taking square roots proves
$$
\boxed{|\mathbb E_{x,y}f(x,y)u(x)v(y)|\leq\|f\|_{\square}\|u\|_2\|v\|_2.}
$$
For the <tripartite graph>, assume its parts are nonempty and write $g_{XY},g_{YZ},g_{XZ}$ for its adjacency <indicator functions>. Let $f=g_{XY}-\alpha$, so $\|f\|_{\square}\leq c$. The normalized <triangle count> is
$$
\tau=\mathbb E_{x,y,z}(\alpha+f(x,y))g_{YZ}(y,z)g_{XZ}(x,z).
$$
The constant-degree hypothesis is exactly $\mathbb E_y g_{YZ}(y,z)=\beta$ for each $z$. Therefore the contribution of the constant $\alpha$ is
$$
\alpha\mathbb E_z\left(\mathbb E_y g_{YZ}(y,z)\right)
\left(\mathbb E_x g_{XZ}(x,z)\right)=\alpha\beta\gamma.
$$
For fixed $z$, apply the <bilinear correlation bound for the box norm> with $u_z(x)=g_{XZ}(x,z)$ and $v_z(y)=g_{YZ}(y,z)$. Since these are <indicator functions>, $\|v_z\|_2^2=\beta$ and $\|u_z\|_2^2=d_X(z)$, the fraction of $X$ adjacent to $z$. Averaging and applying the <Cauchy-Schwarz inequality> in $z$ gives the sharper <triangle counting with one box-uniform pair and constant opposite degree> estimate
$$
|\tau-\alpha\beta\gamma|
\leq c\sqrt\beta\,\mathbb E_z\sqrt{d_X(z)}
\leq c\sqrt{\beta\,\mathbb E_zd_X(z)}
=c\sqrt{\beta\gamma}\leq c.
$$
Multiplying by $|X||Y||Z|$ yields
$$
\boxed{\bigl|T(G)-\alpha\beta\gamma\,|X|\,|Y|\,|Z|\bigr|
\leq c\sqrt{\beta\gamma}\,|X||Y||Z|
\leq3c|X||Y||Z|.}
$$
The middle bound also handles $\beta=0$ or $\gamma=0$, when the <triangle count> is zero.
To connect explicitly with the suggested expansion, put $f_2=g_{YZ}-\beta$, $f_3=g_{XZ}-\gamma$. Both have overall mean zero, and $\mathbb E_y f_2(y,z)=0$ for every $z$. Consequently $\mathbb E_{x,y,z}f_2(y,z)f_3(x,z)=0$; all terms with constant $\alpha$ reduce to $\alpha\beta\gamma$. The terms containing $f$ combine into the single error just estimated. This is where the exact degree assumption is used. If any part is empty the <triangle count> itself is zero, but the printed uniform <expectations> and <edge density of a bipartite graph> values would be undefined; the nonempty-parts convention must therefore be stated rather than dividing by zero.
Back to article page
