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} ,

^{T}L

_{G}x ≤ x

^{T}L

_{H}x ≤ (d + 1 + 2√d /d + 1 − 2√d) x

^{T}L

_{G}x

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.