CSDM - Twice-Ramanujan Sparsifiers

We prove that every graph has a spectral sparsifier with a number of edges linear in its
number of vertices. As linear-sized spectral sparsifiers of complete graphs are expanders, our
sparsifiers of arbitrary graphs can be viewed as generalizations of expander graphs.
In particular, we prove that for every d > 1 and every undirected, weighted graph G =
(V,E,w) on n vertices, there exists a weighted graph H = (V, F, ~w) with at most dn edges
such that for every x ∈ ℜ^V ,

where L_G and L_H are the Laplacian matrices of G and H, respectively. Thus, H approximates
G spectrally at least as well as a Ramanujan expander with dn/2 edges approximates the
complete graph.
We give an elementary deterministic polynomial time algorithm for constructing H. We
briefly describe connections between our work, Bourgain and Tzafriri’s Restricted Invertibility
Theorem, and the Kadison-Singer Conjecture in analysis.
Joint work with Josh Batson and Dan Spielman.