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.

The Shocking Blue Green Theme Blog at


Get every new post delivered to your Inbox.

Join 59 other followers