Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 111 / 2 / ii

Let ${\sigma }_1=\gamma ,{\sigma }_2,\dots$ 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^{\ast }{)}^2$ proves the box norm singular-value identityTherefore (ii) immediately implieswhich is (iii).

Conversely, the square of the Hilbert-Schmidt norm of this operator issince a graph indicator function takes values zero and one. Under (iii), every ${\sigma }_j$ with $j\ge 2$ is at most $c_3$, soThus (iii)$\Rightarrow$(ii) with $\boxed{c_2=c_3^2/4}$. This bound also covers the empty and complete bipartite graphs.