CS294 Lecture 18: Margulis-Gabber-Galil Expanders

In which we present an algebraic construction of expanders.

1. The Marguli-Gabber-Galil Expanders

We present a construction of expander graphs due to Margulis, which was the first explicit construction of expanders, and its analysis due to Gabber and Galil. The analysis presented here includes later simplifications, and it follows an exposition of James Lee.

For every {n}, we construct graphs with {n^2} vertices, and we think of the vertex set as {{\mathbb Z}_n \times {\mathbb Z}_n}, the group of pairs from {\{0,\ldots,n-1\} \times \{ 0,\ldots,n-1\}} where the group operation is coordinate-wise addition modulo {n}.

Define the functions {S(a,b):= (a,a+b)} and {T(a,b):= (a+b,b)}, where all operations are modulo {n}. Then the graph {G_n(V_n,E_n)} has vertex set {V_n := ({\mathbb Z}/n{\mathbb Z} \times {\mathbb Z}/n{\mathbb Z})} and the vertex {(a,b)} is connected to the vertices

\displaystyle  (a+1,b),(a-1,b),(a,b+1),(a,b-1),S(a,b),S^{-1}(a,b),T(a,b),T^{-1}(a,b)

so that {G_n} is an 8-regular graph. (The graph has parallel edges and self-loops.)

We will prove that there is a constant {c>0} such that {\lambda_2(G_n) \geq c} for every {n}.

The analysis will be in four steps, and it will refer to certain infinite “graphs.”

We define an infinite family of graphs {R_n}, such that the vertex set of {R_n} is {({\mathbb R}/n{\mathbb Z} \times {\mathbb R}/n{\mathbb Z})}, that is, every vertex of {R_n} is a pair {(x,y)}, where {0 \leq x < n} and {0 \leq y <n}, and we think of {x} and {y} as elements of the group {{\mathbb R}/ n {\mathbb Z}} in which we do addition modulo {n}. Every vertex of {R_n} is connected to the vertices

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

and is 4-regular. For each of these graphs, we will define a “spectral gap” {\lambda_2(R_n)}; we put “spectral gap” in quotes because, although it is actually the second smallest eigenvalue of a Laplacian operator, we will define it purely formally as the minimum of a certain optimization problem.

We will also define the graph {Z}, whose vertex set is {{\mathbb Z} \times {\mathbb Z} - \{ (0,0 \}}, and such that each vertex {(a,b)} is connected to

\displaystyle  S(a,b),S^{-1}(a,b),T(a,b),T^{-1}(a,b)

so that {Z} is also {4}-regular. We will define a “spectral gap” {\lambda_1 (Z)}, again purely formally as the infimum of a certain expression, although it is the infimum of the spectrum of a certain Laplacian operator. We will also define an “edge expansion” {\phi(Z)} of {Z}.

The proof of the expansion of {G_n} will proceed by establishing the following four facts:

  1. {\lambda_2(G_n) \geq \frac 13 \lambda_2 (R_n)}
  2. {\lambda_2(R_n) \geq \lambda_1 (Z)}
  3. {\phi(Z) \leq \sqrt {2 \lambda_1(Z) } }
  4. {\phi(Z) \geq \frac 17}

The first step will be a discretization argument, showing that a test vector of small Rayleigh quotient for {G_n} can be turned into a test function of small Rayleigh quotient for {R_n}. The second step is the most interesting and unexpected part of the proof; we will not spoil the surprise of how it works. The third step is proved the same way as Cheeger’s inequality. The fourth step is just a careful case analysis.

2. First Step: The Continuous Graph {R_n}

Let {\ell_2([0,n)^2)} be set of functions {f: [0,n)^2 \rightarrow {\mathbb R}} such that {\int_{[0,n)^2} (f(x,y))^2 {\rm d} x {\rm d} y} is well defined and finite. Then we define the following quantity, that we think of as the spectral gap of {R_n}:

\displaystyle  \lambda_2(R_n) := \inf_{f\in \ell_2([0,n)^2) \ : \ \int_{[0,n)^2} f = 0} \frac {\int_{[0,n)^2} |f(x,y) - f(S(x,y))|^2 + |f(x,y) - f(T(x,y)) |^2 {\rm d} x {\rm d} y}{4 \int_{[0,n)^2} (f(x,y))^2 {\rm d} x {\rm d} y}

We could define a Laplacian operator and show that the above quantity is indeed the second smallest eigenvalue, but it will not be necessary for our proof.

We have the following bound.

Theorem 1 {\lambda_2(G_n) \geq \frac 1{3} \cdot \lambda_2(R_n)}.

Proof: Let {f} be the function such that

\displaystyle  \lambda_2(G) = \frac{\sum_{c\in {\mathbb Z}^2_n} |f( c ) - f( S( c )) |^2+|f( c ) - f( T( c )) |^2+|f( c ) - f( c+(0,1) ) |^2 + |f( c ) - f( c+(1,0)) |^2}{8\sum_{ c \in {\mathbb Z}_n^2}f^2( c )}

For a point {(x,y)\in [0,n)^2}, define {\lfloor x,y \rfloor := (\lfloor x \rfloor , \lfloor y \rfloor)}. We extend {f} to a function {\tilde f: [0,n)^2 \rightarrow {\mathbb R}} by defining

\displaystyle  \tilde f(z) := f( \lfloor z \rfloor )

This means that we tile the square {[0,n)^2} into unit squares whose corners are integer-coordinate, and that {\tilde f} is constant on each unit square, and it equals the value of {f} at the left-bottom corner of the square.

It is immediate to see that

\displaystyle  \int_{[0,n)^2} \tilde f^2(z) {\rm d} z = \sum_{c\in {\mathbb Z}_n^2} f^2 ( c )

and so, up to a factor of {2}, the denominator of the Rayleigh quotient of {f} is the same as the denominator of the Rayleigh quotient of {\tilde f}.

It remains to bound the numerators.

Observe that for every {z\in [0,1)^2}, we have that {\lfloor S(z) \rfloor} equals either {S( \lfloor z \rfloor)} or {S( \lfloor z \rfloor) +(0,1)}, and that {floor(T(z))} equals either {T( \lfloor z \rfloor )} or {T( \lfloor z \rfloor ) + (1,0)}. The numerator of the Rayleigh quotient of {\tilde f} is

\displaystyle  \sum_{c=(a,b)\in {\mathbb Z}_n^2} \int_{[a,a+1)\times [b,b+1)} | \tilde f(z)-\tilde f(S(z)) |^2 + | \tilde f(z) - \tilde f(T(z))|^2 {\rm d} z

\displaystyle  = \frac 12 \sum_{c\in {\mathbb Z}_n^2} |f( c) - f(S( c))|^2 +|f( c) - f(S( c)+(0,1))|^2 +|f( c) - f(T( c))|^2 +|f( c) - f(T( c)+(1,0)) |^2

because for a {(x,y)} randomly chosen in the square {[a,a+1)\times [b,b+1)}, there is probability {1/2} that {\lfloor x+y \rfloor = \lfloor x\rfloor + \lfloor y \rfloor} and probability {1/2} that {\lfloor x+y \rfloor = \lfloor x\rfloor + \lfloor y \rfloor+1}.

Now we can use the “triangle inequality”

\displaystyle  | \alpha - \beta|^2 \leq 2|\alpha-\gamma|^2 + 2|\gamma-\beta|^2

to bound the above quantity

\displaystyle  \begin{array}{l}\displaystyle \leq \frac 12 \sum_{c\in {\mathbb Z}_n^2} \displaystyle |f( c) - f(S( c))|^2 +\\ \displaystyle 2|f( c) - f(c+(0,1)) |^2+ 2|f( c+ (0,1)) - f(S( c)+(0,1))|^2 +\\ \displaystyle |f( c) - f(T( c))|^2 +\\ \displaystyle 2|f( c) - f(c+(1,0)) |^2+ 2|f( c+(1,0)) - f(T( c)+(1,0)) |^2\end{array}

which simplifies to

\displaystyle  = \frac 12 \sum_{c\in {\mathbb Z}_n^2} 3 |f( c) - f(S( c))|^2 + 3 |f( c) - f(T( c))|^2 + 2|f( c) - f(c+(0,1)) |^2 + 2|f( c) - f(c+(1,0)) |^2

which is at most {3/2} times the numerator of the Rayleigh quotient of {f}. \Box

3. Second Step: The Countable Graph

We now define the graph {Z} of vertex set {{\mathbb Z} \times {\mathbb Z}-\{ (0,0) \}}, where each vertex {(a,b)} is connected to

\displaystyle  (a,a+b), (a,a-b),(a+b,a),(a-b,a)

Note

For a {d}-regular graph {G=(V,E)} with an countably infinite set of vectors, define {\ell_2(V)} to be the set of functions {f: V \rightarrow {\mathbb R}} such that {\sum_{v\in V} f^2(v)} is finite, and define the smallest eigenvalue of {G} as

\displaystyle  \lambda_1(G) := \inf_{f\in \ell_2(V)} \frac{\sum_{(u,v)\in V} |f(u)-f(v)|^2}{d \sum_v f^2(v)}

So that

\displaystyle  \lambda_1(Z):= \inf_{f\in \ell_2({\mathbb Z} \times {\mathbb Z}-\{(0,0)\})} \frac{\sum_{a,b} |f(a,b)-f(a,a+b)|^2 + |f(a,b)-f(a+b,a)|^2 }{4\sum_{a,b} f^2(a,b)}

We want to show the following result.

Theorem 2 For every {n}, {\lambda_2(R_n) \geq \lambda_1(Z)}.

Proof: This will be the most interesting part of the argument. Let {f\in \ell_2([0,n)^2)} be any function such that {\int f = 0}, we will show that the Fourier transform {\hat f} of {f} has a Rayleigh quotient for {Z} that is at most the Rayleigh quotient of {f} for {R_n}.

First, we briefly recall the definitions of Fourier transforms. If {f: [0,n)^2 \rightarrow {\mathbb R}} is such that

\displaystyle  \int_{z\in [0,n)^2} f^2(z) {\rm d} z < \infty

then we can write the linear combination

\displaystyle  f(z) =\sum_{c \in {\mathbb Z} \times {\mathbb Z}} \hat f( c) \cdot \chi_c(z)

where the basis functions are

\displaystyle  \chi_{a,b}(x,y) = \frac 1n e^{2\pi i \cdot(ax + by)}

and the coefficients are

\displaystyle  \hat f( c) = \langle f, \chi_{a,b} \rangle := \int_{[0,n)^2} f(z) \chi_c(z) {\rm d} z

The condition {\int f = 0} gives

\displaystyle  \hat f(0,0) = 0

and the Parseval identity gives

\displaystyle  \sum_{c\neq (0,0)} \hat f^2(c ) = \sum_c \hat f^2( c) = \int f^2(z) {\rm d} z

and so we have that the denominator of the Rayleigh quotient of {f} for {R_n} and of {\hat f} for {Z} As usual, the numerator is more complicated.

We can break up the numerator of the Rayleigh quotient of {f} as

\displaystyle  \int s^2(z) {\rm d} z + \int t^2(z) {\rm d} z

where {s(z):= f(z) - f(S(z))} and {t(z):= f(z)-f(T(z)) }, and we can use Parseval’s identity to rewrite it as

\displaystyle  \sum_c \hat s^2( c) + \hat t^2(c )

\displaystyle  = \sum_c | \hat f( c) - \widehat{(f\circ S)}( c) |^2 + |\hat f( c) - \widehat{(f \circ T)} ( c)|^2

The Fourier coefficients of the function {(f\circ S) (z)= f(S(z))} can be computed as

\displaystyle  \widehat{(f\circ S)}( a,b) = \frac 1n \int f(S(x,y)) e^{2\pi i ( ax+by)}

\displaystyle  = \frac 1n \int f(x,x+y) e^{2\pi i ( ax+by)}

\displaystyle  = \frac 1n \int f(x,y') e^{2\pi i ( ax+by'-bx)}

\displaystyle  = \hat f (a-b,b)

where we used the change of variable {y' \leftarrow x+y}.

Similarly, {\widehat{(f \circ T)}(a,b) = \hat f(a,b-a)}. This means that the numerator of the Rayleigh quotient of {f} for {R_n} is equal to the numerator of the Rayleigh quotient of {\hat f} for {Z}. \Box

4. Third Step: A Cheeger Inequality for countable graphs

Define the edge expansion of a {d}-regular graph {G=(V,E)} with a countably infinite set of vertices as

\displaystyle  \phi(G) = \inf_{A\subseteq V, A \ {\rm finite}} \ \frac{E(A,\bar A)}{d|A|}

Note that the edge expansion can be zero even if the graph is connected.

Theorem 3 (Cheeger inequality for countable graphs) For every graph {G=(V,E)} with a countably infinite set of vertices we have

\displaystyle  \phi(G) \leq \sqrt{2 \cdot \lambda_1(G)}

Proof: This is similar to the proof for finite graphs, with the simplification that we do not need to worry about constructing a set containing at most half of the vertices.

Let {f \in \ell_2({\mathbb Z}^2)} be any function. We will show that {\phi} is at most {\sqrt{2r}} where

\displaystyle  r:= \frac{\sum_{(u,v) \in E} |f(u)-f(v)|^2}{d\sum_{v\in V} f^2(v)}

is the Rayleigh quotient of {f}.

For every threshold {t\geq t_{\min} := \inf_{v\in V} f^2(v)}, define the set {S_t\subseteq V} as

\displaystyle  S_t := \{ v: f^2(v) > t \}

and note that each set is finite because {\sum_v f^2(v)} is finite. We have, for {t> t_{\min}},

\displaystyle  \phi(G) \leq \frac{E(S_t,\bar S_t)}{d |S_t|}

and, for all {t\geq 0}

\displaystyle  |S_t| \cdot \phi(G) \leq d E(S_t,\bar S_t)

Now we compute the integral of the numerator and denominator of the above expression, and we will find the numerator and denominator of the Rayleigh quotient {r}.

\displaystyle  \int_{0}^\infty |S_t| {\rm d} t = \sum_{v\in V} \int_{0}^\infty I_{f^2(v) > t} {\rm d} t = \sum_{v\in V} f^2(v)

and

\displaystyle  \int_{0}^\infty E(S_t,\bar S_t) {\rm d} t = \sum_{(u,v)\in E} \int_0^\infty I_{t \ {\rm between} \ f^2(u),f^2(v)} {\rm d} t = \sum_{(u,v)} |f^2(u)-f^2(v)|

Which means

\displaystyle  \phi \leq \frac { \sum_{u,v} |f(u)-f(v)|^2 }{d\sum_v f^2(v)}

Now we proceed with Cauchy Schwarz:

\displaystyle  \sum_{(u,v)\in E} |f^2(u)-f^2(v)|

\displaystyle  = \sum_{(u,v)\in E} |f(u)-f(v)| \cdot | f(u) + f(v) |

\displaystyle  \leq \sqrt{\sum_{(u,v)\in E} |f(u)-f(v)|^2 }\cdot \sqrt{\sum_{(u,v)\in E} |f(u) + f(v)|^2 }

\displaystyle  \leq \sqrt{\sum_{(u,v)\in E} |f(u)-f(v)|^2 }\cdot \sqrt{\sum_{(u,v)\in E} 2f^2(u) + 2f^2(v) }

\displaystyle  = \sqrt{\sum_{(u,v)\in E} |f(u)-f(v)|^2 }\cdot \sqrt{\sum_{v\in V} 2 df(v)^2 }

And we have

\displaystyle  \phi \leq \frac { \sqrt {\sum_{(u,v)\in E} |f(u)-f(v)|^2 } \cdot \sqrt{2d}} { d \sqrt{\sum_{v\in V} f(v)^2} } = \sqrt{2 \cdot r}

\Box

5. Expansion of {Z}

After all these reductions, we finally come to the point where we need to prove that something is an expander.

Theorem 4 {\phi(Z) \geq \frac 17}

Proof: Let {A} be a finite subset of {{\mathbb Z} \times {\mathbb Z} - \{ (0,0 \}}.

Let {A_0} be the set of elements of {A} that have one 0 coordinate. Let {A_1,A_2,A_3,A_4} be the set of elements of {A} with nonzero coordinate that belong to the 1st, 2nd, 3rd and 4th quadrant. (Starting from the quadrant of points having both coordinates positive, and numbering the remaining ones clockwise.)

Claim 1 {E(A-A_0,\bar A) \geq |A - A_0| = |A| - |A_0|}.

Proof: Consider the sets {S(A_1)} and {T(A_1)}; both {S()} and {T()} are permutations, and so {|S(A_1)|=|T(A_1)|=|A_1|}. Also, {S(A_1)} and {T(A_1)} are disjoint, because if we had {(a,a+b) = (a'+b',b')} then we would have {b=-a'} while all the coordinates are strictly positive. Finally, {S(A_1)} and {T(A_1)} are also contained in the first quadrant, and so at least {|A_1|} of the edges leaving {A_1} lands outside {A}. We can make a similar argument in each quadrant, considering the sets {S^{-1}(A_2)} and {T^{-1}(A_2)} in the second quadrant, the sets {S(A_3)} and {T(A_3)} in the third, and {S^{-1}(A_4)} and {T^{-1}(A_4)} in the fourth. \Box

Claim 2 {E(A_0,\bar A) \geq 4|A_0| - 3|A-A_0| = 7|A_0| - 3|A|}

Proof: All the edges that have one endpoint in {A_0} have the other endpoint outside of {A_0}. Some of those edges, however, may land in {A-A_0}. Overall, {A-A_0} can account for at most {4|A-A_0|} edges, and we have already computed that at least {|A-A_0|} of them land into {\bar A}, so {A-A_0} can absorb at most {3|A-A_0|} of the outgoing edges of {A_0}. \Box

Balancing the two equalities (adding the first plus {1/7} times the second) gives us the theorem. \Box

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s