A generalized Alon-Boppana bound and weak Ramanujan graphs (Q726663): Difference between revisions

Summary: A basic eigenvalue bound due to Alon and Boppana [\textit{N. Alon}, Combinatorica 6, 83--96 (1986; Zbl 0661.05053)] 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 \leqslant 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.