5
$\begingroup$

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).

$\endgroup$
4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Dave Dec 30 '14 at 13:13
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 30 '14 at 13:26
  • $\begingroup$ Yes, that is exactly why I missed in my analysis. Thanks for your effort :-) $\endgroup$ – Dave Dec 30 '14 at 15:14

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.