Alex Lubotzky

From Ramanujan graphs to Ramanujan complexes

ABSTRACT: Ramanujan graphs are k-regular graphs with all non trivial eigenvalues are bounded ( in absolute value) by 2SR(k-1). They are optimal expanders (from spectral point of view). Explicit constructions of such graphs were given in the 80’s as quotients of the Bruhat-Tits tree associated with GL(2) over a local field F, by the action of suitable congruence subgroups of arithmetic groups. The spectral bound was proved using works of Hecke, Deligne and Drinfeld on the “Ramanujan conjecture” in the theory of automorphic forms. The work of Lafforgue, extending Drinfeld from GL(2) to GL(n), opened the door for the construction of Ramanujan complexes as quotients of the Bruhat-Tits buildings associated with GL(n) over F. This way one gets finite simplical complxes which on one hand are “random like” and at the same time have strong symmetries. These seemingly contradicting properties make them very useful for constructions of various external objects. Recently various applications have been found in combinatorics, coding theory and in relation to Gromov’s overlapping properties. We will survey some of these applications.