User:Sujaykazi/sandbox

The Alon-Boppana bound provides a lower bound on the second-largest eigenvalue of the adjacency matrix of a graph.

Theorem statement

Let $G$ be a $d$-regular graph on $n$ vertices, and let $A$ be its adjacency matrix. Let $\lambda _{1}\geq \lambda _{2}\geq ...\geq \lambda _{n}$ be its eigenvalues. Then $\lambda _{2}\geq 2{\sqrt {d-1}}-o(1).$

More precisely, the $o(1)$ term refers to the asymptotic behavior as $n$ grows without bound while $d$ remains fixed. Also, the fact that $G$ is $d$-regular implies that $\lambda _{1}=d,$ with the all-ones vector $\mathbf {1}$ being the corresponding eigenvector.

First proof

Let the vertex set be $V.$ By the min-max theorem, it suffices to construct a nonzero vector $z\in \mathbb {R} ^{|V|}$ such that $z^{\text{T}}\mathbf {1} =0$ and ${\frac {z^{\text{T}}Az}{z^{\text{T}}z}}\geq 2{\sqrt {d-1}}-o(1).$

Pick some value $r\in \mathbb {N} .$ For each vertex in $V,$ define a vector $f(v)\in \mathbb {R} ^{|V|}$ as follows. Each component will be indexed by a vertex $u$ in the graph. For each $u,$ if the distance between $u$ and $v$ is $k,$ then the $u$-component of $f(v)$ is $f(v)_{u}=w_{k}=(d-1)^{-k/2}$ if $k\leq r-1$ and $0$ if $k\geq r.$ We claim that any such vector $x=f(v)$ satisfies

${\frac {x^{\text{T}}Ax}{x^{\text{T}}x}}\geq 2{\sqrt {d-1}}\left(1-{\frac {1}{2r}}\right).$

To prove this, let $V_{k}$ denote the set of all vertices that have a distance of exactly $k$ from $v.$ First, note that

$x^{\text{T}}x=\sum _{k=0}^{r-1}|V_{k}|w_{k}^{2}.$

Second, note that

$x^{\text{T}}Ax=\sum _{u\in V}x_{u}\sum _{u'\in N(u)}x_{u'}\geq \sum _{k=0}^{r-1}|V_{k}|w_{k}\left[w_{k-1}+(d-1)w_{k+1}\right]-(d-1)|V_{r-1}|w_{r-1}w_{r},$

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

$x^{\text{T}}Ax\geq 2{\sqrt {d-1}}\left(\sum _{k=0}^{r-1}|V_{k}|w_{k}^{2}-{\frac {1}{2}}|V_{r-1}|w_{r}^{2}\right),$

which, when combined with the fact that $|V_{k+1}|\leq (d-1)|V_{k}|$ for any $k,$ yields

$x^{\text{T}}Ax\geq 2{\sqrt {d-1}}\left(1-{\frac {1}{2r}}\right)\sum _{k=0}^{r-1}|V_{k}|w_{k}^{2}.$

The combination of the above results proves the desired inequality.

For convenience, define the $(r-1)$-ball of a vertex $v$ to be the set of vertices with a distance of at most $r-1$ from $v.$ Notice that the entry of $f(v)$ corresponding to a vertex $u$ is nonzero if and only if $u$ lies in the $(r-1)$-ball of $x.$

The number of vertices within distance $k$ of a given vertex is at most $1+d+d(d-1)+d(d-1)^{2}+...+d(d-1)^{k-1}=d^{k}+1.$ Therefore, if $n\geq d^{2r-1}+2,$ then there exist vertices $u,v$ with distance at least $2r.$

Let $x=f(v)$ and $y=f(u).$ It then follows that $x^{\text{T}}y=0,$ because there is no vertex that lies in the $(r-1)$-balls of both $x$ and $y.$ It is also true that $x^{\text{T}}Ay=0,$ because no vertex in the $(r-1)$-ball of $x$ can be adjacent to a vertex in the $(r-1)$-ball of $y.$

Now, there exists some constant $c$ such that $z=x-cy$ satisfies $z^{\text{T}}\mathbf {1} =0.$ Then, since $x^{\text{T}}y=x^{\text{T}}Ay=0,$

$z^{\text{T}}Az=x^{\text{T}}Ax+c^{2}y^{\text{T}}Ay\geq 2{\sqrt {d-1}}\left(1-{\frac {1}{2r}}\right)(x^{\text{T}}x+c^{2}y^{\text{T}}y)=2{\sqrt {d-1}}\left(1-{\frac {1}{2r}}\right)z^{\text{T}}z.$

Finally, letting $r$ grow without bound while ensuring that $n\geq d^{2r-1}+2$ (this can be done by letting $r$ grow sublogarithmically as a function of $n$) makes the error term $o(1)$ in $n.$

Second proof (slightly weaker statement)

This proof will demonstrate a slightly weaker result, but it provides better intuition for the source of the number $2{\sqrt {d-1}}.$ Rather than showing that $\lambda _{2}\geq 2{\sqrt {d-1}}-o(1),$ we will show that $\lambda =\max(|\lambda _{2}|,|\lambda _{n}|)\geq 2{\sqrt {d-1}}-o(1).$

First, pick some value $k\in \mathbb {N} .$ Notice that the number of closed walks of length $2k$ is

${\text{tr}}A^{2k}=\sum _{i=1}^{n}\lambda _{i}^{2k}\leq d^{2k}+n\lambda ^{2k}.$

However, it is also true that the number of closed walks of length $2k$ starting at a fixed vertex $v$ in a $d$-regular graph is at least the number of such walks in an infinite $d$-regular tree, because an infinite $d$-regular tree can be used to cover the graph. By the definition of the Catalan numbers, this number is at least $C_{k}(d-1)^{k},$ where $C_{k}={\frac {1}{k+1}}{\binom {2k}{k}}$ is the $k^{\text{th}}$ Catalan number.

It follows that

${\text{tr}}A^{2k}\geq n{\frac {1}{k+1}}{\binom {2k}{k}}(d-1)^{k}$

$\implies \lambda ^{2k}\geq {\frac {1}{k+1}}{\binom {2k}{k}}(d-1)^{k}-{\frac {d^{2k}}{n}}.$

Letting $n$ grow without bound and letting $k$ grow without bound but sublogarithmically in $n$ yields $\lambda \geq 2{\sqrt {d-1}}-o(1).$

The Cayley graph of the free group on two generators $a$ and $b$ is an example of an infinite $d$-regular tree for $d=4.$

The intuition for the number $2{\sqrt {d-1}}$ comes from considering the infinite $d$-regular tree. This graph is a universal cover of $d$-regular graphs, and it has spectral radius $2{\sqrt {d-1}}.$

Saturation of the bound

A graph that essentially saturates the Alon-Boppana bound is called a Ramanujan graph. More precisely, a Ramanujan graph is a $d$-regular graph such that $|\lambda _{2}|,|\lambda _{n}|\leq 2{\sqrt {d-1}}.$