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 | V 1 | = n , | V 2 | = 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 ≥ d 2 and d 2 = O (n 2 / 3) , we show that λ 2 (A) = O (d 1) with high probability. As a corollary, combining the results from (Tikhomirov and Yousse in Ann Probab 47(1):362–419, 2019), we show that the second singular value of a uniform random d-regular digraph is O (d) for 1 ≤ d ≤ n / 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, | λ i 2 (A) - d 1 | = O (d 1) for all 2 ≤ i ≤ n + m - 1 with high probability. The proofs of the two results are based on the size biased coupling method introduced in Cook et al. (Ann Probab 46(1):72–125, 2018) for random d-regular graphs and several new switching operations we define for random bipartite biregular graphs. [ABSTRACT FROM AUTHOR]