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.

April 18, 2012

Gabber-Galil analysis of Margulis’ expanders

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

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 {G} with vertex set {\mathbb Z^2} . The edges are given by two maps {S} and {T} , where {S(x,y) = (x,x+y)} and {T(x,y) = (x+y,y)} . So the edges are {\{(x,y), S(x,y)\}} and {\{(x,y), T(x,y)\}} . Clearly {(0,0)} is not adjacent to anything. Except for the origin, this graph is an expander in the following sense.

Lemma 1 For any subset {A \subseteq \mathbb Z^2 \setminus \{0\}} , we have

\displaystyle  |E(A)| \geq \frac{1}{3} |A|\,,

where {E(A)} denotes the edges leaving {A} .

The following simple proof is inspired by a paper of Linial and London.

Proof: First consider a subset {A} that does not intersect the coordinate axes. Let {Q_1, Q_2, Q_3, Q_4} represent the four quadrants of {\mathbb Z^2} , and let {A_i = A \cap Q_i} . Consider that {S(A_1), T(A_1) \subseteq Q_1} and {S(A_1) \cap T(A_1) = \emptyset} . The latter fact follows because if {(x,x+y)=(x'+y',y')} then {x'=-y} . Similarly, {S^{-1}(A_2), T^{-1}(A_2) \subseteq Q_2} and {S(A_3), T(A_3) \subseteq Q_3} and {S^{-1}(A_4), T^{-1}(A_4) \subseteq Q_4} , while all the respective pairs {S^{-1}(A_2), T^{-1}(A_2)} and {S(A_3), T(A_3)} and {S^{-1}(A_4), T^{-1}(A_4)} are disjoint.

Combining this with the fact that {S} and {T} are bijections on {\mathbb Z^2} immediately shows that {|S(A) \cup S^{-1}(A) \cup T(A) \cup T^{-1}(A)|} is at least

\displaystyle  |S(A_1)| + |T(A_1)| + |S^{-1}(A_2)| + |T^{-1}(A_2)|

\displaystyle  + |S(A_3)| + |T(A_3)| + |S^{-1}(A_4)| + |T^{-1}(A_4)|

\displaystyle  = 2(|A_1| + |A_2| + |A_3| + |A_4|)

\displaystyle  = 2 |A|\,.

Dealing with the coordinate axes is not too hard. Suppose now that {A \subseteq \mathbb Z^2 \setminus \{0\}} is arbitrary. Let {A_{+} = A \cap \{ (x,0), (0,x) : x \in \mathbb Z \}} . The preceding argument shows {|E(A)| \geq |A\setminus A_+|-|A_+| = |A|-2|A_+|} . We will show that {|E(A)| \geq |A_+|} . Averaging these two inequalities with weights {1/3} and {2/3} completes the proof.

Let {A_\times = A \cap \{ (x,x), (x,-x) : x \in \mathbb Z \}} , and {A_\circ = A \setminus (A_1 \cup A_2)} . Then we have the bounds:

\displaystyle |E(A_+, \bar A)| \geq |A_+| - |A_\times|

\displaystyle |E(A_\times, \bar A)| \geq 2|A_\times| - |A_\circ|

\displaystyle |E(A_\circ, \bar A)| \geq |A_\circ| - |A_\times|\,.

The first equation follows since each element of {A_+} is connected to exactly two elements of {A_{\times}} , and each element of {A_{\times}} is connected to exactly two elements of {A_+} . For instance, {(x,0)} is connected to {(x,x)} and {(x,-x)} , while {(x,x)} is connected to {(x,0)} and {(0,x)} .

The second follows because every point of {A_\times} is connected to two unique points of {A_\circ} , e.g. {(x,x)} is connected to {(x,2x)} and {(2x,x)} . The final inequality follows from the fact that {|E(A_\circ)| \geq |A_\circ|} from our first argument (since {A_{\circ}} does not touch the axes), and because {A_\circ} has no edges to {A_+} . Summing these three inequalities yields {|E(A)| \geq |A_+|} . \Box

Of course, {\mathbb Z^2} is not a finite graph, so for a parameter {n} , we define the graph {G_n=(V_n,E_n)} with vertex set {V_n = \mathbb Z_n \oplus \mathbb Z_n} , where {\mathbb Z_n = \mathbb Z/(n \mathbb Z)} . There are four types of edges in {E_n} : A vertex {(x,y)} is connected to the vertices

\displaystyle \{(x,y+1), (x+1, y), (x,x+y), (x+y,y)\}\,.

This yields a graph of degree at most 8.

Theorem 2 There is a constant {c > 0} such that for every {n \in \mathbb N} ,

\displaystyle  \lambda_2(G_n) \geq c\,,

where {\lambda_2} is the second-smallest eigenvalue of the Laplacian on {G_n} .

Of course, the graphs {\{G_n\}} now have torsion, and thus our expansion result for {\mathbb Z^2} 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.

Recall that,

\displaystyle  \lambda_2(G_n) = \min_{f : V_n \rightarrow \mathbb R} \left\{\frac{\sum_{uv \in E_n} (f(u)-f(v))^2}{\sum_{u \in V_n} f(u)^2} : \sum_{u \in V_n} f(u) = 0\right\}\,,

Let {\mathbb T^2 = \mathbb R^2/\mathbb Z^2} be the 2-dimensional torus equipped with the Lebesgue measure, and consider the complex Hilbert space

\displaystyle  L^2(\mathbb T^2) = \left\{ f : \mathbb T^2 \rightarrow \mathbb C : \int_{\mathbb T^2} |f|^2 < \infty \right\}\,.

equipped with the inner product {\langle f,g\rangle_{L^2} = \int_{\mathbb T^2} f \bar g} .

We might also define a related value,

\displaystyle   \lambda_2(\mathbb T^2) = \min_{f \in L^2(\mathbb T^2)} \left\{\frac{\|f-f\circ S\|_{L^2}^2 + \|f-f \circ T\|_{L^2}^2}{\|f\|_{L^2}^2} : \int_{\mathbb T^2} f = 0\right\}\,. \ \ \ \ \ (1)


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 {\varepsilon > 0} such that for any {n \in \mathbb N} , we have {\lambda_2(G_n) \geq \varepsilon \lambda_2(\mathbb T^2)} \

Proof: We simply sketch a proof, which is rather intuitive. Suppose we are given some map {f : V_n \rightarrow \mathbb R} such that {\sum_{u \in V_n} f(u)=0} . Define its continuous extension {\tilde f : \mathbb T^2 \rightarrow \mathbb R} as follows: Under the natural embedding of {\mathbb Z_n \oplus \mathbb Z_n} into {\mathbb T^2} , every point {z \in \mathbb T^2} sits inside a grid square with four corners {u_1,u_2,u_3,u_4 \in \mathbb Z_n \oplus \mathbb Z_n} . Writing a local convex combination {z = \lambda_1 u_1 + \lambda_2 u_2 + \lambda_3 u_3 + \lambda_4 u_4} , we define

\displaystyle  \tilde f(z) = \lambda_1 f(u_1) + \lambda_2 f(u_2) + \lambda_3 f(u_3) + \lambda_4 f(u_4)\,.

Now it is elementary to verify that {\int_{\mathbb T^2} \tilde f = 0} . It is also easy to verify that {\|\tilde f\|^2_{L^2} \geq c\frac{1}{n} \sum_{v \in V} f(v)^2} for some {c > 0} . (Even if {f(u_1)+f(u_2)+f(u_3)+f(u_4)=0} , we still get a contribution from {f(u_1)^2 + f(u_2)^2 + f(u_3)^2 + f(u_4)^2} to {\|\tilde f\|_{L^2}} on this square because we are taking a weighted average.)

Finally, for any {z \in \mathbb T^2} , there is a path of length {O(1)} in {G_n} connecting each of the corners of {z} ‘s square to the corners of {S(z)} ‘s square. A similar fact holds for {T(z)} . In fact, this is the only place where we need to use the fact that edges of the form {(x,y) \leftrightarrow (x,y+1)} and {(x,y) \leftrightarrow (x+1,y)} are present in {G_n} . Thus any contribution {|\tilde f(z)-\tilde f(S(z))|^2} to {\|\tilde f-\tilde f\circ S\|_{L^2}^2} can be charged against a term in {\sum_{uv \in E_n} (f(u)-f(v))^2} , and similarly for {T} . \Box

Now our goal is to show that {\lambda_2(\mathbb T^2) > 0} . We will use the Fourier transform to “remove the torsion.” The point is that {S} and {T} , being shift operators, will act rather nicely on the Fourier basis.

We recall that if {m,n \in \mathbb N} and we define {\chi_{m,n} \in L^2(\mathbb T^2)} by {\chi_{m,n}(x,y) = \exp(2\pi i(mx+ny))} , then {\{\chi_{m,n}\}} forms an orthonormal Hilbert basis for {L^2(\mathbb T^2)} . In particular, every {f \in L^2(\mathbb T^2)} can be written uniquely as

\displaystyle  f = \sum_{m,n \in \mathbb Z} \hat f_{m,n} \chi_{m,n}\,,

where {\hat f_{m,n} = \langle f, \chi_{m,n}\rangle_{L^2}} . The Fourier transform is defined as a map {\mathcal F~:~L^2(\mathbb T^2) \rightarrow \ell^2(\mathbb Z^2)} , where {\mathcal F f(m,n) = \hat f_{m,n}} . In particular, {\mathcal F} is a linear isometry.

Define {S^*(f) = f \circ S} and {T^*(f) = f \circ T} . Then for any {m,n \in \mathbb Z} , we have

\displaystyle  S^*(\chi_{m,n}) = \chi_{m+n,n} \quad\textrm{ and }\quad T^*(\chi_{m,n}) = \chi_{m,n+m}.

In particular, for any {f \in L^2(\mathbb T^2)} , we have {\widehat{S^*(f)} = \sum_{m,n} \hat f_{m-n,n} \chi_{m,n}} and {\widehat{T^*(f)} = \sum_{m,n} \hat f_{m,n-m} \chi_{m,n}} . The final thing to note is that {\hat f(0,0) = \langle f, \chi_{0,0} \rangle = \int_{\mathbb T^2} f} . So now if we simply apply the Fourier transform (a linear isometry) to the expression in (1), we get a reformulation that {\lambda_2(\mathbb T^2)} is precisely

\displaystyle  \min_{g \in \ell^2(\mathbb Z^2)} \left\{ \frac{\sum_{z \in \mathbb Z^2} |g(z)-g(S(z))|^2 + |g(z)-g(T(z))|^2}{\|g\|^2_{\ell^2}}: g(0,0)=0 \right\}\,.

Here we have simply replaced {f} by {\mathcal F f} in (1), and then written {g = \mathcal F f} .

But now recall our initial infinite graph {G} on {\mathbb Z^2} . If we denote by {L_G} the Laplacian on {G} , then we can rewrite this as,

\displaystyle  \lambda_2(\mathbb T^2) = \min_{g \in \ell^2(\mathbb Z^2)} \left\{ \frac{\langle g, L_G g\rangle_{\ell^2}}{\|g\|^2_{\ell^2}}: g(0,0)=0 \right\}\,.

In other words, it is precisely the first Dirichlet eigenvalue on {G} , subject to the boundary condition {g(0,0)=0} .

But now the discrete Cheeger inequality tells us that

\displaystyle  \lambda_2(\mathbb T^2) \geq \frac1{2 d_{\max}} h^2,

where {h} 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 {h \geq 1/3} , yielding the desired lower bound on {\lambda_2(\mathbb T^2)} .

The Shocking Blue Green Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 60 other followers