<p>The proof of Theorem 4.1 states that:</p>

<blockquote>
  <p>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. [...]</p>
  
  <p>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}$.</p>
</blockquote>

<p>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$.</p>

<p>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?</p>

CC BY-SA 3.0
2014-12-30T13:13:55.460Z
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
CC BY-SA 3.0
2014-12-30T13:26:32.140Z
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
CC BY-SA 3.0
2014-12-30T15:14:46.313Z
Yes, that is exactly why I missed in my analysis. Thanks for your effort :-)
Dave
CC BY-SA 3.0
2014-12-28T20:59:43.643Z
2014-12-28T20:59:43.643Z
Yuval Filmus
<p>I'm currently working on <a href="http://research.microsoft.com/pubs/148550/sl.pdf" rel="nofollow" title="SL = L">this</a> 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. </p>

<p>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$. </p>

<p>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?</p>

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

<p>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.</p>

<p><strong>EDIT:</strong></p>

<p>I think I found the trick. Proposition 2.2 states that if $\lambda &lt; 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).</p>

<graph-theory><graph-algorithms><derandomization>
Why does the transformation in the proof for SL=L preserve connectedness of s and t?
Dave
# Why does the transformation in the proof for SL=L preserve connectedness of s and t?

(Asked by: username_0 on 2014-12-28)

I'm currently working on [this](http://research.microsoft.com/pubs/148550/sl.pdf "SL = L") 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).

**Tags:** graph-theory, graph-algorithms, derandomization

---

## 1 answers

### Answer by username_1 on 2014-12-28. Score: 5 | Accepted answer

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?

> **Comments:**
> **username_0**: 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).  
> **username_1**: 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.  
> **username_0**: Yes, that is exactly why I missed in my analysis. Thanks for your effort :-)  

---

