The adjacency matrix A of a graph G of n vertices is an n×n
matrix such that a_{i,j} is 1 if there is an edge between
vertices i and j and 0 otherwise. Noga Alon noticed that a graph that
has a large gap between the first and second eigenvalue of
the adjacency matrix will be a good expander.

We can use ε-biased
sets to get expanders. Let S be a ε-biased set for
F^{m} for F the field of 2 elements. Consider the graph G
consisting of 2^{m} vertices labelled with the elements of
F^{m} and an edge from x to y if y=x+s or x=y+s. This kind of
graph G is known as a Cayley graph.

By looking at the eigenvalues the adjacency matrix A of G we can show G is an expander. The eigenvectors v are just the vectors corresponding to the functions g in L described earlier. For any vector a we have

_{s in S}g(a+s) = g(a) Σ

_{s in S}g(s)

_{s in S}g(s). We now have that

## No comments:

## Post a Comment