I’m currently teaching a course on spectral graph theory, and I decided to lecture on Margulis’ expander construction and the analysis of its spectral gap by Gabber and Galil. I had never realized how intuitive the analysis could be; the lectures notes I had seen didn’t quite reflect this. In particular, we won’t do any unsightly calculations. Everything I’m about to say is probably well-known, but I thought I would write it down anyway.
The idea is to first start with an initial “expanding object,” and then try to construct a family of graphs out of it. First, consider the infinite graph with vertex set . The edges are given by two maps and , where and . So the edges are and . Clearly is not adjacent to anything. Except for the origin, this graph is an expander in the following sense.
Lemma 1 For any subset , we have
where denotes the edges leaving .
The following simple proof is inspired by a paper of Linial and London.
Proof: First consider a subset that does not intersect the coordinate axes. Let represent the four quadrants of , and let . Consider that and . The latter fact follows because if then . Similarly, and and , while all the respective pairs and and are disjoint.
Combining this with the fact that and are bijections on immediately shows that is at least
Dealing with the coordinate axes is not too hard. Suppose now that is arbitrary. Let . The preceding argument shows . We will show that . Averaging these two inequalities with weights and completes the proof.
Let , and . Then we have the bounds:
The first equation follows since each element of is connected to exactly two elements of , and each element of is connected to exactly two elements of . For instance, is connected to and , while is connected to and .
The second follows because every point of is connected to two unique points of , e.g. is connected to and . The final inequality follows from the fact that from our first argument (since does not touch the axes), and because has no edges to . Summing these three inequalities yields .
Of course, is not a finite graph, so for a parameter , we define the graph with vertex set , where . There are four types of edges in : A vertex is connected to the vertices
This yields a graph of degree at most 8.
Theorem 2 There is a constant such that for every ,
where is the second-smallest eigenvalue of the Laplacian on .
Of course, the graphs now have torsion, and thus our expansion result for is not, a priori, very useful. The non-trivial idea of the proof is that the torsion doesn’t matter, making Lemma 1 applicable. This is not difficult to show using some Fourier analysis. It turns out to be better though, if we first move to the continuous torus.
Let be the 2-dimensional torus equipped with the Lebesgue measure, and consider the complex Hilbert space
equipped with the inner product .
We might also define a related value,
Note that this is just defined as a number; the eigenvalue notation is merely suggestive, but we have not introduced an operator on the torus.
Claim 1 There is some such that for any , we have \
Proof: We simply sketch a proof, which is rather intuitive. Suppose we are given some map such that . Define its continuous extension as follows: Under the natural embedding of into , every point sits inside a grid square with four corners . Writing a local convex combination , we define
Now it is elementary to verify that . It is also easy to verify that for some . (Even if , we still get a contribution from to on this square because we are taking a weighted average.)
Finally, for any , there is a path of length in connecting each of the corners of ‘s square to the corners of ‘s square. A similar fact holds for . In fact, this is the only place where we need to use the fact that edges of the form and are present in . Thus any contribution to can be charged against a term in , and similarly for .
Now our goal is to show that . We will use the Fourier transform to “remove the torsion.” The point is that and , being shift operators, will act rather nicely on the Fourier basis.
We recall that if and we define by , then forms an orthonormal Hilbert basis for . In particular, every can be written uniquely as
where . The Fourier transform is defined as a map , where . In particular, is a linear isometry.
Define and . Then for any , we have
In particular, for any , we have and . The final thing to note is that . So now if we simply apply the Fourier transform (a linear isometry) to the expression in (1), we get a reformulation that is precisely
Here we have simply replaced by in (1), and then written .
But now recall our initial infinite graph on . If we denote by the Laplacian on , then we can rewrite this as,
In other words, it is precisely the first Dirichlet eigenvalue on , subject to the boundary condition .
But now the discrete Cheeger inequality tells us that
where is the minimal expansion of any set not containing the origin. Thus we have indeed unwrapped the torsion and returned to our initial question. Lemma 1 shows that , yielding the desired lower bound on .
2 thoughts on “Gabber-Galil analysis of Margulis’ expanders”
What does it mean for a graph (or graph family) to have torsion ?
Perhaps it was a poor choice of words–the underlying group has torsion in the sense that it contains elements of finite order, i.e. non-zero elements such that . In general such a non-identity element of a group is called a torsion element. So in this case torsion for the graphs just meant “wrap around.”