Ramanujan graphs and the solution of the Kadison-Singer problem

MaRDI QIDQ5371303zbMATH OpenFDO

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

Publication date 25 October 2017

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

zbMATH Keywords

restricted invertibilityKadison-SingerRamanujan graphsinterlacing polynomialsmixed discriminantsmixed characteristic polynomials

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) General theory of (C^*)-algebras (46L05) Real polynomials: location of zeros (26C10)

Abstract: We survey the techniques used in our recent resolution of the Kadison-Singer problem and proof of existence of Ramanujan Graphs of every degree: mixed characteristic polynomials and the method of interlacing families of polynomials. To demonstrate the method of interlacing families of polynomials, we give a simple proof of Bourgain and Tzafriri's restricted invertibility principle in the isotropic case.

Recommendations

• Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
• Consequences of the Marcus/Spielman/Srivastava solution of the Kadison-Singer problem
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• The solution of the Kadison-Singer problem
• The Kadison-Singer problem

Cited in

(19)

• scientific article; zbMATH DE number 653215 (Why is no real title available?)
• The legacy of Jean Bourgain in geometric functional analysis
• Anderson-Bernoulli localization at large disorder on the 2D lattice
• Boosted optimal weighted least-squares
• Signatures, lifts, and eigenvalues of graphs
• Spaces of Lorentzian and real stable polynomials are Euclidean balls
• Full spark frames in the orbit of a representation
• Detecting Fourier subspaces
• Graphs, vectors, and matrices
• Interlacing families. III: Sharper restricted invertibility estimates
• scientific article; zbMATH DE number 3235079 (Why is no real title available?)
• Lower bounds for the smallest singular value of structured random matrices
• Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
• Restricted invertibility revisited
• Approximating the largest root and applications to interlacing families
• Interlacing families. IV: Bipartite Ramanujan graphs of all sizes
• Cheeger constants, structural balance, and spectral clustering analysis for signed graphs
• The solution of the Kadison-Singer problem
• On the Aldous-Caputo spectral gap conjecture for hypergraphs

This page was built for publication: Ramanujan graphs and the solution of the Kadison-Singer problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5371303)