In spectral graph theory, the Alon–Boppana bound provides a lower bound on the second-largest eigenvalue of the adjacency matrix of a -regular graph,[1] meaning a graph in which every vertex has degree . The reason for the interest in the second-largest eigenvalue is that the largest eigenvalue is guaranteed to be due to -regularity, with the all-ones vector being the associated eigenvector. The graphs that come close to meeting this bound are Ramanujan graphs, which are examples of the best possible expander graphs.

Its discoverers are Noga Alon and Ravi Boppana.

Theorem statement

edit

Let   be a  -regular graph on   vertices with diameter  , and let   be its adjacency matrix. Let   be its eigenvalues. Then

 

The above statement is the original one proved by Noga Alon. Some slightly weaker variants exist to improve the ease of proof or improve intuition. Two of these are shown in the proofs below.

Intuition

edit
 
The Cayley graph of the free group on two generators   and   is an example of an infinite  -regular tree for  

The intuition for the number   comes from considering the infinite  -regular tree.[2] This graph is a universal cover of  -regular graphs, and it has spectral radius  

Saturation

edit

A graph that essentially saturates the Alon–Boppana bound is called a Ramanujan graph. More precisely, a Ramanujan graph is a  -regular graph such that  

A theorem by Friedman[3] shows that, for every   and   and for sufficiently large  , a random  -regular graph   on   vertices satisfies   with high probability. This means that a random  -vertex  -regular graph is typically "almost Ramanujan."

First proof (slightly weaker statement)

edit

We will prove a slightly weaker statement, namely dropping the specificity on the second term and simply asserting   Here, the   term refers to the asymptotic behavior as   grows without bound while   remains fixed.

Let the vertex set be   By the min-max theorem, it suffices to construct a nonzero vector   such that   and  

Pick some value   For each vertex in   define a vector   as follows. Each component will be indexed by a vertex   in the graph. For each   if the distance between   and   is   then the  -component of   is   if   and   if   We claim that any such vector   satisfies

 

To prove this, let   denote the set of all vertices that have a distance of exactly   from   First, note that

 

Second, note that

 

where the last term on the right comes from a possible overcounting of terms in the initial expression. The above then implies

 

which, when combined with the fact that   for any   yields

 

The combination of the above results proves the desired inequality.

For convenience, define the  -ball of a vertex   to be the set of vertices with a distance of at most   from   Notice that the entry of   corresponding to a vertex   is nonzero if and only if   lies in the  -ball of  

The number of vertices within distance   of a given vertex is at most   Therefore, if   then there exist vertices   with distance at least  

Let   and   It then follows that   because there is no vertex that lies in the  -balls of both   and   It is also true that   because no vertex in the  -ball of   can be adjacent to a vertex in the  -ball of  

Now, there exists some constant   such that   satisfies   Then, since  

 

Finally, letting   grow without bound while ensuring that   (this can be done by letting   grow sublogarithmically as a function of  ) makes the error term   in  

Second proof (slightly modified statement)

edit

This proof will demonstrate a slightly modified result, but it provides better intuition for the source of the number   Rather than showing that   we will show that  

First, pick some value   Notice that the number of closed walks of length   is

 

However, it is also true that the number of closed walks of length   starting at a fixed vertex   in a  -regular graph is at least the number of such walks in an infinite  -regular tree, because an infinite  -regular tree can be used to cover the graph. By the definition of the Catalan numbers, this number is at least   where   is the   Catalan number.

It follows that

 
 

Letting   grow without bound and letting   grow without bound but sublogarithmically in   yields  

References

edit
  1. ^ Nilli, A. (1991), "On the second eigenvalue of a graph", Discrete Mathematics, 91 (2): 207–210, doi:10.1016/0012-365X(91)90112-F, MR 1124768
  2. ^ Hoory, S.; Linial, N.; Wigderson, A. (2006), "Expander Graphs and their Applications" (PDF), Bull. Amer. Math. Soc. (N.S.), 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8
  3. ^ Friedman, Joel (2003). "Relative expanders or weakly relatively Ramanujan graphs". Duke Math. J. 118 (1): 19–35. doi:10.1215/S0012-7094-03-11812-8. MR 1978881.