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

Nikhil Srivastava, Luca Trevisan

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 deg…