Expander graphs
Expander graphs
-
Ryan Alweiss, Princeton University
Fine Hall 110
In this talk, we will introduce expander graphs, which are constant degree graphs with good connectivity properties. We will briefly discuss important properties of expanders, including Cheeger's inequality which shows the equivalence of the algebraic and combinatorial definitions of expanders. We will introduce Ramanujan graphs, which are the best possible expanders. We will then discuss some of the connections between expander graphs and fields as diverse as theoretical computer science and number theory, including the construction of Ramanujan graphs by Lubotzsky, Phillips, and Sarnak using Cayley graphs of matrix groups.