EXISTENCE AND EXPLICIT CONSTRUCTIONS OF Q-Q(1 REGULAR RAMANUJAN GRAPHS FOR EVERY PRIME POWER)

For any prime power q, we give explicit constructions for many infinit e linear families of q + 1 regular Ramanujan graphs. This partially so lves a problem that was raised by A. Lubotzky, R. Phillips, and P. Sar nak. They gave the same results as here, but only for q being prime an d not equal to two, and raised the question of the existence and expli cit construction of such graphs for other degrees of regularity. Moreo ver, our construction removes the nondeterministic part of finding lar ge prime numbers, which for some applications may appear in their cons truction. Our graphs are given as Cayley graphs of PGL(2) or PSL(2) ov er finite fields, with respect to very simple generators. They also sa tisfy all other extremal combinatorial properties that those of Lubots ky, Phillips, and Sarnak do. (C) 1994 Academic Press, Inc.