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 1 Let 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.
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 4 For 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 5 Let 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 7 If 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
It remains to prove that . If we let be the adjacency matrix of , then we can see that
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: