Boppana | in theory

Let ${G=(V,E)}$ be a ${d}$ -regular graph, and let

$\displaystyle d= \lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$

be the eigenvalues of the adjacency matrix of ${A}$ counted with multiplicities and sorted in descending order.

How good can the spectral expansion of ${G}$ be?

1. Simple Bounds

The simplest bound comes from a trace method. We have

$\displaystyle trace(A^2) = \sum_i \lambda_i^2$

by using one definition of the trace and

$\displaystyle trace(A^2) = \sum_{v,v} (A^2)_{v,v} \geq dn$

using the other definition and observing that ${(A^2)_{v,v}}$ counts the paths that go from ${v}$ to ${v}$ in two steps, of which there are at least ${d}$ : follow an edge to a neighbor of ${v}$ , then follow the same edge back. (There could be more if ${G}$ has multiple edges or self-loops.)

So we have

$\displaystyle dn \leq d^2 + \sum_{i=2,\ldots,n} \lambda_i ^2$

and so

$\displaystyle \max_{i=2,\ldots,n} |\lambda_i | \geq \sqrt d \cdot \sqrt{\frac {n-d}{n-1}}$

The condition ${d \leq n(1-\epsilon)}$ is necessary to get lower bounds of ${\Omega(\sqrt d)}$ ; in the clique, for example, we have ${d=n-1}$ and ${\lambda_2 = \lambda_n = -1}$ .

A trace argument does not give us a lower bound on ${\lambda_2}$ , and in fact it is possible to have ${\lambda_2=0}$ and ${d= n/2}$ , for example in the bipartite complete graph.

If the diameter of ${G}$ is at least 4, it is easy to see that ${\lambda_2 \geq \sqrt d}$ . Let ${a,b}$ be two vertices at distance 4. Define a vector ${x}$ as follows: ${x_a = 1}$ , ${x_v = 1/\sqrt d}$ if ${v}$ is a neighbor of ${a}$ , ${x_b=-1}$ and ${x_v = - 1/\sqrt d}$ if ${v}$ is a neighbor of ${b}$ . Note that there cannot be any edge between a neighbor of ${a}$ and a neighbor of ${b}$ . Then we see that ${||x||^2 = 4}$ , that ${x^T A x \geq 4\sqrt d}$ (because there are ${2d}$ edges, each counted twice, that give a contribution of ${1/\sqrt d}$ to ${\sum_{u,v} A_{uv} x_u x_v}$ ) and that ${x}$ is orthogonal to ${(1,\ldots,1)}$ .

2. Nilli’s Proof of the Alon-Boppana Theorem

Nilli’s proof of the Alon-Boppana theorem gives

$\displaystyle \lambda_2 \geq 2 \sqrt{ d-1 } - O \left( \frac {\sqrt{d-1}}{diam(G)-4} \right)$

where ${diam(G) \geq \frac {\log |V|}{\log d-1}}$ is the diameter of ${G}$ . This means that if one has a family of (constant) degree- ${d}$ graphs, and every graph in the family satisfies ${\lambda_2 \leq \lambda}$ , then one must have ${\lambda \geq 2 \sqrt{d -1}}$ . This is why families of Ramanujan graphs, in which ${\lambda_2 \leq 2 \sqrt{d-1}}$ , 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. Continue reading →

in theory

"Marge, I agree with you – in theory. In theory, communism works. In theory." — Homer Simpson

Tag Archives: Boppana

The Alon-Boppana Theorem