Click here to flash read.
The Kadison-Singer Conjecture, as proved by Marcus, Spielman, and Srivastava
(MSS) [Ann. Math. 182, 327-350 (2015)], has been informally thought of as a
strengthening of Batson, Spielman, and Srivastava's theorem that every
undirected graph has a linear-sized spectral sparsifier [SICOMP 41, 1704-1721
(2012)]. We formalize this intuition by using a corollary of the MSS result to
derive the existence of spectral sparsifiers with a number of edges linear in
its number of vertices for all undirected, weighted graphs. The proof consists
of two steps. First, following a suggestion of Srivastava [Asia Pac. Math.
Newsl. 3, 15-20 (2013)], we show the result in the special case of graphs with
bounded leverage scores by repeatedly applying the MSS corollary to partition
the graph, while maintaining an appropriate bound on the leverage scores of
each subgraph. Then, we extend to the general case by constructing a recursive
algorithm that repeatedly (i) divides edges with high leverage scores into
multiple parallel edges and (ii) uses the bounded leverage score case to
sparsify the resulting graph.
No creative common's license