1549380232-Automorphic_Forms_and_Applications__Sarnak_

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

Observe that fi(x) = x + 1, and, by induction, form 2: 2,

fm(d) = L fm- 1(v1)

o::;v1::;d

is a polynomial in d over Q of degree m. Therefore we have

Proposition 2.8. The number of different support sequences occurring in the

elements of Mu(d+l) is fn-i(d+l) defined by equation (2. 1}, which is a polynomial

in d + 1 over Q of degree n - 1. Further, the function f defined above satisfies

(!, f) = O((d + l)n-l) for n fixed and d large.

It is not hard to prove

Lemma 2.9. For 1:::;: i:::;: n - 1 and [g] E M~(d), we have

(Ad)([g]) = f([g]) L qe(w) a(w) =Ai f([g]).

wEJ;

This is also valid if neither [g] nor its neighbors of type difference i lie in Mu ( d + 1).

Therefore Ad - Ai f is zero except on

(i) the boundary points Mu(d + 1) - M~(d);

(ii) vertices in Bu(d+2)-Mu(d+l) which have some neighbors falling in Mu(d+l).

It remains to estimate the contribution to (Ad - Ai f, Ad - Ai f ) on these two

kinds of points and compare them with(!,!). For each 1:::;: i:::;: n-1, each boundary

point in (i) has certain neighbors of type difference i lying inside Mu(d + 1) and

some outside. By a careful analysis, one proves that the number of different support

sequences occurring in elements of Mu(d+l)-M~(d) is fn-i(d+l)-fn-i(d-n+l),

which is O((d+ l)n-^2 ) for n fixed and d -too. This in turn leads to the conclusion

that the contribution of points in (i) to the inner product of Ad - Ai f with itself

is O((d + l)n-^2 ). A similar argument yields the same conclusion for points in (ii).

Therefore the quotient

(Ad - Ai f , Ad - Ai f) / (!, f) -t O

for each 1 :::;: i ::::; n - l. This proves Theorem 2.2.

asd-too

Using the diagonality condition (d), we can reinterprete Theorem 2.2 spectrally.

Theorem 2.10. Let { Xj} be a family of finite ( q + 1 )-regular n-hypergraphs whose

radius approaches infinity as j -t oo. Then, for 1 :::;: i ::::; n - 1, the closure of the

collection of eigenvalues of Ai (Xj), j 2: 1, contains qi (n-l)/^2 Dn,ii the spectrum of

A i on Bn,F·

Theorem 2.10 motivates the following definition of Ramanujan hypergraphs.

Definition. A finite (q + 1)-regular n-hypergraph Xis called a Ramanujan hyper-
graph if, for 1 :::;: i :::;: n - 1, all eigenvalues of Ai (X) other than qn,i (;;', 1 :::;: m ::::; n,
fall in the region qi (n-i)/^2 Dn,i · Here (n = e^2 rr i/n.