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 LG and LH 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
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.