An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification
Nikhil Srivastava, Luca Trevisan · Society for Industrial and Applied Mathematics eBooks · 2018
We prove the following Alon-Boppana type theorem for general (not necessarily regular) weighted graphs: if G is an n-node weighted undirected graph of average combinatorial degree d (that is, G has dn/2 edges) and girth g > 2d1/8 + 1, and if λ1 ≤ λ2 ≤ · · · λn are the eigenvalues of the (non-normalized) Laplacian of G, then (The Alon-Boppana theorem implies that if G is unweighted and d-regular, then if the diameter is at least d1.5.) Our result implies a lower bound for spectral sparsifiers. A graph H is a spectral є-sparsifier of a graph G if where L(G) is the Laplacian matrix of G and L(H) is the Laplacian matrix of H. Batson, Spielman and Srivastava proved that for every G there is an є-sparsifier H of average degree d where and the edges of H are a (weighted) subset of the edges of G. Batson, Spielman and Srivastava also show that the bound on є cannot be reduced below when G is a clique; our Alon-Boppana-type result implies that є cannot be reduced below when G comes from a family of expanders of super-constant degree and superconstant girth. The method of Batson, Spielman and Srivastava proves a more general result, about sparsifying sums of rank-one matrices, and their method applies to an “online” setting. We show that for the online matrix setting the bound is tight, up to lower order terms.