Let be a -regular graph, and let
be the eigenvalues of the adjacency matrix of counted with multiplicities and sorted in descending order.
How good can the spectral expansion of be?
1. Simple Bounds
The simplest bound comes from a trace method. We have
by using one definition of the trace and
using the other definition and observing that counts the paths that go from to in two steps, of which there are at least : follow an edge to a neighbor of , then follow the same edge back. (There could be more if has multiple edges or self-loops.)
So we have
The condition is necessary to get lower bounds of ; in the clique, for example, we have and .
A trace argument does not give us a lower bound on , and in fact it is possible to have and , for example in the bipartite complete graph.
If the diameter of is at least 4, it is easy to see that . Let be two vertices at distance 4. Define a vector as follows: , if is a neighbor of , and if is a neighbor of . Note that there cannot be any edge between a neighbor of and a neighbor of . Then we see that , that (because there are edges, each counted twice, that give a contribution of to ) and that is orthogonal to .
2. Nilli’s Proof of the Alon-Boppana Theorem
Nilli’s proof of the Alon-Boppana theorem gives
where is the diameter of . This means that if one has a family of (constant) degree- graphs, and every graph in the family satisfies , then one must have . This is why families of Ramanujan graphs, in which , are special, and so hard to construct, or even to prove existence of.
Friedman proves a stronger bound, in which the error term goes down with the square of the diameter. Friedman’s proof is the one presented in the Hoory-Linial-Wigderson survey. I like Nilli’s proof, even if it is a bit messier than Friedman’s, because it starts off with something that clearly is going to work, but the first two or three ways you try to establish the bound don’t work (believe me, I tried, because I didn’t see why some steps in the proof had to be that way), but eventually you find the right way to break up the estimate and it works.
So here is Nilli’s proof. Read the rest of this entry »