Many months (and only one post) ago, I wrote about an analysis of the Gabber-Galil graphs using a simple combinatorial lemma and the discrete Cheeger inequality. Here is a note I posted recently carrying the study a bit further.
Given any two invertible, integral matrices 
, one can consider the family of graphs 
, where 
contains edges from every 
to each of
The Gabber-Galil graphs correspond to the choice 
and 
.
Consider also the countably infinite graph 
with vertex set 
and edges
Using some elementary Fourier analysis and a discrete Cheeger inequality, one can prove the following relationship (we use 
to represent the transpose of a matrix 
).
Theorem 1 For any , if 
has positive Cheeger constant, then 
is a family of expander graphs.
We recall that an infinite graph 
with uniformly bounded degrees has positive Cheeger constant if there is a number 
such that every finite subset 
has at least 
edges with exactly one endpoint in 
.
While Theorem 1 may not seem particularly powerful, it turns out that in many interesting cases, proving a non-trivial lower bound on the Cheeger constant of is elementary. For the Gabber-Galil graphs, the argument is especially simple. The following argument is, in fact, significantly simpler than the analysis of the previous post.
In the next lemma, let 
where 
and 
and let 
be the corresponding edge set. We will prove that 
has positive Cheeger constant.
Lemma 2 For any finite subset 
, we have 
.
Proof: Define 
. This is the first quadrant, without the 
-axis and the origin. Define 
similarly by rotating 
by 
, 
, and 
degrees, respectively, and note that we have a partition 
.
Let 
. We will show that 
. Since our graph is invariant under rotations of the plane by 
, this will imply our goal:
It is immediate that 
. Furthermore, we have 
because 
maps points in above (or onto) the line 
and 
maps points of below the line . Furthermore, and are bijections, thus 
In particular, this yields , as desired. 
One can generalize the Gabber-Galil graphs in a few different ways. As a prototypical example, consider the family 
for any 
. An elementary analysis yields the following characterization.
Theorem 3 For any 
, it holds that is an expander family if and only if 
.
For instance, the preceding theorem implies that if has order dividing 
then is not a family of expander graphs, but if has order 
or infinite order (the other possibilities) and 
then the graphs are expanders.
Here is a different sort of generalization. Let 
be the reflection across the line . The Gabber-Galil graphs can also be seen as 
where and 
. We can characterize expansion of these graphs as well.
Theorem 4 For any , it holds that 
is an expander family if and only if 
.
It is an interesting open problem to find a complete characterization of the pairs such that is a family of expanders.
