On the Ramanujancy of Heisenberg Graphs over Rings of degree 6 or more

摘要

The purpose of this paper is to determine 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 non-trivial eigenvalue, λ, of its adjacency matrix satisfies the condition that |λ| ≤ 2(k-1)~(1/2) 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 occurance 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.