Jump to content

User:Sujaykazi/sandbox

From Wikipedia, the free encyclopedia

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

Theorem statement

[edit]

Let be a -regular graph on vertices, and let be its adjacency matrix. Let be its eigenvalues. Then

More precisely, the term refers to the asymptotic behavior as grows without bound while remains fixed. Also, the fact that is -regular implies that with the all-ones vector being the corresponding eigenvector.

First proof

[edit]

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 weaker statement)

[edit]

This proof will demonstrate a slightly weaker 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

The Cayley graph of the free group on two generators and is an example of an infinite -regular tree for


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 of the bound

[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


References

[edit]
  1. ^ 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
  2. ^ 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