Spectral gap in random bipartite biregular graphs and applications
Gerandy Brito, Ioana Dumitriu, Kameron Decker Harris
Abstract
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 by-product 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.
Topics & Concepts
Bipartite graphAdjacency matrixMathematicsCombinatoricsBacktrackingRandom matrixDiscrete mathematicsConjectureMatrix (chemical analysis)Eigenvalues and eigenvectorsAlgorithmGraphPhysicsComposite materialMaterials scienceQuantum mechanicsRandom Matrices and ApplicationsError Correcting Code TechniquesGraph theory and applications