|
Abstract:
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.
|