|Discrete Mathematics and Optimization Seminar
Monday December 4th at 4.30pm
Title. Ramanujan graphs: a motivated introduction.
Ramanujan graphs are among the optimal expander graphs: sets
expand very fast in those graphs under the operation of adjoining their
neighbors. The terminology and non-trivial constructions originate in
the theory of modular forms, which is part of number theory. After some
background material I shall attempt to describe two constructions, due
to Lubotzky-Philips-Sarnak and Pizer and explain how the relation to
modular forms comes about. I shall then discuss joint work with Dennis
Charles and Kristin Lauter (both at Microsoft Research) that constructs
hash functions from Ramanujan graphs and explain some (seemingly) new
questions it raises.