= Solution
Use uniform <expectations> on the two nonempty parts, and equip their function spaces with the <inner product> $\langle u,v\rangle=\mathbb E\overline u v$. Let $H=G-\gamma$ and
$$
(T_Hv)(x)=\mathbb E_yH(x,y)v(y).
$$
Since the <bipartite graph> is a <biregular graph>, both row and column averages of $H$ vanish. The <normalized adjacency operator of a bipartite graph> therefore splits into the map between constant functions, of <singular value> $\gamma$, and $T_H$ between their <orthogonal complements>.
There is no <singular value> larger than $\gamma$. Indeed, for $\gamma>0$, the <Cauchy-Schwarz inequality> gives
$$
|\mathbb E_yG(x,y)v(y)|^2
\leq\gamma\mathbb E_yG(x,y)|v(y)|^2.
$$
Averaging in $x$ uses the constant column degree and gives $\|\theta_Gv\|_2\leq\gamma\|v\|_2$. For $\gamma=0$ every operator is zero. Thus the second <singular value> is
$$
s=\|T_H\|_{\mathrm{op}}.
$$
If one part has a single vertex, missing <singular values> are interpreted as zero; the <biregular graph> then has $H=0$.
The discrepancy in (i) is exactly $\mathbb E H1_A1_B$. Its supremum over $A,B$ is the <cut norm> $\delta=\|H\|_{\mathrm{cut}}$. To pass from this bound to arbitrary bounded <real-valued functions>, use the positive and negative parts and the identity $u_+(x)=\int_0^M1_{\{u(x)>t\}}\,dt$ for $|u|\leq M$. Applying this separately to both factors gives
$$
|\mathbb E_{x,y}H(x,y)u(x)v(y)|\leq4\delta MN
\quad\text{if }|u|\leq M,\ |v|\leq N.
$$
Here $N$ is a bound on $v$, unrelated to any <cardinality>.
If $s>0$, take real unit <left singular vector> $u$ and <right singular vector> $v$ with $T_Hv=su$ and $T_H^*u=sv$. The <Cauchy-Schwarz inequality> and $|H|\leq1$ imply $\|u\|_\infty,\|v\|_\infty\leq1/s$. Hence
$$
s=\mathbb E Huv\leq\frac{4\delta}{s^2},
\qquad\boxed{s\leq(4c_1)^{1/3}}.
$$
This proves (i)$\Rightarrow$(iii), with a constant independent of both part sizes. The case $s=0$ satisfies the same conclusion immediately.
Back to article page
