Introduction to Zig-Zag
Starting September 21st, Erin introduced us to the Zig-Zag product as a means of expander construction.
In leading up to the construction, we first defined a rotation map of a graph G = (V,E) to be a function from pairs (v, i) to (w, j) where v,w ∈ V and the i-th incident edge to v leads to w, and it leads through the j-th incident edge to w. Further, we will use the notation that G is a (N, D, λ)-graph if G has N-vertices, is D-regular, and has second largest eigenvalue in absolute value, λ = max α ⊥ 1n | ⟨ α, M α ⟩ | / ⟨ α, α ⟩.
Next we explored the results of squaring and the tensor product of a graph. Namely, we considered Gt for G an (N,D, λ)-graph. Proposition 1 stated that Gt is an (N, Dt, λt)-graph. To see this, consider the normalized adjacenty matrix for Mt for Gt. Then Mtu = λtu from repeated iterations of Mu = λu.
We then defined the tensor product G of G1 and G2 where G1 is N1-vertex D1-regular and G2 is N2-vertex D2-regular to be a N1 · N2-vertex D1 · D2-regular graph such that the rotation map of the tensor product G is
RG( (v,w), (i,j) ) = ( (v',w'), (i',j') ) where v ∈ G1, w ∈ G2, i ≤ D1, j ≤ D2 and RG1(v,i) = (v',i'), RG2(w,j) = (w',j')
This is a replacement of each vertex in G1 with a copy G2 and connecting all vertices based on the vertices they represent in G1.
As the graph can be represented by the adjacency matrix, we consider the tensors effect on the two adjacency matricies A and B. If we let Au = λ1u and Bv = λ2v and let C be the tensor of A and B and let w be the tensor of u and v, then the product of Cw = λ1λ2w. We see this by considering the tensor of Au and Bv, extracting the appropriate position (i,j) in the resulting matrix.
Now, we consider the effect of the tensor. We considered Proposition 1 which states,
Let G1 be a (N1, D1 λ1) and G2 be a (N2, D2, λ2) graph. Then the tensor of the two is (N1 · N2, D1 · D2, max{ λ1, λ2 }).
To see this, consider the eigenvalues of the normalized adjacency matrix of the tensor. These eigenvalues depend on the normalized adjancency matricies of the original graphs G1 and G2. As the result of the tensoring of these normalized adjacency matricies results in a largest eigenvalue of 1, the second largest value is either λ1 or λ2.
From here we defined the Zig-Zag product. Consider G1 a D1-regular graph on N-vertices and G2 a D2-regular graph on D1-vertices. Replacing each vertex in G1 with a copy of G2, we create an edge in this resulting graph on [N] × [D1] by adding an edge for every path of length 3 of the following form:
(1) Take a random step inside a copy of G2
(2) Take an edge inside G1 which represents the jump from the current embedded G2 to another.
(3) Take a random step inside the copy of G2
Thus, an edge between vertex i and j exists if there is some verticies i' and j' such that there is an edge between i and i' in am embedded copy of G2, an edge in the tensor product between i' and j', and an edge in an embedded copy of G2 between j' and j.
This can be expressed formally via the rotation map of G, G1, and G2 as follows:
Let v ∈ [N], k ∈ [D1], and i,j ∈ [D2].
Let (k', i') = RG2(k,i), the first step within a cloud.
Let (w, l') = RG1(v, k), the step in G1.
Let (l, j') = RG2(l' j), the second step within a cloud.
Then RG( (v,k), (i,j)) = ((w,l), (j',i')).
The point of exploring the zig-zag product is that if the two graphs G1 and G2 are good expanders we expect that their product G will also be a good expander.
To this end, we have Theorem 4 which follows. Let G1 be a (N, D1, λ1) graph and G2 be a (D1, D2, λ2) graph. Then the zig-zag G of G1 and G2 is (N · D1, D22, f( λ1, λ2 )) where f( λ1, λ2 ) ≤ λ1 + λ2 + λ22 and f( λ1, λ2 ) < 1 if λ1, λ2 < 1.
Intuitively, we can think of the construction as trying evenly distribute entropy thoughout the resulting graph. We claim that a step in the zig-zag results in a more uniform distribution of the entropy given that the entropy was not already uniformly distributed. To see this we consider two cases based on the initial probability distribution.
If the distributions are not too close to uniform then the random first step used to produce an edge in the zig-zag contributes some amount of entropy. As the deterministic step across clouds and the following random step cannot decrease the contribution from step one, some amount of reallocation is done making the graph entropy more uniform.
If instead the entropy is close to uniform then the first step is unproductive. However the deterministic step is now effectively random due to the uniformity of the choice of vertex in the cloud and so a contribution is still made for the resulting step in the zig-zag.
The proof follows along the lines of considering any action in terms of its component breakdown into the above two cases, making use of the above propositions. While I believe I understand the intuition behind the idea, the algebraic manipulation seems a bit tedious for this post.
In leading up to the construction, we first defined a rotation map of a graph G = (V,E) to be a function from pairs (v, i) to (w, j) where v,w ∈ V and the i-th incident edge to v leads to w, and it leads through the j-th incident edge to w. Further, we will use the notation that G is a (N, D, λ)-graph if G has N-vertices, is D-regular, and has second largest eigenvalue in absolute value, λ = max α ⊥ 1n | ⟨ α, M α ⟩ | / ⟨ α, α ⟩.
Next we explored the results of squaring and the tensor product of a graph. Namely, we considered Gt for G an (N,D, λ)-graph. Proposition 1 stated that Gt is an (N, Dt, λt)-graph. To see this, consider the normalized adjacenty matrix for Mt for Gt. Then Mtu = λtu from repeated iterations of Mu = λu.
We then defined the tensor product G of G1 and G2 where G1 is N1-vertex D1-regular and G2 is N2-vertex D2-regular to be a N1 · N2-vertex D1 · D2-regular graph such that the rotation map of the tensor product G is
RG( (v,w), (i,j) ) = ( (v',w'), (i',j') ) where v ∈ G1, w ∈ G2, i ≤ D1, j ≤ D2 and RG1(v,i) = (v',i'), RG2(w,j) = (w',j')
This is a replacement of each vertex in G1 with a copy G2 and connecting all vertices based on the vertices they represent in G1.
As the graph can be represented by the adjacency matrix, we consider the tensors effect on the two adjacency matricies A and B. If we let Au = λ1u and Bv = λ2v and let C be the tensor of A and B and let w be the tensor of u and v, then the product of Cw = λ1λ2w. We see this by considering the tensor of Au and Bv, extracting the appropriate position (i,j) in the resulting matrix.
Now, we consider the effect of the tensor. We considered Proposition 1 which states,
Let G1 be a (N1, D1 λ1) and G2 be a (N2, D2, λ2) graph. Then the tensor of the two is (N1 · N2, D1 · D2, max{ λ1, λ2 }).
To see this, consider the eigenvalues of the normalized adjacency matrix of the tensor. These eigenvalues depend on the normalized adjancency matricies of the original graphs G1 and G2. As the result of the tensoring of these normalized adjacency matricies results in a largest eigenvalue of 1, the second largest value is either λ1 or λ2.
From here we defined the Zig-Zag product. Consider G1 a D1-regular graph on N-vertices and G2 a D2-regular graph on D1-vertices. Replacing each vertex in G1 with a copy of G2, we create an edge in this resulting graph on [N] × [D1] by adding an edge for every path of length 3 of the following form:
(1) Take a random step inside a copy of G2
(2) Take an edge inside G1 which represents the jump from the current embedded G2 to another.
(3) Take a random step inside the copy of G2
Thus, an edge between vertex i and j exists if there is some verticies i' and j' such that there is an edge between i and i' in am embedded copy of G2, an edge in the tensor product between i' and j', and an edge in an embedded copy of G2 between j' and j.
This can be expressed formally via the rotation map of G, G1, and G2 as follows:
Let v ∈ [N], k ∈ [D1], and i,j ∈ [D2].
Let (k', i') = RG2(k,i), the first step within a cloud.
Let (w, l') = RG1(v, k), the step in G1.
Let (l, j') = RG2(l' j), the second step within a cloud.
Then RG( (v,k), (i,j)) = ((w,l), (j',i')).
The point of exploring the zig-zag product is that if the two graphs G1 and G2 are good expanders we expect that their product G will also be a good expander.
To this end, we have Theorem 4 which follows. Let G1 be a (N, D1, λ1) graph and G2 be a (D1, D2, λ2) graph. Then the zig-zag G of G1 and G2 is (N · D1, D22, f( λ1, λ2 )) where f( λ1, λ2 ) ≤ λ1 + λ2 + λ22 and f( λ1, λ2 ) < 1 if λ1, λ2 < 1.
Intuitively, we can think of the construction as trying evenly distribute entropy thoughout the resulting graph. We claim that a step in the zig-zag results in a more uniform distribution of the entropy given that the entropy was not already uniformly distributed. To see this we consider two cases based on the initial probability distribution.
If the distributions are not too close to uniform then the random first step used to produce an edge in the zig-zag contributes some amount of entropy. As the deterministic step across clouds and the following random step cannot decrease the contribution from step one, some amount of reallocation is done making the graph entropy more uniform.
If instead the entropy is close to uniform then the first step is unproductive. However the deterministic step is now effectively random due to the uniformity of the choice of vertex in the cloud and so a contribution is still made for the resulting step in the zig-zag.
The proof follows along the lines of considering any action in terms of its component breakdown into the above two cases, making use of the above propositions. While I believe I understand the intuition behind the idea, the algebraic manipulation seems a bit tedious for this post.
posted by Phillip at
2:55 PM
0 Comments:
Post a Comment
<< Home