Spectral gap in random bipartite biregular graphs and applications

DOI10.1017/S0963548321000249OpenAlexW3186482404MaRDI 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

bipartiterandom graphsspectral gapexpanders

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Combinatorial probability (60C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Expander graphs (05C48)

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, Scalable Bayesian computation for crossed and nested hierarchical models

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