Alon–Boppana bound – Wikipedia
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 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
, 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]
- ^ 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
- ^ 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
- ^ 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.
Recent Comments