8
$\begingroup$

I am reading the paper introducing zigzag products of expander graphs (https://arxiv.org/abs/math/0406038). The paper mentions the following observation in the introduction:

Moreover, the variational definition of the second eigenvalue better captures the symmetry of the zig and zag steps (and gives a better bound than what can be obtained from this asymmetric intuition).

However, by following the asymmetric intuition (that $\tilde{A}$ sends most of the mass of a parallel vector to the perpendicular subspace), I am able to obtain a slightly better bound than the paper: I am able to show that the zigzag product of a $(N, D, \lambda_1)$ graph and $(D, D_2, \lambda_2)$ graph has second eigenvalue $\leq \lambda_1 + \lambda_2 - \lambda_1\lambda_2$, while the paper shows a bound of $\lambda_1 + 2\lambda_2 + \lambda_2^2$.

Is my proof correct? Pointing out errors will be appreciated. (Borrowing notiations from the paper: $x^{\parallel}$ denotes projection of $x$ to the parallel subspace, consisting of vectors uniform on each cloud, and $x^{\perp}$ denotes the projection to its orthogonal complement)

Let $G$ be a $(N, D, \lambda_1)$ expander, and let $H$ be a $(D, D_2, \lambda_2)$ expander. We want to upper bound the second eigenvalue of $G _{z} H$.

We want to upper bound $||Mx||_2$ subject to $||x||_2=1, x \perp 1_{V_1 \otimes V_2}$ where $M= \tilde{H}\tilde{G}\tilde{H}$, where $\tilde{H}= I_{V_1} \otimes H$ and $\tilde{G}$ is the permutation matrix for the permutation $(v,i) \rightarrow \text{Rot}(v,i) $. Write $x = x^{\parallel} + x^{\perp} $. By triangle inequality $||Mx|| \leq ||Mx^{\parallel}|| + ||Mx^{\perp}||$. We have $$||\tilde{H}x^{\perp}|| \leq \lambda_2 ||x^{\perp}|| \implies ||\tilde{H}\tilde{G}\tilde{H}x^{\perp}|| \leq ||Hx^{\perp}|| \leq \lambda_2 ||x^{\perp}|| $$

Now we have to upper bound $||\tilde{H}\tilde{G}\tilde{H}x^{\parallel}|| = ||\tilde{H}\tilde{G}x^{\parallel}||$. Decompose $\tilde{G}x^{\parallel} = (Gx^{\parallel})^{\parallel} + (Gx^{\parallel})^{\perp}$. We have $$ ||\tilde{H}Gx^{\parallel}|| \leq ||\tilde{H}(\tilde{G}x^{\parallel})^{\parallel}|| + ||\tilde{H}(\tilde{G}x^{\parallel})^{\perp}||\leq ||(\tilde{G}x^{\parallel})^{\parallel}|| + \lambda_2 ||(\tilde{G}x^{\parallel})^{\perp}|| $$

It is easy to see $x^{\parallel} = \alpha \otimes 1_{V_2}$ for some vector $\alpha$ with $\alpha \perp 1_{V_1}$ and $||\alpha|| = ||x^{\parallel}||$. Easy computations (as done in the paper) show that $$ || \tilde{G} x^{\parallel}|| = ||G \alpha|| \leq \lambda_1|| \alpha|| = \lambda_1 ||x^{\parallel}||$$ Also, since $\tilde{G}$ is a permutation, $$ ||\tilde{G}x^{\parallel}|| = ||x^{\parallel}|| \implies ||(\tilde{G}x^{\parallel})^{\parallel}|| + || (\tilde{G}x^{\parallel})^{\perp}|| = ||x^{\parallel}||$$

Let $c= ||x^{\parallel}|| = ||\tilde{G}x^{\parallel}||, a= ||(\tilde{G} x^{\parallel})^{\parallel}|| , b= ||(\tilde{G}x^{\parallel})^{\perp}||$. We have $c=a+b$ and we want to upper bound $a + \lambda_2 b$, given that $a \leq \lambda_1 c$.

Since $b \geq (1-\lambda_1)c$, we have

$$ a + \lambda_2 b = c - (1-\lambda_2)b \leq (1 - (1-\lambda_1)(1-\lambda_2))c = (\lambda_1 + \lambda_2 - \lambda_1\lambda_2)c$$

So we have $$ ||\tilde{H}Gx^{\parallel}|| \leq (\lambda_1 + \lambda_2 - \lambda_1 \lambda_2) ||x^{\parallel}||$$ and putting it all together, we get that $$ |\tilde{H}\tilde{G}\tilde{H}x|| \leq \lambda_2 ||x^{\perp}|| + (\lambda_1 + \lambda_2 - \lambda_1 \lambda_2) ||x^{\parallel}|| \leq (\lambda_1 + \lambda_2 - \lambda_1 \lambda_2)||x||$$ In the last step we used the fact that $\lambda_2 \leq \lambda_2 + \lambda_1 - \lambda_1 \lambda_2$.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.