2017/07/20 by Srivastava, Nikhil, Trevisan, Luca · 1 citation
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1707.06364
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 \frac λnλ2 ≥ 1 + \frac 4√ d - O ( \frac 1d\frac 58 ) (The Alon-Boppana theorem implies that if G is unweighted and d-regular, then \frac λnλ2 ≥ 1 + \frac 4√ d - O( \frac 1 d ) 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 L(G) \preceq L(H) \preceq (1+ε) L(G) 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 ε≈ \frac 4√ 2√ d 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 ≈ \frac 2√ d when G is a clique; our Alon-Boppana-type result implies that ε cannot be reduced below ≈ \frac 4√ d when G comes from a family of expanders of super-constant degree and super-constant 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 4√ 2 / √ d bound is tight, up to lower order terms.