Interlacing families. I: Bipartite Ramanujan graphs of all degrees

DOI10.4007/annals.2015.182.1.7zbMath1316.05066arXiv1304.4132OpenAlexW2095087473WikidataQ56553645 ScholiaQ56553645MaRDI QIDQ2352911

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

Publication date: 6 July 2015

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

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

zbMATH Keywords

Ramanujan graphs lifts of graphs matching polynomials of graphs

Mathematics Subject Classification ID

Graph polynomials (05C31)

Related Items

Impediments to diffusion in quantum graphs: Geometry-based upper bounds on the spectral gap, Improved bounds in Weaver's \(\operatorname{KS}_r\) conjecture for high rank positive semidefinite matrices, Finite free cumulants: Multiplicative convolutions, genus expansion and infinitesimal distributions, Gap sets for the spectra of cubic graphs, Spectra of infinite graphs via freeness with amalgamation, Combinatorics and preservation of conically stable polynomials, Complete signed graphs with largest maximum or smallest minimum eigenvalue, Spectrum of random d‐regular graphs up to the edge, Paradigms for Unconditional Pseudorandom Generators, On the second eigenvalue of random bipartite biregular graphs, Blowup polynomials and delta-matroids of graphs, The spectral property of hypergraph coverings, Trace formulas for magnetic Schrödinger operators on periodic graphs and their applications, Morse theory for discrete magnetic operators and nodal count distribution for graphs, Mixing in High-Dimensional Expanders, Frustration index and Cheeger inequalities for discrete and continuous magnetic Laplacians, Explicit Near-Ramanujan Graphs of Every Degree, What Do Networks and Elliptic Curves Have in Common?, Shift lifts preserving Ramanujan property, A class of highly symmetric graphs, symmetric cylindrical constructions and their spectra, Ramanujan complexes and golden gates in \(PU(3)\), Finite free convolutions of polynomials, Matching number, Hamiltonian graphs and magnetic Laplacian matrices, Quantum ergodicity for quantum graphs without back-scattering, Paving property for real stable polynomials and strongly Rayleigh processes, A rectangular additive convolution for polynomials, Interlacing families. III: Sharper restricted invertibility estimates, On the spectrum and linear programming bound for hypergraphs, Graphs, Vectors, and Matrices, The Kadison-Singer problem, Local expanders, Cutoff on all Ramanujan graphs, Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes, Inertia indices and eigenvalue inequalities for Hermitian matrices, Isoperimetric inequalities in simplicial complexes, Explicit expanding expanders, A Spectral Approach to Network Design, Interlacing Ehrhart polynomials of reflexive polytopes, Ramanujan coverings of graphs, Mean isoperimetry with control on outliers: exact and approximation algorithms, On regular hypergraphs of high girth, Polynomial representation of quantum entanglement, Local Kesten-McKay law for random regular graphs, Laplacian matching polynomial of graphs, Ramanujan graphs and exponential sums over function fields, Imaginary projections: complex versus real coefficients, Restricted Invertibility Revisited, Edge rigidity and universality of random regular graphs of intermediate degree, Dilations of operator-valued measures with bounded \(p\)-variations and framings on Banach spaces, Signatures, Lifts, and Eigenvalues of Graphs, Four deviations suffice for rank 1 matrices, Interlacing families and the Hermitian spectral norm of digraphs, Curvature and Higher Order Buser Inequalities for the Graph Connection Laplacian, Ramanujan complexes and high dimensional expanders, EPG-representations with Small Grid-Size, Approximating Nonnegative Polynomials via Spectral Sparsification, Graph covers with two new eigenvalues, Expander graphs -- both local and global, Formal Zeta function expansions and the frequency of Ramanujan graphs, The Ising partition function: zeros and deterministic approximation, On the order of regular graphs with fixed second largest eigenvalue, A connection between a question of Bermond and Bollobás and Ramanujan graphs, Expansion of random graphs: new proofs, new results, Explicit expanders of every degree and size, Improved bounds in Weaver and Feichtinger conjectures, On eigenvalues of random complexes, Explicit Bounds from the Alon–Boppana Theorem, Lifts, derandomization, and diameters of Schreier graphs of Mealy automata, A unified proof of interlacing properties of eigenvalues of totally positive matrices, Imaginary projections of polynomials, Deterministic Tensor Completion with Hypergraph Expanders, Conic stability of polynomials and positive maps, The convexification effect of Minkowski summation, An isoperimetric constant for signed graphs, The converse of Weyl's eigenvalue inequality, On loops intersecting at most once, Computational topology and the Unique Games Conjecture, A spectral version of the Moore problem for bipartite regular graphs, Cheeger constants, structural balance, and spectral clustering analysis for signed graphs, Open problems in the spectral theory of signed graphs, Size Ramsey number of bipartite graphs and bipartite Ramanujan graphs, Signed graphs with maximal index, Explicit Construction of Ramanujan Bigraphs, Fisher zeros and correlation decay in the Ising model, Recent progress in combinatorial random matrix theory, Ramanujan graphs and expander families constructed from \(p\)-ary bent functions, On the largest eigenvalue of a mixed graph with partial orientation, Recent progress on graphs with fixed smallest adjacency eigenvalue: a survey, A combinatorial proof of Bass's determinant formula for the zeta function of regular graphs, Maximizing the Order of a Regular Graph of Given Valency and Second Eigenvalue, Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids, Opinion Forming in Erdös-Rényi Random Graph and Expanders, Fisher Zeros and Correlation Decay in the Ising Model, On Deformations of Hyperbolic Varities, Unnamed Item, Subset selection for matrices with fixed blocks, Conic stability of polynomials, On Computationally Tractable Selection of Experiments in Measurement-Constrained Regression Models, The Ramanujan conjecture and its applications, From Ramanujan graphs to Ramanujan complexes, Generalizations of the matching polynomial to the multivariate independence polynomial, The separating semigroup of a real curve, On the location of zeros of the Laplacian matching polynomials of graphs, Atoms of the matching measure, Spectral aspects of symmetric matrix signings, A Performance Guarantee for Spectral Clustering, Covers, orientations and factors, Cutoff on hyperbolic surfaces, Upper and lower bounds for matrix discrepancy, Spectrahedrality of hyperbolicity cones of multivariate matching polynomials, Ramanujan graphs arising as weighted Galois covering graphs, Quantum ergodicity on large regular graphs, Median eigenvalues of bipartite graphs, A refined Gallai-Edmonds structure theorem for weighted matching polynomials, Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem, On cylindrical graph construction and its applications, The Kadison-Singer problem, New and explicit constructions of unbalanced Ramanujan bipartite graphs

Cites Work