A lower bound on the spectral radius of the universal cover of a graph
type: Item
instance of: scholarly article
title: A lower bound on the spectral radius of the universal cover of a graph
zbMATH Open document ID: 1063.05091
author: Shlomo Hoory
published in: Journal of Combinatorial Theory. Series B
publication date: 2005-02-09T00:00:00Z
review text: 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}. \]
reviewed by: Dragan Stevanović
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 2132706
zbMATH Keywords: eigenvalues
zbMATH Keywords: average degree
MaRDI profile type: Publication
full work available at URL: j.jctb.2004.06.001
OpenAlex ID: W2024330321
cites work: The Moore bound for irregular graphs
cites work: Some geometric aspects of graphs and their eigenfunctions
cites work: Walk generating functions and spectral measures of infinite graphs
cites work: The size of bipartite graphs with a given girth
cites work: Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
cites work: Ramanujan graphs
cites work: Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
cites work: Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
cites work: On the second eigenvalue of a graph
DOI: 10.1016/J.JCTB.2004.06.001
description: scientific article; zbMATH DE number 2132706