Brief History
of Expander Graphs

•Originally shown to exist by counting methods

non-expander
graphs.

•Margulis (70s, 80s),
Lubotzky-Phillips-Sarnak (1986) give first constructions.

•LPS “Ramanujan graphs” use the (known)
Ramanujan conjectures
in their proof. The Ramanujan
conjectures in
number theory are a statement about optimal cancellation in random sums.

•Other constructions:
Reingold-Vadhan-Wigderson “Zig-Zag”, algebraic geometry. Have algebraic flavor.