An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification

zbMATH Open1403.05057arXiv1707.06364MaRDI QIDQ4607973FDOQ4607973

Authors: Nikhil Srivastava, Luca Trevisan 

Publication date: 15 March 2018

Abstract: 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>2d^{1/8}+1$, and if $lambd{a}_{1}leqlambd{a}_{2}leqcdotslambd{a}_n$ are the eigenvalues of the (non-normalized) Laplacian of $G$, then [ frac {lambda_n}{lambda_2} geq 1 + frac 4{sqrt d} - O left( frac 1{d^{frac 58} } ight) ] (The Alon-Boppana theorem implies that if $G$ is unweighted and $d$-regular, then $fraclambd{a}_{n}lambd{a}_{2}geq1+frac4sqrtd-Oleft(frac1dight)$ if the diameter is at least $d^{1.5}$.) Our result implies a lower bound for spectral sparsifiers. A graph $H$ is a spectral $epsilon$-sparsifier of a graph $G$ if [ L(G) preceq L(H) preceq (1+epsilon) 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 $epsilon$-sparsifier $H$ of average degree $d$ where $epsilonapproxfrac4sqrt2sqrtd$ and the edges of $H$ are a (weighted) subset of the edges of $G$. Batson, Spielman and Srivastava also show that the bound on $epsilon$ cannot be reduced below $approxfrac2sqrtd$ when $G$ is a clique; our Alon-Boppana-type result implies that $epsilon$ cannot be reduced below $approxfrac4sqrtd$ 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 $4sqrt2/sqrtd$ bound is tight, up to lower order terms.

Full work available at URL: https://arxiv.org/abs/1707.06364

Recommendations

• Lower bounds on the (Laplacian) spectral radius of weighted graphs
• Towards tight bounds for spectral sparsification of hypergraphs
• A sharp upper bound on the spectral radius of weighted graphs
• An upper bound on the spectral radius of weighted graphs
• On sparse spanners of weighted graphs
• Spectral sparsification of graphs
• An approach to bounding the spectral radius of a weighted digraph
• The new upper bounds on the spectral radius of weighted graphs
• A note on upper bounds for the spectral radius of weighted graphs
• A bound on the pathwidth of sparse graphs with applications to exact algorithms

zbMATH Keywords

Alon-Boppana type theoremspectral \(\varepsilon\)-sparsifier

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Signed and weighted graphs (05C22) Enumeration in graph theory (05C30)

Cited In (6)

• On weighted spectral radius of unraveled balls and normalized Laplacian eigenvalues
• Proportional volume sampling and approximation algorithms for \(A\)-optimal design
• Alon-Boppana-type bounds for weighted graphs
• The weighted spectrum of the universal cover and an Alon-Boppana result for the normalized Laplacian
• On spectral radii of unraveled balls
• Weighted expanders and the anisotropic Alon-Boppana theorem

This page was built for publication: An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4607973)