11 Feb 2017

Spectra of Heisenberg Graphs over Finite Rings

The aim of this paper is to study spectra of Cayley graphs attached to finite Heisenberg groups using histograms and Hofstadter butterfly figures. The Heisenberg group H(R) over a ring R consists of upper triangular 3×3 matrices with entries in R and ones on the diagonal.

Heisenberg groups over finite fields have provided a tool in the search for random number generators (see Maria Zack) as well as the search for Ramanujan graphs (see Perla Myers). Other references are P. Diaconis and L. Saloff-Coste [5] and Terras [24]. As shown in the last reference, the size of the second largest (in absolute value) eigenvalue of the adjacency matrix governs the speed of convergence to uniform for the standard random walk on a connected regular graph. Ramanujan graphs have the best possible eigenvalue bound for connected regular graphs of fixed degree in an infinite sequence of graphs with number of vertices going to infinity. For such graphs, the random walker gets lost as quickly as possible. Equivalently, this says that such graphs can be used to build efficient communication networks.

with M. Martinez, A. Medrano, M. Minei, H.M. Stark, and A. TerrasDynamical systems and differential equations (Wilmington, NC, 2002). Discrete Contin. Dyn. Syst. 2003, suppl., 213–222. MR2018119 11T60 (05C25)

Comments Off on Spectra of Heisenberg Graphs over Finite Rings