1549380232-Automorphic_Forms_and_Applications__Sarnak_

LECTURE 1. F INITE MODELS 345

Basic Questions about Spectra of Finite Connected k-Regular Graphs

• 
  
  
  
  1. Can non-isomorphic graphs have the same spectrum? Can you hear
     the shape of a graph?
  
  
  
  


• 
  
  
  
  2. a) What ar e bounds on the spectrum of A? Note that k is a lways an
  
  
  
  

eigenvalue of multiplicity 1. And -k is an eigenvalue iff X is bipartite.

Are there gaps in the spectrum or does it approach the interval [-k, k] as

t he number of vertices of the graph goes to infinity? Is 0 an eigenvalue of

A?

b) What does the size of t he second largest eigenvalue of A in absolute

value have to do with graph-theoretic constants such as diameter, girth ,

chromatic number, expansion constants?

• 
  
  
  
  3. Does the histogram of the spectrum of AJ (the a dj acency matrix of Xj)
     approach the Wigner semi-circle distribution for a sequence of graphs Xj,
     with [XJ[---> oo, as j---> oo?
  
  
  
  


• 
  
  
  
  4. Arrange the spectrum P·n}of Aj so that An ::; An+i· Consider the level
     spacings [An+i - An [ normalized to h ave mean 1. What is the limiting
     histogram for the level spacings as j ---> oo?
  
  
  
  


• 
  
  
  
  5. What can be said about the behavior of t he eigenfunctions (eigenvec-
     tors) of A?
  
  
  
  

Here we will discuss some of these questions for some special types of graphs.

Exercise 3. Show that for a connected k-regular graph X, the degree k is always

an eigenvalue of multiplicity 1. Prove that -k is an eigenvalu e iff X is bipartite.

Figure out the definitions of diameter, girth, chromatic number, expansion constant

of a graph and explore the connections with bounds on the second largest eigenvalue

of A in absolute value. R eferences are: Biggs [10] , Bollobas [13], Terms [82].

It was shown by Alon and Boppana (see Lubotzky [52], p. 57 or Feng and Li

[28] for a generalization to hypergraphs) that for connected k-regular graph s X, if

A(X) denotes the second largest eigenvalue of A in absolute value, then

liminf A(X) 2: 2(k - 1)^112 , as [X[ _____, oo.

Following Lubotzky, Phillips and Sarnak [53], we call a k-regular graph X Ra-
manujan iff

(4.1) A(X)::; 2(k - 1)^112.

Thus Ramanujan graphs a re the connected k-regular graphs with the smallest pos-
sible asymptotic bound on their eigenvalues. Such graphs are good expanders and
(when the graph is not bipartite) the standard random walk on X converges ex-
trem ely rapidly to uniform. This means that Ramanujan graphs make efficient
communications networks. See Lubotzky [52], Sarnak [66], and Terras [82]. Fi-
nally Ramanujan graphs are those for which the Ihara zeta function satisfies the
an alogue of the Riemann hypothesis. See Exercise 9 in Lecture 2.

Remark 1. The name "Ramanujan" was attached to these graphs by Lubotzky,
Phillips and Barnak [53] because they needed to use the (now proved) R amanujan
conjecture on the size of Fourier coefficients of modular forms such as .6. in order
to show that the graphs they created did satisfy the inequality ( 4 .1).