Expander Graphs

Graphs for which the random walk mixes rapidly (=uniformly distributed up to small error). Assume degree k is
relatively small compared to the size of the graph |V| -- e.g. k = (log|V|)power.

If all *nontrivial* eigenvalues of A satisfy

|l|
< k 1/(log k)r

for some r,
then the random
walk mixes in (log k)r+1 steps. Can
serve as definition of expander.

Optimal bound is |l| < 2(k-1)1/2, known as the Ramanujan bound.

Isogeny graphs are
close to being Ramanujan
graphs

Can have |l| = O(k1/2+e).