Spectral gap in random bipartite biregular graphs and applications

Abstract

We prove an analogue of Alon's spectral gap conjecture for random bipartite, biregular graphs. We use the Ihara-Bass formula to connect the non-backtracking spectrum to that of the adjacency matrix, employing the moment method to show there exists a spectral gap for the non-backtracking matrix. A byproduct of our main theorem is that random rectangular zero-one matrices with fixed row and column sums are full-rank with high probability. Finally, we illustrate applications to community detection, coding theory, and deterministic matrix completion.

arXiv commentSmall changes to the paper

References in corpus (7)

• Community detection in graphs
• Cutoff phenomena for random walks on random regular graphs
• Equitable random graphs
• A class of network models recoverable by spectral clustering
• Invertibility of adjacency matrices for random d-regular directed graphs
• Spectral partitioning in equitable graphs
• The Marčenko-Pastur law for sparse random bipartite biregular graphs

Cited by in corpus (9)

• A Sparse Model of Quantum Holography
• Ramanujan Graphs and Digraphs
• Ramanujan complexes and Golden Gates in PU(3)
• Deterministic tensor completion with hypergraph expanders
• On the second eigenvalue of random bipartite biregular graphs
• Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
• On the eigenvalues of Erdos-Renyi random bipartite graphs
• Uniqueness of communities in regular stochastic block models
• Existence and polynomial time construction of biregular, bipartite Ramanujan graphs of all degrees