Peter Sarnak (Courant-NYU / Princeton University ):
Ramanujan Graphs
Highly connected but sparse ("expanders") have proven to be
fundamental building blocks in many algorithms in computational
complexity theory. We review the definition(in terms of
eigenvalues of the adjacency matrix) and construction of Ramanujan
Graphs, these being optimal in this connection. We then discuss
recent developments related to the eigenvalues and random graphs
and matrices as well as higher dimensional Ramanujan Buildings.