*In which we define and analyze the zig-zag graph product.*

**1. Replacement Product and Zig-Zag Product **

In the previous lecture, we claimed it is possible to “combine” a -regular graph on vertices and a -regular graph on vertices to obtain a -regular graph on vertices which is a good expander if the two starting graphs are. Let the two starting graphs be denoted by and respectively. Then, the resulting graph, called the *zig-zag product* of the two graphs is denoted by .

Using to denote the eigenvalue with the second-largest absolute value for a graph , we claimed that if and , then . In this lecture we shall describe the construction for the zig-zag product and prove this claim.

**2. Replacement product of two graphs **

We first describe a simpler product for a “small” -regular graph on vertices (denoted by ) and a “large” -regular graph on vertices (denoted by ). Assume that for each vertex of , there is some ordering on its neighbors. Then we construct the replacement product (see figure) as follows:

- Replace each vertex of with a copy of (henceforth called a
*cloud*). For , let denote the vertex in the cloud. - Let be such that is the -th neighbor of and is the -th neighbor of . Then . Also, if , then .

Note that the replacement product constructed as above has vertices and is -regular.

**3. Zig-zag product of two graphs **

Given two graphs and as above, the zig-zag product is constructed as follows (see figure):

- The vertex set is the same as in the case of the replacement product.
- if there exist and such that , and are in i.e. can be reached from by taking a step in the first cloud, then a step between the clouds and then a step in the second cloud (hence the name!).

It is easy to see that the zig-zag product is a -regular graph on vertices.

Let be the normalized adjacency matrix of . Using the fact that each edge in is made up of three steps in , we can write as , where

And if is the -th neighbor of and is the -th neighbor of , and otherwise.

Note that is the adjacency matrix for a matching and is hence a permutation matrix.

**4. Preliminaries on Matrix Norms **

Recall that, instead of bounding , we will bound the following parameter (thus proving a stronger result).

Definition 1Let be the normalized adjacency matrix of a graph , and be its eigenvalues with multiplicities. Then we use the notation

The parameter has the following equivalent characterizations.

Fact 2

Another equivalent characterization, which will be useful in several contexts, can be given using the following matrix norm.

Definition 3 (Spectral Norm)The spectral norm of a matrix is defined as

If is symmetric with eigenvalues , then the spectral norm is . Note that is indeed a norm, that is, for every two square real matrices we have and for every matrix and scalar we have . In addition, it has the following useful property:

Fact 4For every two matrices we have

*Proof:* For every vector we have

where the first inequality is due to the fact that for every vector , and the second inequality is due to the fact that . So we have

We can use the spectral norm to provide another characterization of the parameter of the normalized adjacency matrix of a graph.

Lemma 5Let be a regular graph and be its normalized adjacency matrix. Then

where is the matrix with a 1 in each entry.

*Proof:* Let be the eigenvalues of and , , , a corresponding system of orthonormal eigenvector. Then we can write

Noting that , we have

and so is also a system of eigenvectors for , with corresponding eigenvalues , meaning that

The above lemma has several applications. It states that, according to a certain definition of distance, when a graph is a good expander then it is close to a clique. (The matrix is the normalized adjacency matrix of a clique with self-loops.) The proof of several results about expanders is based on noticing that the result is trivial for cliques, and then on “approximating” the given expander by a clique using the above lemma.

We need one more definition before we can continue with the analysis of the zig-zag graph product.

Definition 6 (Tensor Product)Let and be two matrices. Then is a matrix whose rows and columns are indexed by pairs such that

For example is a block-diagonal matrix in which every block is a copy of .

**5. Analysis of the Zig-Zag Product **

Suppose that and are identical cliques with self-loops, that is, are both -regular graphs with self-loops. Then the zig-zag product of and is well-defined, because the degree of is equal to the number of vertices of . The resulting graph is a -regular graph with vertices, and an inspection of the definitions reveals that is indeed a clique (with self-loops) with vertices.

The intuition for our analysis is that we want to show that the zig-zag graph product “preserves” distances measured in the matrix norm, and so if is close (in matrix norm) to a clique and is close to a clique, then is close to the zig-zag product of two cliques, that is, to a clique. (Strictly speaking, what we just said does not make sense, because we cannot take the zig-zag product of the clique that is close to and of the clique that is close to, because they do not have the right degree and number of vertices. The proof, however, follows quite closely this intuition.)

Theorem 7If and , then

*Proof:* Let be the normalized adjacency matrix of , and let be a unit vector such that and

Recall that we defined a decomposition

where is a permutation matrix, and . Let us write , then . Let us call and .

First, we argue that the matrix norm of is small. Take any vector and write is as , where, for each , is the -dimensional restriction of to the coordinates in the cloud of . Then

and so we have

Then we have

and so, using the triangle inequality and the property of the matrix norm, we have

where

It remains to prove that . If we let be the adjacency matrix of , then we can see that

That is,

Finally, we write , where is the -dimensional vector of entries corresponding to the cloud of , we call , and we note that, by Cauchy-Schwarz:

The final calculation is:

## 1 comment

Comments feed for this article

December 7, 2011 at 5:24 am

walmartgilbert arenas drew brees