# tcs math – some mathematics of theoretical computer science

## January 27, 2013

### Expanders from the action of GL(2,Z)

Filed under: Math — Tags: , , , — James Lee @ 8:14 pm

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 ${S,T \in GL_2(\mathbb Z)}$, one can consider the family of graphs ${G_n^{S,T} = (V_n, E_n^{S,T})}$, where ${E_n^{S,T}}$ contains edges from every ${(x,y) \in V_n}$ to each of

$\displaystyle (x \pm 1,y), (x,y\pm 1), S(x,y), S^{-1}(x,y), T(x,y), T^{-1}(x,y)\,.$

The Gabber-Galil graphs correspond to the choice ${S = \left(\begin{smallmatrix} 1 & 1 \\ 0 & 1 \end{smallmatrix}\right)}$ and ${T = \left(\begin{smallmatrix} 1 & 0 \\ 1 & 1 \end{smallmatrix}\right)}$.

Consider also the countably infinite graph ${G^{S,T}}$ with vertex set ${\mathbb Z^2 \setminus \{0\}}$ and edges

$\displaystyle E^{S,T} = \left\{ \{z,S z\}, \{z, T z\} : z \in \mathbb Z^2 \setminus \{0\} \right\}\,.$

Using some elementary Fourier analysis and a discrete Cheeger inequality, one can prove the following relationship (we use $S'$ to represent the transpose of a matrix $S$).

Theorem 1 For any ${S,T \in GL_2(\mathbb Z)}$, if ${G^{S',T'}}$ has positive Cheeger constant, then ${\{G_n^{S,T}\}}$ is a family of expander graphs.

We recall that an infinite graph ${G=(V,E)}$ with uniformly bounded degrees has positive Cheeger constant if there is a number ${\epsilon > 0}$ such that every finite subset ${U \subseteq V}$ has at least ${\epsilon |U|}$ edges with exactly one endpoint in ${U}$.

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 ${G^{S,T}}$ 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 $G=G^{S,T}$ where $S(x,y)=(x+y,x)$ and $T(x,y)=(x,y+x)$ and let $E=E^{S,T}$ be the corresponding edge set. We will prove that $G$ has positive Cheeger constant.

Lemma 2 For any finite subset ${A \subseteq \mathbb Z^2 \setminus \{0\}}$, we have ${ |E(A, \bar A)| \geq |A| }$.

Proof: Define ${Q_1 = \{ (x,y) \in \mathbb Z^2 : x > 0, y \geq 0 \}}$. This is the first quadrant, without the ${y}$-axis and the origin. Define ${Q_2, Q_3, Q_4}$ similarly by rotating ${Q_1}$ by ${90}$, ${180}$, and ${270}$ degrees, respectively, and note that we have a partition ${\mathbb Z^2 \setminus \{0\} = Q_1 \cup Q_2 \cup Q_3 \cup Q_4}$.

Let ${A_i = A \cap Q_i}$. We will show that ${|E(A_1, \bar A \cap Q_1)| \geq |A_1|}$. Since our graph is invariant under rotations of the plane by ${90^{\circ}}$, this will imply our goal:

$\displaystyle |E(A, \bar A)| \geq \sum_{i=1}^4 |E(A_i, \bar A \cap Q_i)| \geq \sum_{i=1}^4 |A_i| = |A|\,.$

It is immediate that ${S(A_1), T(A_1) \subseteq Q_1}$. Furthermore, we have ${S(A_1) \cap T(A_1) = \emptyset}$ because ${S}$ maps points in ${Q_1}$ above (or onto) the line ${y=x}$ and ${T}$ maps points of ${Q_1}$ below the line ${y=x}$. Furthermore, ${S}$ and ${T}$ are bijections, thus ${|S(A_1) + T(A_1)| = |S(A_1)| + |T(A_1)| = 2|A_1|\,.}$ In particular, this yields ${|E(A_1, \bar A \cap Q_1)| \geq |A_1|}$, as desired. $\Box$

One can generalize the Gabber-Galil graphs in a few different ways. As a prototypical example, consider the family ${\{G_n^{S,S'}\}}$ for any ${S \in GL_2(\mathbb Z)}$. An elementary analysis yields the following characterization.

Theorem 3 For any ${S =\left(\begin{smallmatrix} a & b \\ c & d \end{smallmatrix}\right) \in GL_2(\mathbb Z)}$, it holds that ${\{G_n^{S,S'}\}}$ is an expander family if and only if ${(a+d)(b-c) \neq 0}$.

For instance, the preceding theorem implies that if ${S}$ has order dividing ${4}$ then ${\{G_n^{S,S'}\}}$ is not a family of expander graphs, but if ${S}$ has order ${3, 6, 12}$ or infinite order (the other possibilities) and ${S \neq S'}$ then the graphs are expanders.

Here is a different sort of generalization. Let ${R = \left(\begin{smallmatrix} 0 & 1 \\ 1 & 0 \end{smallmatrix}\right)}$ be the reflection across the line ${y=x}$. The Gabber-Galil graphs can also be seen as ${G_n^{S,T}}$ where ${S = \left(\begin{smallmatrix} 1 & 1 \\ 0 & 1 \end{smallmatrix}\right)}$ and ${T = RSR}$. We can characterize expansion of these graphs as well.

Theorem 4 For any ${S =\left(\begin{smallmatrix} a & b \\ c & d \end{smallmatrix}\right) \in GL_2(\mathbb Z)}$, it holds that ${\{G_n^{S,RSR}\}}$ is an expander family if and only if ${(a+d)(b+c) \neq 0}$.

It is an interesting open problem to find a complete characterization of the pairs ${S,T \in GL_2(\mathbb Z)}$ such that ${\{G_n^{S,T}\}}$ is a family of expanders.