REU Number Theory Group

K-Regular Expander Graphs (Led by Giuliana Davidoff).

Summer 2004

My group this year was working on properties of k-regular expander graphs and, in particular, looking at connections between the expansion constant, which measures the efficiency of a graph as a communication network, and the spectral gap, k - µ1, where µ1 is the second largest eigenvalue. The first quantity, which is bounded above and below by simple functions of the spectral gap, is typically difficult to compute. On the other hand, µ1, at least in graphs given by quaternionic constructions, is much simpler to estimate or bound, so the spectral gap is simpler to handle computationally. Graphs with optimally large spectral gaps are called Ramanujan graphs, and, thus far, no example has been found of a non-Ramanujan graph with a better expansion constant than some known Ramanujan graphs. Our goal this past summer was to produce such an example. By using positive definite quaternion algebras with class number one, other that the classical Hamiltonian example, and then varying the generating sets, we obtained a collection of (p+1)-regular graphs that seems to include rich subsets of both Ramanujan and non-Ramanujan examples. Though we were not able to resolve the computational problems involved, we do still hope to find among our collection of graphs at least one that might be the example we were seeking.

The members of the Number Theory REU group in 2004 were:

  • Matt Wechter, Amherst College
  • Lauren Shareshian, New York University
  • Aubrey DaCunha, Iowa State University
  • Matthew Goldfield, Carnegie Mellon
  • Richard Gottesman, Brown