Brief History of Expander Graphs
Originally shown to exist by counting methods
: There are far more graphs than there are
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.