Claremont Center for the Mathematical Sciences

Think of a graph as a communications network. Putting in edges (e.g., fiber optic cables, telephone lines) is expensive, so we wish to limit the number of edges in the graph. At the same time, we would like messages in the graph to spread as rapidly as possible. We will see that the speed of communication is closely related to the eigenvalues of the graph's adjacency matrix. Essentially, the smaller the eigenvalues are, the faster messages spread. It turns out that there is a bound, due to Serre and others, on how small the eigenvalues can be. This gives us a rough sense of what it means for graphs to represent "optimal" communications networks; we call these Ramanujan graphs. Families of k-regular Ramanujan graphs have been constructed in this manner by Sarnak and others whenever k minus one equals a power of a prime number. No one knows whether families of k-regular Ramanujan graphs exist for all k.