Using Group Theory and Graph Theory to Build Fast CommunicationsNetworks: A Brief Introduction to Expanders and Ramanujan Graph

12/02/2008 - 12:15pm
12/02/2008 - 1:10pm
Mike Krebs (California State University Los Angeles)

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.

ML 211