A Generalized Alon-Boppana Bound and Weak Ramanujan Graphs

Fan Chung

Abstract


A basic eigenvalue bound due to Alon and Boppana holds only for regular graphs. In this paper we give a generalized Alon-Boppana bound for eigenvalues of graphs that are not required to be regular. We show that a graph $G$ with diameter $k$ and vertex set $V$, the smallest nontrivial eigenvalue $\lambda_1$ of the normalized Laplacian $\mathcal L$ satisfies
$$
\lambda_1 \leq 1-\sigma \big(1- \frac c {k} \big)
$$ for some constant $c$ where $\sigma = 2\sum_v d_v \sqrt{d_v-1}/\sum_v d_v^2 $ and $d_v$ denotes the degree of the vertex $v$.

We consider weak Ramanujan graphs defined as graphs satisfying $ \lambda_1 \geq 1-\sigma$. We examine the vertex expansion and edge expansion of weak Ramanujan graphs and then use the expansion properties among other methods to derive the above Alon-Boppana bound.

 

A corrigendum was added on the 3rd of November 2017.


Keywords


Eigenvalues, Laplacian, Expander, Ramanujan graphs

Full Text:

PDF