Discrete Mathematics and Optimization Seminar

---

EYAL GOREN
McGill University
Monday December 4th at 4.30pm
Burnside 1205



Title. Ramanujan graphs: a motivated introduction.

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