1549380232-Automorphic_Forms_and_Applications__Sarnak_

416 W.-C. W. LI, RAMANUJAN GRAPHS AND RAMANUJAN HYPERGRAPHS

(d) (diagonalizability) The operators Ai are simultaneously diagonalizable, and

the space of functions on vertices of X has an orthonormal basis consisting of

common eigenfunctions of the Ai 's.

An n-hypergraph is called (q + 1)-regular if it satisfies the following regularity

condition:

(R) (regularity) There is a positive integer q such that for i = 1, ... , n - 1, each

vertex x has exactly

(qn - 1) · · · (q - 1)

qn,i := (qi_ 1) ... (q _ l)(qn-i _ 1) ... (q _ 1)

neighbors of type T(x) + i.

Thus a (q+ 1)-regular 2-hypergraph is nothing but a (q+ 1)-regular bipartite graph.

A typical example of a ( q + 1 )-regular n-hypergraph is the Bruhat-Tits building

Bn,F := PGLn(F)/PGLn(OF), where Fis a nonarchimedean local field with q ele-

ments in its residue field, and OF is its ring of integers. We examine the conditions

in detail. Let 7r be a uniformizer of F. Each vertex x of Bn,F, when expressed

as g GLn(OF) Z(F) for some g E GLn(F) with Z the center of GLn, represents an

equivalence class of rank n lattices L x over OF with basis the columns of g. The

determinant of g is 7rm times a unit in OF, and the integer mis well-defined mod n,

which defines the type of x. Two vertices x and y of Bn,F with T(y) = T(x) + i

for some 1 :"'.:: i :::; n - 1 are adjacent if and only if x and y can be represented by

some lattices Lx and Ly such that Lx J Ly J 7r Lx and the index [Lx : Ly] =qi.

Vertices X1, ... , Xn form a hyperedge if and only if the vertices x 1 , ... , Xn can be

represented by lattices L 1 , ... , Ln so that

Li J L2 J · · · J Ln J 7r Li.

Hence the condition (P) holds.

Similar to the case n = 2, for 1 :::; i :::; n - 1, the operator Ai on Bn,F is the

Hecke operator Ti which acts on the functions on vertices of Bn,F by convolution

with the characteristic function of the PGLn ( 0 F )-double coset

7r

1

1

In other words, if we express this double coset as a disjoint union of a PGLn ( 0 F),

a E Si, then

(Ad)([g]) = L f([ga]).

a.ES,

We may choose coset representatives a in S i to be upper-triangular with determi-
nant 7ri, entries in 0 F, and diagonal entries being 7r or 1. To a we associate the
vector~ = (w1, ... , wn) E {O, l}n so that Wj = 1 if and only if the j-th diagonal
entry of a is 7r. We call w the type of a and the set {1 :::; j :::; n : Wj = 1} the
support of a or w. Clearly, the support of w has cardinality i. Denote by Ii the set