Constructions of
Expanders

•Known to exist by counting arguments (it
was known that the number of graphs which were not expanders was far smaller than the
total

•Margulis (1982 and earlier),
Lubotzky-Phillips-Sarnak (1986) gave explicit constructions using group theory,
number theory

•More recently, ideas from computer science:
Zig-Zag construction, covers

•Jao-Miller-Venkatesan: constructions
depending on the generalized Riemann hypothesis to prove expansion.

•Simplest example: Let *Q* be a large prime, and
vertices labeled {1,…,*Q-1*}. Connect vertex *x* to vertex *px*, where *p* is a prime smaller than
(log *Q*)**A**.