[ACM Press the eighteenth annual ACM symposium - Berkeley, California, United States (1986.05.28-1986.05.30)] Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86 - Explicit expanders and the Ramanujan conjectures

✍ Scribed by Lubotzky, A; Phillips, R; Sarnak, P

• Book ID: 121280298
• Publisher: ACM Press
• Year: 1986
• Weight: 284 KB
• Category: Article
• ISBN-13: 9780897911931
• DOI: 10.1145/12130.12154

✦ Synopsis

1. Background. The aim of this note is to give an explicit construction of a rich family of k-regular (except for k ° =k) of the adjacency matrix satisfy Ikjl < 2 k~-l. graphs for which all the eigenvalues kj This bound is optimal (see Proposition 2.1). We call such graphs Ramanujan graphs.

These graphs have many applications in the construction of explicit algorithms. ~ny of these applications come from the fact that Ramanujan graphs make good expanders. Expanders in ~irn serve as basic building blocks for the construction of nonblocking networks [Pin, Bas-Pin, PI1], s~perconcentrators [G-G], sorting and selecting algorithms [AKS, PI3] etc.

More precisely let X = (V,E) be a graph with vertices V and edges E . For A c: V we define the boundary of A, denoted ~A, by 8A = [yc V[d(y,A) = i} .