Why is the universal covering tree of $G$ unique up to isomorphism and how to obtain the covers of $G$ of quotients thereof?

187 Views Asked by At

Let us start from defining the universal covering tree of a graph $G$ to be the infinite tree $\mathcal{T}$ such that any cover $H$ of $G$ is a quotient of $\mathcal{T}$.

It is well known that the construction of a universal covering tree of $G$ can be done as follows. Pick a vertex $v\in V_G$, and define the vertex set of $\mathcal{T}$ to be in bijection with all the no-backtracking walks in $G$ starting at $v$. A walk $(v_1v_2 ... v_m)$ is no-backtracking if $v_i\neq v_i+2$ for all $1\leq i<m-1$. We then put an edge between two walks if one is the extension of the other by a single edge. That is, walks $w$ and $w'$ are adjacent if there is some $u\in V_G$ such that $w'=wu$ or $w=w'u$.

My first question is the following: how does one show that all the connected coverings of $G$ are quotients of $\mathcal{T}$? I can see how $G$ is a quotient of $\mathcal{T}$ - just partition the vertices of $\mathcal{T}$ according to the vertex where the walk ends - but I cannot see what partition is required for non-trivial covers of $G$.

Second question: how to show that this construction is unique up to isomorphism?

1

There are 1 best solutions below

2
On

Let $H$ be a connected $k$-fold covering space for $G$, with covering map $f:H\to G$. Any walk $W=[v_0,v_1,\dots,v_n]$ in $G$ can be lifted in $k$ ways to a walk $\tilde W=[\tilde v_0,\tilde v_1,\dots,\tilde v_n]$ of $H$ for which $f\circ \tilde W=W$. Namely, we pick $\tilde v_0$ to be any of the $k$ vertices in $f^{-1}(v_0)$, then for each $i\in \{1,\dots,n\}$, $\tilde v_i$ is defined to be the unique vertex for which $f(\tilde v_i)=v_i$ and $\tilde v_i$ is adjacent to $\tilde v_{i-1}$ in $H$.

This explains how $H$ is a quotient of $\mathcal T$. For each vertex $(v,v_1,\dots,v_n)$ in $\mathcal T$, it can be thought of as a walk in $G$, which lifts to a walk in $H$. Define the relation $\sim_H$ on $\mathcal T$ by saying $(v,v_1,\dots,v_n)\sim_H (v,w_1,\dots,w_m)$ if, whenever the two non-backtracking walks in $G$ are lifted to walks in $H$ with the same start point, then they have the same end point. You can show $$\mathcal T/\sim_H\,\,\cong H.$$

I can at least give a sketch of the proof of the uniqueness of universal covering spaces. Suppose we have two connected, acyclic covering spaces $T_1$ and $T_2$ of $G$, with covering maps $$ T_1\stackrel{f_1}{\longrightarrow} G\stackrel{f_2}{\longleftarrow} T_2 $$ Choose an arbitrary base point $r_0\in G$, and turn $T_1$ and $T_2$ into rooted trees by choosing $r_1\in f_1^{-1}(r_0)$ and $r_2\in f_2^{-1}(r_0)$. I will define a correspondence $\Phi:T_1\to T_2$ as follows.

Given $v\in T_1$, there is a unique path $r_1\to v$ in $T_1$. This projects down to a non-backtracking walk in $G$ starting at $r_0$, which lifts to a unique walk in $T_2$ starting at $r_2$. The endpoint of the lifted walk is $\Phi(v)$.

Now, if $\Phi(v)=\Phi(w)$, then the projections of the paths $r_1\to v$ and $r_1\to w$ must lift to two paths ending in the same place in $T_2$. Since $T_2$ is acyclic, they must be the same exact path in $T_2$, so $r_1\to v$ and $r_1\to w$ both project to the same walk in $G$. This means that the combined path $v\to r_1 \to w$ projects to a closed walk in $G$, which implies it is a closed walk in $T_1$, which is only possible in the trivial case where the paths $r_1\to v$ and $r_2\to v$ are the exact same path. This proves injectivity of $\Phi$.

Finally, it is simple to show that $\Phi(T_1)$ must be a connected component of $T_2$, which by connectivity of $T_2$ implies $\Phi(T_1)=T_2$, proving surjectivity.