Ramanujan Graphs and the Solution of the Kadison-Singer Problem

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.

arXiv commentA version of this paper will appear in the proceedings of the 2014 International Congress of Mathematicians

References in corpus (3)

• Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees
• Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem
• Sparse quadratic forms and their geometric applications (after Batson, Spielman and Srivastava)

Cited by in corpus (9)

• Optimal Regularization Can Mitigate Double Descent
• Cheeger constants, structural balance, and spectral clustering analysis for signed graphs
• Boosted optimal weighted least-squares
• Signatures, lifts, and eigenvalues of graphs
• Bohrification: From classical concepts to commutative algebras
• The solution to the Kadison--Singer Problem: yet another presentation
• Linear-Sized Spectral Sparsifiers and the Kadison-Singer Problem
• Convex Approximation and the Hilbert Geometry
• An analytical Lieb-Sokal lemma