Families of Ramanujan Graphs and Quaternion Algebras

摘要

Expander graphs are graphs in which the neighbors of any given "not too large" set of vertices X form a large set relative to the size of X - rumors tend to spread very fast. Among those, the Ramanujan graphs are extremal in their expansion properties. To be precise, the eigenvalues of the adjacency matrix have an extremal property that guarantees good expansion properties. Expanders, and hence Ra-manujan graphs, have many applications, practical and theoretical, to computer science, coding theory, cryptography and network construction, besides numerous purely mathematical applications. Some applications are briefly indicated in the last section of this paper; for a thorough overview see [14, 38] and the references therein.