Homotopy Covers of Graphs

We can define a homotopy $\Lambda:G\times I_{1}\to H$ by $\Lambda(x,i)=f(x)=g(x)$ and

∎

Define the projection $\pi:G\to G_{s}$ by the identity on vertices and the projection on edges. Define $\iota:G_{s}\to G$ using the identity on vertices, and for each pair of edges $[e],[\overline{e}]$ choose an edge $e$ between the same vertices and define $\iota[e]=e$ and $\iota[\overline{e}]=\overline{e}$. Then $\iota\pi=id_{H}$ and $\pi\iota\simeq id_{G}$ by Lemma 2.6. ∎

The proof of [CS1], Proposition 4.4 can by adapted to the multi-edge case as follows. If $f$ and $g$ agree on vertices, then by Lemma 2.6 there is a one step homotopy between them. If $f,g$ differ by a single vertex $v$ then we can create a homotopy $\Lambda:G\times I_{1}\to H$ by $\Lambda|_{G\times\{0\}}=f$ and $\Lambda|_{G\times\{1\}}=g$, and

and

If $v$ has any loops $\ell_{i}$, then we know there is an edge $\eta$ connecting $f(v)$ to $g(v)$ and we define $\Lambda(\ell_{i},e_{1})=\eta$ and $\Lambda(\ell_{i},\overline{e}_{1})=\overline{\eta}$.

Conversely, suppose we have a homotopy $f\simeq g$; it is sufficient to consider a one-step homotopy $\Lambda:G\times I_{1}\to H$ between $f$ and $g$ and then induct to get longer homotopies. Suppose that $G$ has vertex set $\{v_{1},v_{2},\dots,v_{n}\}$. We define a homotopy $\widetilde{\Lambda}:G\times I_{n}\to H$ on vertices by

and on edges by the following: if $e$ is an edge of $G$ with $\partial_{0}e=v_{i}$ and $\partial_{1}e=v_{j}$ then

This defines intermediate graph homomorphisms $f_{k}=\widetilde{\Lambda}(v,k)$ in which $f_{k},f_{k+1}$ either agree on vertices or differ by a single vertex, and thus we get a sequence of spider moves joining $f$ to $g$. ∎

The product groupoid $\Pi(G_{u})/T\times\operatorname{\mathbb{Z}}/2$ is defined as the product of categories, interpreting $\operatorname{\mathbb{Z}}/2$ as a category with a single object. Explicitly, $\Pi(G)/T\times\operatorname{\mathbb{Z}}/2$ has the same objects as $\Pi(G)/T$, with arrows $x\to y$ defined by $(\alpha,i)$ for $\alpha:x\to y$ in $\Pi(G)/T$ and $i=0,1\in\operatorname{\mathbb{Z}}/2$. The composition is defined by $(\alpha,i)\circ(\beta,j)=(\alpha\circ\beta,i+j\textup{ (mod 2)})$.

We define the functor $\Psi:\Pi(G)\to\Pi(G_{u})/T\times\mathbb{Z}/2$ by $\Psi(v)=v$ on objects and $\Psi(\alpha)=(\alpha_{u},i)$ on arrows, where $\alpha_{u}$ denotes the walk $\alpha$ with all loops removed, and $i$ is the length of the walk $\alpha$ (mod 2).

To show that $\Psi$ is well defined, we suppose that $[\alpha]=[\alpha^{\prime}]$ in $\Pi(G)$. Then $\alpha$ and $\alpha^{\prime}$ are connected by a sequence of prunes, anti-prunes, and spider moves, all of which preserve the parity of the length. It is easy to see that any prune, anti-prune, or spider move not involving any loops has a corresponding move on the unlooped version, and that a prune involving a loop must just insert or delete a pair of loops, leaving the unlooped walk the same. So we consider the case when we have a spider move involving a loop. Unlooping $(vvw)$ and $(vww)$ both result in $(vw)$. If we replace $\alpha=uuv$ with $\alpha^{\prime}=uxv$, then $\alpha_{u}=uv$ while $\alpha^{\prime}_{u}=uxv=uxvuv=uv$ since $uxvu$ is a triangle. Hence the $\alpha_{u}=\alpha^{\prime}_{u}$ in $\Pi(G_{u})/T$. $\Psi$ respects composition since $(\alpha*\beta)_{u}=\alpha_{u}*\beta_{u}$.

We define an inverse functor $\Phi:\Pi(G_{u})/T\times\mathbb{Z}/2\to\Pi(G)$ again using the identity on objects, and on arrows defining $\Phi(\gamma,i)=\gamma*(ww)^{k}$ where $(ww)$ denotes the loop on the ending vertex $w$ of $\gamma$, and $k=i+p$ where $p$ is the mod 2 length of $\gamma$. This ensures that the parity of $\gamma*(ww)^{k}$ matches the parity of $i$.

We check that this is well-defined: again, any prune, anti-prune, or spider move of $\gamma$ gives a corresponding move on $\gamma*(ww)$, so we just need to check what happens when we insert or remove a triangle. Suppose that we have two walks in $G_{u}$ defined by $\gamma$ and $\gamma^{\prime}=\gamma_{1}*(xyzx)*\gamma_{2}$ where $\gamma_{1}*\gamma_{2}=\gamma$, so that we obtain $\gamma^{\prime}$ by inserting a triangle into $\gamma$. Then the length of $\gamma$ and $\gamma^{\prime}$ have opposite parities, and so when we apply $\Phi$ to $(\gamma,i)$ and to $(\gamma^{\prime},i)$, one will be concatenated with a loop and the other will not. Assume that $\Phi(\gamma,i)=\gamma*(ww)$ and $\Phi(\gamma^{\prime},i)=\gamma^{\prime}$. Then we use Observation 3.6 to get the following in $\Pi(G)$: $\gamma^{\prime}*(ww)=\gamma_{1}*(xyzx)*\gamma_{2}*(ww)=\gamma_{1}*(xyzx)*(xx)*\gamma_{2}=\gamma_{1}*(xyzxx)*\gamma_{2}=\gamma_{1}*(xyxxx)*\gamma_{2}=\gamma_{1}*(xyx)*\gamma_{2}=\gamma_{1}*\gamma_{2}=\gamma$. Therefore $\gamma^{\prime}=\gamma^{\prime}*(ww)*(ww)=\gamma*(ww)$. A similar argument verifies well-definedness when $\Phi$ puts the loop on $\gamma^{\prime}$, and migrating loops through out paths ensures that $\Phi$ respects the concatenation operation.

Because all loops can be moved to the end of any walk in $\Pi(G)$, $\Psi$ and $\Phi$ are inverse functors, giving the desired isomorphism of groupoids.

∎

Suppose that $f:\widetilde{G}\to G$ is a homotopy covering map. To show that it induces a bijection on stars $f_{*}:\Pi_{\widetilde{v}}(\widetilde{G})\to\Pi_{v}(G)$, we observe that since $f$ is a covering by Observation 4.5, Lemma 4.2 allows us to lift paths and so $f_{*}$ is surjective. To see that $f_{*}$ is also injective, we recall that equivalences in $\Pi(G)$ are generated by prunes, anti-prunes and spider moves. We again use Observation 4.5 to see that any prunable section of a walk $e\overline{e}$ lifts to a similarly prunable section $d\overline{d}$, and that any spider move that changes edges but not vertices will lift to a similar edge move since parallel edges lift to parallel edges. Lastly, any spider move that adjusts one vertex will lift to a similar spider move because the bijection on second neighbourhoods $N_{2}(v)$ respects endpoints.

Conversely, suppose $f:\widetilde{G}\to G$ is a graph cover which induces a covering of groupoids $\Pi(f):\Pi(\widetilde{G})\to\Pi(G)$. We know that we can lift any 2-walk uniquely by Lemma 4.2. This lift must respect endpoints because if two 2-walks have the same endpoint, then they represent the same arrow in $\Pi_{v}(G)$ and then the bijecton on stars ensures that their lifts represent the same arrow of $\Pi_{\widetilde{v}}(\widetilde{G})$ and hence have the same target vertex.

∎

The proof of the above follows standard arugments as in [Angluin1, Bass, Hatcher]. Any walk $\alpha$ in $G$ lifts uniquely to a walk $\widetilde{\alpha}$ starting at $\tilde{v}$ in $\widetilde{G}$, and so we define $\tilde{\rho}(\alpha)$ to be the endpoint of this lift. This is easily extended to edges. ∎

The map $\Phi$ is a group homomorphism because $\Phi(\gamma*\gamma^{\prime})(\alpha)=\gamma*\gamma^{\prime}*\alpha=\psi_{\gamma}\left(\psi_{\gamma^{\prime}}(\alpha)\right)=\left(\Phi(\gamma)\circ\Phi(\gamma^{\prime})\right)(\alpha)$. To show that $\Phi$ is injective, suppose that $\gamma,\gamma^{\prime}\in\Pi_{v}^{v}G$ such that $\Phi(\gamma)=\Phi(\gamma^{\prime})$. Then $\psi_{\gamma}((v))=\psi_{\gamma^{\prime}}((v))$ and so $\gamma=\gamma*(v)=\gamma^{\prime}*(v)=\gamma^{\prime}$.

To check that $\Phi$ is surjective, we let $\varphi\in D(G)$ and define $\gamma=\varphi((v))$. Since $\rho(\varphi((v)))=\rho((v))=v$, the walk $\gamma$ ends at $v$ and hence $\Phi(\gamma)=\psi_{\gamma}$ is defined with $\psi_{\gamma}((v))=\varphi((v))$. We claim that $\varphi=\psi_{\gamma}$. We prove this by induction on the length of a walk representing a vertex in $U$, starting with our base case length $0$ walk $(v)$. Let $\alpha$ have a representative of length $n$, of the form $\beta*e$ for an edge $e$ and a length $n-1$ walk $\beta$, and assume that $\varphi(\beta)=\psi_{\gamma}(\alpha)$. We know that $e$ defines an edge $d_{e}$ from $\beta$ to $\alpha$ in $U$, and since $\varphi$ is a graph homomorphism that commutes with $\rho$ we have an edge $\varphi(d_{e})=d^{\prime}_{e}$ from $\varphi(\beta)$ to $\varphi(\alpha)$. Therefore $\varphi(\alpha)=\varphi(\beta)*d^{\prime}_{e}=\gamma*\beta*d^{\prime}_{e}$. Uniqueness of path lifting ensures that $\gamma*\beta*d^{\prime}_{e}=\gamma*\alpha$. Thus $\varphi=\psi_{\gamma}$ and so $\Phi$ is surjective, completing the proof.

∎

We first note that $r$ is well-defined on equivalence classes forming the vertices $U/S$ because for any $s\in S\leq D(G)$, we have $\rho s\alpha=\rho\alpha$; and hence $r$ is surjective on vertices because $\rho$ is. The map $r$ is similarly well-defined on edges, and moreover since $\rho(sd_{e})=\rho(d_{e})=e$ the edges $[d_{e}]$ from $[\alpha]$ to $[\beta]$ are still in bijection with edges $e$ from their endpoints $w,w^{\prime}$ in $G$. Thus $r$ induces a bijection from $N_{E}([\alpha])$ to $N_{E}(w)$. Therefore $r$ is a cover as in Defintion 4.1.

We now show that $r$ induces a covering map on fundamental groupoids $\Pi(r):\Pi(U/S)\to\Pi(G)$, meaning that it is bijective on stars. By definition, $rp=\rho$ where $p$ is the projection map $p:U\to U/S$. Functoriality ensures that $\Pi(\rho)=\Pi(rp)=\Pi(r)\Pi(p)$. Now $\Pi(p)$ is surjective on stars: given a walk $([d_{1}][d_{2}]\cdots[d_{n}])$ in $U/S$, we know that there are representatives $d_{i}$ in $U$ and $s_{i}\in S$ such that $\partial_{1}(d_{i-1})=\partial_{0}(s_{i}d_{i})$. By applying the $s_{i}$ in turn to the end of the walk, we obtain a walk in $U$ that maps to $([d_{1}][d_{2}]\cdots[d_{n}])$ by $p$.

Since $\Pi(p)$ is surjective on stars and $\Pi(\rho)=\Pi(r)\Pi(p)$ is bijective on stars, we conclude that $\Pi(r)$ is bijective on stars. By Proposition 4.7, $r$ is a homotopy covering map.

∎

Suppose that $f:\widetilde{G}\to G$ is a homotopy covering map. Theorem 4.10 states that $U$ is also the universal homotopy cover of $\widetilde{G}$ and there exists a homotopy covering map $\tilde{\rho}:U\to\widetilde{G}$ such that $\rho=pf$. Define $S=\{s\in D(G):s\tilde{\rho}=\tilde{\rho}\}$. We wish to show that $U/S\cong\widetilde{G}$. In fact, $S=D(\widetilde{G})$, and thus it suffcies to consider the case $S=D(G)$ and prove that $U/D(G)\cong G$.

Let $r:U/D(G)\to G$ be defined by $r[u]=\rho(u)$. Then $r$ is a homotopy covering map by Theorem 4.16, and hence surjective. We will show that it is also injective. Suppose that $r[\alpha]=w=r[\beta]$ for vertices $[\alpha],[\beta]\in U$. Since $\alpha,\beta$ have the same endpoint, define $\gamma=\alpha*\beta^{-1}$, giving a walk starting and ending at $v$, and let $s=\psi_{\gamma}$ as in Definition 4.14. Then $\psi_{\gamma}\in D(G)$ and $\psi_{\gamma}(\beta)=\alpha$ and so $[\alpha]=[\beta]$ in $U/D(G)$. Therefore $r$ is a bijection of vertices, and also a cover which gives a bijection on neighbourhoods. So $r$ is also a bijection on edges and hence an isomorphism.

∎

We know that $U_{v}G$ has vertices which are defined by walks from $v$ in $\Pi_{v}(G)$. We apply the isomorphism of Proposition 3.8 to get an arrow in the groupoid $\Pi_{v}(G_{u})/T\times\operatorname{\mathbb{Z}}/2$ starting at $v$, giving an isomorphism between the vertices of $U_{v}G$ and $C_{\ell}\times K_{2}$. We then define the mapping $U_{v}G\to C_{\ell}\times K_{2}$ on edges. Any edge $d_{e}\in(U_{v}G)$ corresponds to extending a walk $\alpha$ by a single edge $e\in E(G)$ to $\alpha*e$. In this case, the parity of $\alpha$ and $\alpha*e$ are opposite, and so $\alpha$ and $\alpha*e$ are mapped to $(\alpha_{u},i)$ and $((\alpha*e)_{u},1-i)$ in $C_{\ell}\times K_{2}$. If $\alpha_{u}=(\alpha*e)_{u}$ then $e=\ell$ was a loop, and we define the image of $d_{e}$ to be the edge $c_{e}=d_{\ell}$ with $\partial_{0}(c_{\ell})=(\alpha_{u},i),\partial_{1}(c_{\ell})=(\alpha_{u},1-i)$. Otherwise we have $\alpha_{u}*e=(\alpha*e)_{u}$ and there is an edge $c_{e}$, $\partial_{0}(c_{e})=(\alpha_{u},i),\partial_{1}(c_{e})=(\alpha_{u}*e,1-i)$. We then map $d_{e}\mapsto c_{e}$. It is straightforward to check that this gives a bijective map on edges in which $\overline{d_{e}}\mapsto\overline{c_{e}}$. Thus we get an isomorphism of graphs.

∎

We know that $U_{v}G\cong C_{\ell}\times K_{2}$ and since $G$ is $C_{3}$ free, $U_{v}G_{u}=C$ and so the parity of a walk in $C$ is well-defined. Define a homomorphism $\Phi:C_{\ell}\times K_{2}\to C\square K_{2}$ by $(\gamma,i)\to(\gamma,i+k)$ where $k$ is the length of $\gamma$ (mod 2). Since $\gamma$ and $\gamma*e$ always have opposite parity, the vertices $(\gamma,i)$ and $(\gamma*e,1-i)$ are always mapped to the same layer in the box product and this gives a graph homomorphism. It is straightforward to see that $\Phi$ is bijective on vertices and edges and thus is an isomorphism.

∎