# Why does the transformation in the proof for SL=L preserve connectedness of s and t?

I'm currently working on this paper showing that $\mathcal{SL} = \mathcal{L}$. But I keep wondering how the transformation $\tau$ in definition 3.1 preserves the connectivity of $s$ and $t$. $\tau$ consists of several applications of the zig-zag-product and powering.

They show in Lemma 3.2 that if $s$ and $t$ aren't connected in $G$, then all nodes induced by $s$ arent't connected to any node induced by $t$. But they don't show that if $s$ and $t$ were connected in $G$ that $s'$ and $t'$, as defined in the proof of the theorems 4.1 and 4.2, are connected in $\tau(G,H)$ for some expander graph $H$.

One can easily find examples were the zig-zag-product or powering destroys connectivity of nodes. So why is here no argumentation needed on why $s'$ and $t'$ will be connected if $s$ and $t$ were? Am I missing something?

I assume that the proof itself is correct since the first versions of the paper were published more than ten years ago.

PS: I'm not 100% sure whether this is a research level question. But I think that it will be hard to get an answer in one of the other forums since it is kind of special question.

EDIT:

I think I found the trick. Proposition 2.2 states that if $\lambda < 1$ is achieved there is a path of some length for every pair of verticies $s$ and $t$. Thus by showing that the spectral expansion of the nodes induced by the connected component of s is smaller than $1/2$ it is also shown, that the connection isn't lost (if there was one).

The proof of Theorem 4.1 states that:

Let $S$ be the connected component of $G$, such that $s \in S$. By the arguments above, $S \times [N]$ is a connected component of $G_{\mathrm{reg}}$, and $G_{\mathrm{reg}}|_{S\times [N]}$ is non-bipartite. [...]

By Lemma 3.2 and Lemma 3.3, we have that $\lambda(G_{\exp}|_{S\times[N]\times([D^{16}_{\mathbf{e}}])^\ell}) \leq 1/2$. In particular, we have that $S\times[N]\times([D^{16}_{\mathbf{e}}])^\ell$ is a connected component of $G_{\exp}$.

In particular, if $t \in S$ then both $s'$ and $t'$ belong to the connected component $S\times[N]\times([D^{16}_{\mathbf{e}}])^\ell$.

Lemma 3.2 only works when $G$ is non-bipartite and $\lambda(H) \leq 1/2$. Perhaps one of these conditions wasn't satisfied in your examples?

• Lemma 3.2 just states $\lambda(\tau(G,H)) \leq 1/2$ under these circumstances. Also $G_{exp}$ is created by $\tau$. But I think I found a solution (see edit of my post). – Dave Dec 30 '14 at 13:13
• If the graph is disconnected then there is no spectral gap, and so $\lambda = 1$. So $\lambda < 1$ implies that the graph is connected. That's also what you wrote in your update. – Yuval Filmus Dec 30 '14 at 13:26
• Yes, that is exactly why I missed in my analysis. Thanks for your effort :-) – Dave Dec 30 '14 at 15:14