= Spectral discrepancy bound for a biregular graph
{title2=$|e(A,B)-\delta|A||B||\leq s\sqrt{|A||B|}$}
Let $H=M-\delta J$ be the centered <biadjacency matrix> of an equal-part <biregular graph>, and put $s=\|H\|_{\mathrm{op}}$. For subsets $A,B$ of the two parts, their edge discrepancy is $\mathbf1_A^{\mathsf T}H\mathbf1_B$. The <Cauchy-Schwarz inequality> proves the displayed bound. If the part size is $n$, centering the two <indicator vectors> improves it to $s n\sqrt{\alpha(1-\alpha)\beta(1-\beta)}$. The <centered four-cycle identity for a biregular graph> shows that $t_4(G)\leq\delta^4(1+c^4)$ implies $s\leq c\delta n$ for $c\geq0$.
Back to article page
