2001 REU Project Report

Ramanujan Graphs (Led by Giuliana Davidoff).

The students were: Sylvia Carlisle (Carlton College), Brian Carty (Amherst College) Bejamin Chan (Rochester), Sawson Eskander (Mount Holyoke College), Matt Noonan (Hampshire College), Anne Short (Harvey Mudd College). Five of these students were supported by NSF funds and one by Mount Holyoke funds. The research this summer examined families of Ramanujan graphs, a class of optimally efficient graphs for the transmission of information. These graphs are characterized by the spectra associated to their adjacency matrices, and the only known constructions are limited to k-regular graphs for $k = p + 1$, $p^n + 1$, where p is a prime. Our problem this summer was to generalize these constructions to k= pq and, especially, to k = 2p, that is, to see if we might find a way of constructing expander graphs by gluing together two underlying graphs known to be Ramanujan. The numerical evidence suggests that these particular methods do yield expanders, but not necessarily Ramanujan graphs. To work on the project, students were required to learn about algebraic graph theory, to read and understand the results for known k, to study Eichler's work on general quaternion algebras and their maximal orders and Sarnak's book on applications of modular forms. In addition, they learned how to use new software for computational algebra and resolved various complexity issues associated to the numerical problem of calculating eigenvalues of graphs with many vertices. Finally, the group was able to extend Chiu's work to the three additional definite quaternion algebras with class number 1 that split at the prime p = 2.

The group's work was accepted for the undergraduate poster session at the joint meetings in San Diego in January, 2002, but because of scheduling conflicts, no member was available to attend.