“GRH Graphs”

•Let Q be a large integer.

•Let S = { primes p < (log Q)B , p - Q } , for B
> 2.

•Define the graph G to have

– vertices V=(Z/QZ)*.

– edges connecting v to pv, for
each v 2 V and p 2 S.

– (G is the *Cayley
graph* of the group (Z/QZ)* with respect to the generating
set S).

•Theorem
– Assuming GRH, G is an expander: its nontrivial eigenvalues
satisfy the bound

|l| = O(k1/2+1/B).

New, conditional
construction of expander graphs.