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 ).
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.
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.