Let $\Gamma \, zz\, G$ denote the zig-zag product of graphs $\Gamma$ and $G$. Reingold, Vadhan, and Wigderson proved that the second largest eigenvalue of the normalized adjacency matrix of the zig-zag product satisfies $$ \lambda(\Gamma\, zz\, G)\leq \lambda(\Gamma) + \lambda(G). $$ This leads to a simple construction of expanders: given a graph $\Gamma$ with sufficiently small $\lambda(\Gamma)$, the sequence $$ \Gamma_n=\Gamma_{n-1}^2 \, zz\, \Gamma $$ is an expanding family, where $\Gamma^2$ is the square of the graph. Basically, the zig-zag product reduces the degree, while the squaring reduces the second eigenvalue.

Question: Is it possible to get expanders using just the iterated zig-zag product without squaring, i.e., is there a graph $\Gamma$ such that $\Gamma_n=\Gamma_{n-1} \, zz\, \Gamma$ is an expanding family? Or the zig-zag product necessary increases the second eigenvalue?


Well, the zig-zag product necessarily doesn't lower the second eigenvalue. Since if you look at the proof, an orthogonal decomposing is possible. The first space corresponds to the eigenspace of A(H), and the second one to A(G) (let look at GzzH). It is easier to take the proof from here: www.wisdom.weizmann.ac.il/~dinuri/courses/18-HDX/lect02.pdf

Thus taking the second eigenvector of either G or H leads to this result.

It can still theoretically keep the maximal second eigenvalue. But it is outside the reach of the current proof.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.