In spectral graph theory, the Alon–Boppana bound provides a lower bound on the second-largest eigenvalue of the adjacency matrix of a
d
d
d
d
Its discoverers are Noga Alon and Ravi Boppana.
Let
G
d
n
m
A
λ1\geλ2\ge … \geλn
λ2\ge2\sqrt{d-1}-
2\sqrt{d-1 | |
- |
1}{\lfloorm/2\rfloor}.
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.
The intuition for the number
2\sqrt{d-1}
d
d
2\sqrt{d-1}.
A graph that essentially saturates the Alon–Boppana bound is called a Ramanujan graph. More precisely, a Ramanujan graph is a
d
|λ2|,|λn|\le2\sqrt{d-1}.
A theorem by Friedman[1] shows that, for every
d
\epsilon>0
n
d
G
n
max\{|λ2|,|λn|\}<2\sqrt{d-1}+\epsilon
n
d
We will prove a slightly weaker statement, namely dropping the specificity on the second term and simply asserting
λ2\ge2\sqrt{d-1}-o(1).
o(1)
n
d
Let the vertex set be
V.
z\inR|V|
zT1=0
zTAz | |
zTz |
\ge2\sqrt{d-1}-o(1).
Pick some value
r\inN.
V,
f(v)\inR|V|
u
u,
u
v
k,
u
f(v)
f(v)u=wk=(d-1)-k/2
k\ler-1
0
k\ger.
x=f(v)
xTAx | |
xTx |
\ge2\sqrt{d-1}\left(1-
1 | |
2r |
\right).
To prove this, let
Vk
k
v.
xTx=
r-1 | |
\sum | |
k=0 |
2 | |
|V | |
k. |
Second, note that
xTAx=\sumu\inxu\sumu'\inxu'\ge
r-1 | |
\sum | |
k=0 |
|Vk|wk\left[wk-1+(d-1)wk+1\right]-(d-1)|Vr-1|wr-1wr,
where the last term on the right comes from a possible overcounting of terms in the initial expression. The above then implies
xTAx\ge
r-1 | |
2\sqrt{d-1}\left(\sum | |
k=0 |
2 | |
|V | |
k |
-
1 | |
2 |
|Vr-1
2 | |
|w | |
r-1 |
\right),
which, when combined with the fact that
|Vk+1|\le(d-1)|Vk|
k,
xTAx\ge2\sqrt{d-1}\left(1-
1 | |
2r |
r-1 | |
\right)\sum | |
k=0 |
2 | |
|V | |
k. |
The combination of the above results proves the desired inequality.
For convenience, define the
(r-1)
v
r-1
v.
f(v)
u
u
(r-1)
x.
The number of vertices within distance
k
1+d+d(d-1)+d(d-1)2+ … +d(d-1)k-1=dk+1.
n\ged2r-1+2,
u,v
2r.
Let
x=f(v)
y=f(u).
xTy=0,
(r-1)
x
y.
xTAy=0,
(r-1)
x
(r-1)
y.
Now, there exists some constant
c
z=x-cy
zT1=0.
xTy=xTAy=0,
zTAz=xTAx+c2yTAy\ge2\sqrt{d-1}\left(1-
1 | |
2r |
\right)(xTx+c2yTy)=2\sqrt{d-1}\left(1-
1 | |
2r |
\right)zTz.
Finally, letting
r
n\ged2r-1+2
r
n
o(1)
n.
This proof will demonstrate a slightly modified result, but it provides better intuition for the source of the number
2\sqrt{d-1}.
λ2\ge2\sqrt{d-1}-o(1),
λ=max(|λ2|,|λn|)\ge2\sqrt{d-1}-o(1).
First, pick some value
k\inN.
2k
\operatorname{tr}A2k=
n | |
\sum | |
i=1 |
2k | |
λ | |
i\le |
d2k+nλ2k.
However, it is also true that the number of closed walks of length
2k
v
d
d
d
k, | |
C | |
k(d-1) |
Ck=
1 | |
k+1 |
\binom{2k}{k}
kth
It follows that
\operatorname{tr}A2k\gen
1 | |
k+1 |
\binom{2k}{k}(d-1)k
\impliesλ2k\ge
1 | |
k+1 |
\binom{2k}{k}(d-1)k-
d2k | |
n |
.
Letting
n
k
n
λ\ge2\sqrt{d-1}-o(1).