Spectral gap in random bipartite biregular graphs and applications

DOI10.1017/S0963548321000249MaRDI QIDQ5886318

Ioana Dumitriu, Kameron Decker Harris, Gerandy Brito

Publication date: 31 March 2023

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1804.07808

zbMATH Keywords

bipartite; random graphs; spectral gap; expanders

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

60B20: Random matrices (probabilistic aspects)

60C05: Combinatorial probability

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

05C48: Expander graphs

Related Items

Detection thresholds in very sparse matrix completion, Global eigenvalue fluctuations of random biregular bipartite graphs, On the second eigenvalue of random bipartite biregular graphs

Uses Software

• Jellyfish

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Adjacency matrices of random digraphs: singularity and anti-concentration
• Equitable decompositions of graphs with symmetries
• Anti-concentration property for random digraphs and invertibility of their adjacency matrices
• Complexity measures of sign matrices
• Cutoff phenomena for random walks on random regular graphs
• Walk generating functions and spectral measures of infinite graphs
• Eigenvalues and expanders
• The asymptotic connectivity of labelled regular graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• The asymptotic number of non-negative integer matrices with given row and column sums
• The asymptotic number of labeled graphs with given degree sequences
• Relative expanders or weakly relatively Ramanujan graphs.
• On Tanner codes: Minimum distance and decoding
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• The semicircle law for semiregular bipartite graphs
• Spectra of regular graphs and hypergraphs and orthogonal polynomials
• Spectra of hypergraphs and applications
• Large incidence-free sets in geometries
• The spectral gap of sparse random digraphs
• Spectral density of equitable core-periphery graphs
• Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
• Parallel stochastic gradient algorithms for large-scale matrix completion
• The Marčenko-Pastur law for sparse random bipartite biregular graphs
• Deterministic algorithms for matrix completion
• Resolvent of large random graphs
• A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
• Modern Coding Theory
• Expander graphs and their applications
• A proof of Alon’s second eigenvalue conjecture and related problems
• The rank of random graphs
• A recursive approach to low complexity codes
• Recovery and Rigidity in a Regular Stochastic Block Model
• THE IHARA-SELBERG ZETA FUNCTION OF A TREE LATTICE
• The threshold for SDP-refutation of random regular NAE-3SAT
• The non-backtracking spectrum of the universal cover of a graph
• Community detection thresholds and the weak Ramanujan property
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Learning Theory
• Networks