I have been fiddling with the ZigZag product and constructing expanders for a while now. I was wondering if the following definition of a ZigZag product is the same as the original article:
Lets first denote the graphs as $G_1, G_2$, where we have $|V_{G_2}|=deg(G_1)$. Construct the "simple ZigZag product" as defined by the original article:
- Replace every $v \in V_1$ with the complete graph $G_2$ (including it's edges).
- Connect the clouds $(v,w)$ by an edge $( (v,i), (w,j) ) \iff (w,v) \in E_1$ and the edge $(v,w)$ is the i'th edge leaving $v$ and the j'th edge leaving $w$.
This will result with the graph $SZ$ where $|V_{SZ}|=|V_{G_2}| \cdot |V_{G_1}|$ and $deg(S_{SZ})=deg(G_2)+1$. Now for creating the actual graph do the following:
- Compute all shortest paths (using Floyd-Warshall for example) over the graph $SZ$.
- connect every two nodes $(v,i)$ and $(w,j)$ if: $v \neq w$ and $dist((v,i),(w,j))=3$.
The second step (as I see it) is just the zig-zag step, we must be 3 hops away from every one of our neighbors (and they must be on different clouds).
Does this seem right to you?
Thanks!