On the second eigenvalue of random bipartite biregular graphs

Abstract

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\ge d_2$ and $d_2=O(n^{2/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/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, $|{\lambda }_i^2(A)-d_1|=O(\sqrt{d_1})$ for all $2\le i\le 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.

arXiv comment23 pages, 3 figures

References in corpus (19)

• Local Kesten--McKay law for random regular graphs
• Local semicircle law for random regular graphs
• Bulk eigenvalue statistics for random regular graphs
• Size biased couplings and the spectral gap for random regular graphs
• Functional limit theorems for random regular graphs
• Edge rigidity and universality of random regular graphs of intermediate degree
• Spectral gaps of random graphs and applications
• ${\ell }_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
• Spectral gap in random bipartite biregular graphs and applications
• Exchangeable pairs, switchings, and random regular graphs
• The smallest singular value of a shifted $d$-regular random square matrix
• Sparse random tensors: Concentration, regularization and applications
• Matrix Completion from $O(n)$ Samples in Linear Time
• Spectrum of Random $d$-regular Graphs Up to the Edge
• Global eigenvalue fluctuations of random biregular bipartite graphs
• Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs
• Local Marchenko-Pastur Law for Random Bipartite Graphs
• Concentration of measures via size biased couplings
• Bulk Eigenvalue Correlation Statistics of Random Biregular Bipartite Graphs

Cited by in corpus (3)

• On the eigenvalues of Erdos-Renyi random bipartite graphs
• Extreme singular values of inhomogeneous sparse random rectangular matrices
• Concentration inequalities from monotone couplings for graphs, walks, trees and branching processes