Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes

DOI10.1137/16M106176XzbMath1409.05185arXiv1505.08010OpenAlexW2904639156WikidataQ128724959 ScholiaQ128724959MaRDI QIDQ4562281

Nikhil Srivastava, Adam W. Marcus, Daniel A. Spielman

Publication date: 19 December 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

random matricesrandom graphsfree probabilityinterlacingexpander graphs

Mathematics Subject Classification ID

Graph polynomials (05C31) Random graphs (graph-theoretic aspects) (05C80)

Related Items

Finite free convolutions of polynomials, A Determinantal Identity for the Permanent of a Rank 2 Matrix, Inertia indices and eigenvalue inequalities for Hermitian matrices, Mean isoperimetry with control on outliers: exact and approximation algorithms, Improved bounds in Weaver's \(\operatorname{KS}_r\) conjecture for high rank positive semidefinite matrices, Explicit construction of \(q+1\) regular local Ramanujan graphs, for all prime-powers \(q\), Amalgamation of real zero polynomials, Edge rigidity and universality of random regular graphs of intermediate degree, Size Ramsey number of bipartite graphs and bipartite Ramanujan graphs, Subset selection for matrices with fixed blocks, Explicit Near-Ramanujan Graphs of Every Degree, Unnamed Item, New and explicit constructions of unbalanced Ramanujan bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the zeros of convex combinations of polynomials
• The roots of the independence polynomial of a clawfree graph
• Lifts, discrepancy and nearly optimal spectral gap
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Ramanujan graphs
• The expected eigenvalue distribution of a large regular graph
• On the second eigenvalue of a graph
• Obreschkoff's theorem revisited: What convex sets are contained in the set of hyperbolic polynomials?
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
• Lectures on the Combinatorics of Free Probability
• Expander graphs and their applications
• A proof of Alon’s second eigenvalue conjecture and related problems
• An Introduction to Random Matrices
• Twice-Ramanujan Sparsifiers
• Ramanujan coverings of graphs