A lower bound on the spectral radius of the universal cover of a graph (Q707021): Difference between revisions

For a connected graph \(G\) of size \(n\), let \(\rho(G)\) be the largest eigenvalue of its adjacency matrix, and let \(\lambda(G)\) be the maximum of absolute values of the remaining eigenvalues. A well-known result of Alon and Boppana states that for any sequence of \(d\)-regular graphs \(G_i\) of diameter \(\mapsto\infty\), \[ \liminf_{i\mapsto\infty}\lambda(G_i)\geq2\sqrt{d-1}, \] and a \(d\)-regular graph \(G\) is said to be a Ramanujan graph if it satisfies \(\lambda(G)\leq 2\sqrt{d-1}\). Here, the author notes that the universal cover \(\widetilde{G}\) of a \(d\)-regular graph \(G\) is the \(d\)-regular infinite tree with \(\rho(\widetilde{G})=2\sqrt{d-1}\). A theorem due to \textit{Y.~Greenberg} from his Ph.D. thesis [Hebrew University of Jerusalem, 1995 (in Herbew)] states that if \(G_i\) is a family of graphs of size \(\mapsto\infty\), covered by the same universal cover \(\widetilde{G}\), then \[ \liminf_{i\mapsto\infty}\lambda(G_i)\geq\rho(\widetilde{G}), \] which motivated the author to suggest the following generalization to non-regular graphs: a graph is a Ramanujan graph if it satisfies \(\lambda(G)\leq\rho(\widetilde{G})\). The main results of the paper are: Theorem 1. For any size \(n\) graph \(G\) with the degree sequence \(d_1,\dots,d_n\) and minimal degree at least 2 we have \(\rho(\tilde{G})\geq 2\sqrt{\Lambda}\), where \[ \Lambda=\prod_{i=1}^n (d_i-1)^{d_i/\sum_{i=1}^n d_j}. \] Theorem 3. Let \(G_i\) be a sequence of graphs such that \(G_i\) has the property that the average degree of \(G_i\) after deleting any radius \(r_i\) ball is at least \(d\geq 2\), where \(r_i\mapsto\infty\). Then \[ \liminf_{i\mapsto\infty}\lambda(G_i)\geq 2\sqrt{d-1}. \]