CSDM - Twice-Ramanujan Sparsifiers

Nikhil Srivastava
Yake University
September 21, 2009

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 ,