This paper determines if certain families of Heisenberg graphs satisfy the Ramanujan bound. Proving conditions for Ramanujancy and non-Ramanujancy is desirable as a Ramanujan graph can represent efficient communication networks in that they minimize cost of wiring and maintenance, but maximize the number of connections from one vertex to another. We say that a graph is Ramanujan if it is k-regular, simple, connected, undirected and the largest nontrivial eigenvalue, λ, of its adjacency matrix satisfies the condition that |λ|≤sqrt(2k-1) where k is the degree of the graph. We find λ by using the exponential sum lemma and prove a general theorem for the non-Ramanujancy of these graphs under certain conditions. One of these conditions is satisfied by assuming the minimality of certain terms in the exponential sum. Then, without loss of generality, we isolate and prove the conditions for the occurrence of all lower-dimensional eigenvalues that exceed the Ramanujan bound. Also, graphical analysis of the spectra of Ramanujan graphs is performed and it is shown that, for a fixed number of elements in the symmetric set and as a prime p increases without bound, the distribution of the eigenvalues resembles the Sato-Tate semi-circle distribution.
with Vincent Dang and Yang Ge, Proceedings of the Thirty-Eighth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congr. Numer. 185 (2007), 111–126. MR2408803 05C50
