1549380232-Automorphic_Forms_and_Applications__Sarnak_

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

(3) [Nilli [31]]. He showed that if the diameter of a k-regular graph X is at least

d + 2, then

The analogous asymptotic result for lim sup _A-(X) does not hold uncondition-

ally. For example, the line graph of a connected regular graph is itself a connected

regular graph, and Sachs [32] showed that such a graph has smallest eigenvalue -2

regardless of the size. Recall that the line graph of X has as vertices the edges of

X; two vertices are adjacent in a line graph if the two edges in X share a common

vertex in X.

Theorem 1.2. [Li [20]] Assume the family { Xj} satisfies the extra condition

(C) the length of the shortest odd cycle in Xj tends to oo as j ~ oo.

Then

limsup.A-(Xj):::; -2Vk-l.

IX;l->oo

We give a brief explanation of why >.±(X) behave as described above. Take a

vertex u in X and denote by Um(X) the set of vertices in X whose distance to u is

m. Write q for k - l. Let

Bu(d) ball centered at u with radius d

d

LJ Ui(X).

i=O

The size of U 1 is :::; (q + 1), and the size of Um+l is at most (q + 1) qm. Define

{

1 if x E Uo,

f(x)= (jq)m ifxEUm+lforO:::;m:::;d-1,

0 otherwise.

If each vertex x in Um+l has one neighbor in Um and q neighbors in Um+ 2 ,

then

(

1 ) m ( 1 ) m+

2

Af(x) = vq + q vq = ( vq 1 ) m+l ( Jg+ q vq 1 ) = f(x) (20J).

If this is so for all m = 0, ... , d - 1, then f is almost an eigenfunction of A with
eigenvalue 2 vq and llAf - 2 vq fll/llfll ~ 0 as d ~ oo.
If this is so for all m = 0, ... , d - 1, then f is almost an eigenfunction of A
with eigenvalue 2 vq and llAf - 2 vq fll/llfll ~ 0 as d ~ oo. However, if some
x in Um+l has less than q neighbors in Um+ 2 , then this only makes Af(x) larger.
Hence the lim inf .A+ (Xj) result is unconditional.

To study .A -(Xj), on Bu ( d) we define

g(x)={ (-~r

. 0

if x E Uo,

if x E Um+l for 0 :::; m:::; d - 1,

otherwise.