= Solution
Let $\sigma_1=\gamma,\sigma_2,\ldots$ be the <singular values> of the <normalized adjacency operator of a bipartite graph>, with the uniform <inner products> used above. Its ordinary matrix in an <orthonormal basis> on each side is $G/\sqrt{|X||Y|}$. Expanding the <trace> of $(\theta_G\theta_G^*)^2$ proves the <box norm singular-value identity>
$$
\|G\|_\square^4
=\mathbb E_{x,x',y,y'}G(x,y)G(x',y)G(x',y')G(x,y')
=\sum_j\sigma_j^4
=\gamma^4+\sum_{j\geq2}\sigma_j^4.
$$
Therefore (ii) immediately implies
$$
\boxed{s\leq c_2^{1/4}},
$$
which is (iii).
Conversely, the square of the <Hilbert-Schmidt norm> of this operator is
$$
\sum_j\sigma_j^2=\mathbb E_{x,y}G(x,y)^2=\gamma,
$$
since a <graph> <indicator function> takes values zero and one. Under (iii), every $\sigma_j$ with $j\geq2$ is at most $c_3$, so
$$
\sum_{j\geq2}\sigma_j^4
\leq c_3^2\sum_{j\geq2}\sigma_j^2
=c_3^2(\gamma-\gamma^2)
\leq\frac{c_3^2}{4}.
$$
Thus (iii)$\Rightarrow$(ii) with $\boxed{c_2=c_3^2/4}$. This bound also covers the empty and complete <bipartite graphs>.
Back to article page
