In which we present an algebraic construction of expanders.
1. The Marguli-Gabber-Galil Expanders
We present a construction of expander graphs due to Margulis, which was the first explicit construction of expanders, and its analysis due to Gabber and Galil. The analysis presented here includes later simplifications, and it follows an exposition of James Lee.
For every , we construct graphs with vertices, and we think of the vertex set as , the group of pairs from where the group operation is coordinate-wise addition modulo .
Define the functions and , where all operations are modulo . Then the graph has vertex set and the vertex is connected to the vertices
so that is an 8-regular graph. (The graph has parallel edges and self-loops.)
We will prove that there is a constant such that for every .
The analysis will be in four steps, and it will refer to certain infinite “graphs.”
We define an infinite family of graphs , such that the vertex set of is , that is, every vertex of is a pair , where and , and we think of and as elements of the group in which we do addition modulo . Every vertex of is connected to the vertices
and is 4-regular. For each of these graphs, we will define a “spectral gap” ; we put “spectral gap” in quotes because, although it is actually the second smallest eigenvalue of a Laplacian operator, we will define it purely formally as the minimum of a certain optimization problem.
We will also define the graph , whose vertex set is , and such that each vertex is connected to
so that is also -regular. We will define a “spectral gap” , again purely formally as the infimum of a certain expression, although it is the infimum of the spectrum of a certain Laplacian operator. We will also define an “edge expansion” of .
The proof of the expansion of will proceed by establishing the following four facts:
The first step will be a discretization argument, showing that a test vector of small Rayleigh quotient for can be turned into a test function of small Rayleigh quotient for . The second step is the most interesting and unexpected part of the proof; we will not spoil the surprise of how it works. The third step is proved the same way as Cheeger’s inequality. The fourth step is just a careful case analysis.
2. First Step: The Continuous Graph
Let be set of functions such that is well defined and finite. Then we define the following quantity, that we think of as the spectral gap of :
We could define a Laplacian operator and show that the above quantity is indeed the second smallest eigenvalue, but it will not be necessary for our proof.
We have the following bound.
Theorem 1 .
Proof: Let be the function such that
For a point , define . We extend to a function by defining
This means that we tile the square into unit squares whose corners are integer-coordinate, and that is constant on each unit square, and it equals the value of at the left-bottom corner of the square.
It is immediate to see that
and so, up to a factor of , the denominator of the Rayleigh quotient of is the same as the denominator of the Rayleigh quotient of .
It remains to bound the numerators.
Observe that for every , we have that equals either or , and that equals either or . The numerator of the Rayleigh quotient of is
because for a randomly chosen in the square , there is probability that and probability that .
Now we can use the “triangle inequality”
to bound the above quantity
which simplifies to
which is at most times the numerator of the Rayleigh quotient of .
3. Second Step: The Countable Graph
We now define the graph of vertex set , where each vertex is connected to
For a -regular graph with an countably infinite set of vectors, define to be the set of functions such that is finite, and define the smallest eigenvalue of as
We want to show the following result.
Theorem 2 For every , .
Proof: This will be the most interesting part of the argument. Let be any function such that , we will show that the Fourier transform of has a Rayleigh quotient for that is at most the Rayleigh quotient of for .
First, we briefly recall the definitions of Fourier transforms. If is such that
then we can write the linear combination
where the basis functions are
and the coefficients are
The condition gives
and the Parseval identity gives
and so we have that the denominator of the Rayleigh quotient of for and of for As usual, the numerator is more complicated.
We can break up the numerator of the Rayleigh quotient of as
where and , and we can use Parseval’s identity to rewrite it as
The Fourier coefficients of the function can be computed as
where we used the change of variable .
Similarly, . This means that the numerator of the Rayleigh quotient of for is equal to the numerator of the Rayleigh quotient of for .
4. Third Step: A Cheeger Inequality for countable graphs
Define the edge expansion of a -regular graph with a countably infinite set of vertices as
Note that the edge expansion can be zero even if the graph is connected.
Proof: This is similar to the proof for finite graphs, with the simplification that we do not need to worry about constructing a set containing at most half of the vertices.
Let be any function. We will show that is at most where
is the Rayleigh quotient of .
For every threshold , define the set as
and note that each set is finite because is finite. We have, for ,
and, for all
Now we compute the integral of the numerator and denominator of the above expression, and we will find the numerator and denominator of the Rayleigh quotient .
Now we proceed with Cauchy Schwarz:
And we have
5. Expansion of
After all these reductions, we finally come to the point where we need to prove that something is an expander.
Proof: Let be a finite subset of .
Let be the set of elements of that have one 0 coordinate. Let be the set of elements of with nonzero coordinate that belong to the 1st, 2nd, 3rd and 4th quadrant. (Starting from the quadrant of points having both coordinates positive, and numbering the remaining ones clockwise.)
Claim 1 .
Proof: Consider the sets and ; both and are permutations, and so . Also, and are disjoint, because if we had then we would have while all the coordinates are strictly positive. Finally, and are also contained in the first quadrant, and so at least of the edges leaving lands outside . We can make a similar argument in each quadrant, considering the sets and in the second quadrant, the sets and in the third, and and in the fourth.
Proof: All the edges that have one endpoint in have the other endpoint outside of . Some of those edges, however, may land in . Overall, can account for at most edges, and we have already computed that at least of them land into , so can absorb at most of the outgoing edges of .
Balancing the two equalities (adding the first plus times the second) gives us the theorem.