On the second eigenvalue of random bipartite biregular graphs

We consider the spectral gap of a uniformly chosen random $(d_1,d_2)$-biregular bipartite graph $G$ with $\mathrm{\mid }{V}_1\mathrm{\mid }=n,\mathrm{\mid }{V}_2\mathrm{\mid }=m$, where $d_1,d_2$ could possibly grow with $n$ and $m$. Let $A$ be the adjacency matrix of $G$. Under the assumption that $d_1\ge d_2$ and $d_2=O(n^{2\mathrm{/}3}),$ we show that ${\lambda }_2(A)=O(\sqrt{d_1})$ with high probability. As a corollary, combining the results from Tikhomirov and Youssef (2019), we showed that the second singular value of a uniform random $d$-regular digraph is $O(\sqrt{d})$ for $1\le d\le n\mathrm{/}2$ with high probability. Assuming $d_2$ is fixed and $d_1=O(n^2)$, we further prove that for a random $(d_1,d_2)$-biregular bipartite graph, $\mathrm{\mid }{\lambda }_i^2(A)-d_1\mathrm{\mid }=O(\sqrt{d_1})$ for all $2\leq i\leq n+m-1$ with high probability. The proofs of the two results are based on the size biased coupling method introduced in Cook, Goldstein, and Johnson (2018) for random $d$-regular graphs and several new switching operations we defined for random bipartite biregular graphs.