Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\) (Q1333324): Difference between revisions

A Ramanujan graph is a finite connected \(r\)-regular graph, such that the second largest eigenvalue is at most \(2 \sqrt {r-1}\). Such graphs have good expansion properties, much sought after for applications in computer science. \textit{A. Lubotzky}, \textit{R. Phillips} and \textit{P. Sarnak} [Combinatorica 8, No. 3, 261-277 (1988; Zbl 0661.05035)] gave constructions for such graphs. The present paper gives further constructions. In particular, explicit constructions are presented for infinite families of \(q + 1\)-regular Ramanujan graphs, for any prime power \(q\) (not just for odd primes \(q)\). The graphs are given as Cayley graphs of \(PGL_ 2\) or \(PSL_ 2\) over finite fields.