Coverings #
Motivation #
In Path groupoids we defined the path groupoid \( \pathGroupoid{\quiver{Q}} \) of a quiver \( \quiver{Q} \), and in Path homomorphisms we defined maps between the path groupoids of two quivers that was a groupoid homomorphism. We will now define a relationship between quivers called a quiver covering, which corresponds to a surjective path homomorphism. Certain coverings can be seen as contractions in which we glue together sets of vertices.
Graph covers #
Graph homomorphisms #
Before we can define quiver covers, we'll briefly introduce graph covers and graph homomorphisms.
Formally, a (directed) graph cover \( \functionSignature{\function{ \pi }}{\graph{G}}{\graph{H}} \) is a surjective graph homomorphism between directed graphs \( \graph{G} \) and \( \graph{H} \). \( G \) is then called a cover of \( \graph{H} \), written \( \CoFo{\graph{G}}{\graph{H}} \). We'll also write \( \GrInCoFoⅡ{\graph{G}}{\graph{H}}{\graphHomomorphism{ \pi }} \) to explicitly indicate the homomorphism \( \graphHomomorphism{ \pi } \) involved. But what is a graph homomorphism?
The homomorphism \( \graphHomomorphism{ \pi } \) tells us how to "project" elements of \( \graph{G} \) onto elements of \( \graph{H} \), and can be thought of as a pair \( \TuFo{\graphHomomorphism{ \pi _{\vertices{}}}, \graphHomomorphism{ \pi _{\edges{}}}} \), where \( \functionSignature{\graphHomomorphism{ \pi _{\vertices{}}}}{\vertexList(\graph{G})}{\vertexList(\graph{H})} \) projects vertices and \( \functionSignature{\graphHomomorphism{ \pi _{\edges{}}}}{\edgeList(\graph{G})}{\edgeList(\graph{H})} \) projects edges, subject to the fairly obvious compatibility condition that the vertices of the projection of an edge must be the projection of the vertices of that edge:
\[ \begin{nsarray}{c} \graphHomomorphism{ \pi _{\edges{}}}(\de{\vert{g_1}}{\vert{g_2}}) = \de{\vert{h_1}}{\vert{h_2}}\\ \implies \\ \paren{\graphHomomorphism{ \pi _{\vertices{}}}(\vert{g_1})\orSymbol \vert{h_1}}\andSymbol \paren{\graphHomomorphism{ \pi _{\vertices{}}}(\vert{g_2})\orSymbol \vert{h_2}} \end{nsarray} \]Graph covers #
A graph cover \( \CoFo{\graph{G}}{\graph{H}} \) is a surjective graph homomorphism. Therefore one way we can depict a cover is by illustrating which vertices and edges of \( \graph{G} \) cover which vertices and edges of \( \graph{H} \). For small graphs, we will use additive color semantics to do this. In particular, if \( \graph{G} \) has three vertices, we will depict them as \( \reFo{\fiToSy} \), \( \grFo{\fiToSy} \), \( \blFo{\fiToSy} \). Then we'll show a vertex of \( \graph{H} \) with a color that is the additive blend of the primary colors of its preimage under \( \graphHomomorphism{ \pi _V} \). For example, \( \inverse{\graphHomomorphism{ \pi _V}}(\teFo{\fiToSy}) = \list{\reFo{\fiToSy},\grFo{\fiToSy}} \), \( \inverse{\graphHomomorphism{ \pi _V}}(\liGFo{\fiToSy}) = \list{\reFo{\fiToSy},\grFo{\fiToSy},\blFo{\fiToSy}} \). Similarly we'll color the edges: \( \inverse{\graphHomomorphism{ \pi _E}}(\daGFo{\baToSy}) = \list{\baToSy,\liGFo{\baToSy}} \).
Let's look at very simple example undirected graph \( \graph{G} \), which we'll call the partial triangle, and a particular \( \graph{H} \) it covers:
The \( \graph{H} \)-vertex \( \teFo{\fiToSy} \) is covered by the \( \graph{G} \)-vertices \( \reFo{\fiToSy},\grFo{\fiToSy} \), and the \( \graph{H} \)-vertex \( \blFo{\fiToSy} \) by the \( \graph{G} \)-vertex \( \blFo{\fiToSy} \). We’ll refer to these pre-images as contractions, so that we say \( \teFo{\fiToSy} \) is the contraction of \( \reFo{\fiToSy},\grFo{\fiToSy} \). We've also shown dotted lines to their original positions to indicate that the \( \reFo{\fiToSy},\grFo{\fiToSy} \) vertices were contracted together by this covering to form the \( \teFo{\fiToSy} \) vertex. The two edges are mapped uniquely here, and so remain colored \( \baToSy \) and \( \liGFo{\baToSy} \), hence there are no edge contractions. However, the edge between \( \reFo{\fiToSy} \) and \( \grFo{\fiToSy} \) now become a self-loop on \( \teFo{\fiToSy} \).
Covering partial order #
Our partial triangle covers many smaller graphs. For finite graphs, it’s clear that the covered graph has the same or fewer vertices, so we can conclude that up to isomorphism there are only finitely many covered graphs of \( \graph{G} \). Furthermore, if \( \CoFo{\graph{G}}{\graph{H}} \), it's clear that \( \CoFo{\graph{G}}{\graph{J}} \), since the composition of two surjective homomorphisms is another. Therefore, covering forms a partial order on finite graphs, and we can depict this in the form of a larger vertical graph, with an edge between two graphs if the higher one strictly covers the lower one -- in other words a graph is connected to one below it if it covers it, is not isomorphic, and the covering is not implied by transitivity.
Here is the covering partial order, or synonymously the contraction partial order, for our example:
Square #
Let's consider the covering partial order for a "partial square" with 4 vertices and 3 edges. To reduce uninteresting complexity, we will avoid the explicit contraction of edges, and perform these contractions "greedily" whenever multiple edges exist between two vertices as a result of a vertex contraction:
Notice that as in the previous example, this partial order terminates in a single vertex and self-loop, the 1-graph, which is covered by every other graph. This single vertex and its self loop are gray, reflecting the fact that they are the color average of all of the original primary-colored vertices and edges.
Quiver covers #
What about quivers? How do we extend the notion of covering to the quiver setting? We saw that for graphs, we could effect any particular covering in a sequence of atomic steps, in which we contracted together pairs of vertices and edges. It turns out that this approach does not work for quivers, for the elementary reason that we can easily violate the local uniqueness property unless we perform multiple vertex contractions simultaneously.
Simultaneous contractions #
Let's take a simple example to illustrate this idea. We'll focus on coverings of \( \bindCards{\subSize{\squareQuiver }{2}}{\reFo{\card{r}},\blFo{\card{b}}} \):
Here we illustrate a particular graph covering:
Here, we have performed the contraction \( \CoPrFo{\vert{N} \coPrFo \vert{E}} \), where \( \coPrFo \) represents the contraction of two vertices. However the result is no longer a quiver, as the contracted vertex \( \CoPrFo{\vert{n} \coPrFo \vert{e}} \) now has two incoming \( \reFo{\card{r}} \) cardinals. So while this is graph covering, it is not a quiver covering.
In contrast, here is a valid quiver covering, where we have performed the gluing \( \CoSuFo{\CoPrFo{\vert{N} \coPrFo \vert{E}} \coSuFo \CoPrFo{\vert{S} \coPrFo \vert{W}}} \), which consists of the simultaneous gluings \( \CoPrFo{\vert{N} \coPrFo \vert{E}} \) and \( \CoPrFo{\vert{S} \coPrFo \vert{W}} \):
You might object that there should be two edges with the cardinal \( \reFo{\card{r}} \) between the glued vertices \( \CoPrFo{\vert{N} \coPrFo \vert{E}} \) and \( \CoPrFo{\vert{S} \coPrFo \vert{W}} \). We simply define these two edges to be contracted together automatically and implicitly, and in fact we will only allow edge contractions that are precisely of this "deduplicating" form.
The key point here is that the requirement of preserving the local uniqueness property is what makes gluings such as \( \CoPrFo{\vert{N} \coPrFo \vert{E}} \) impossible to perform in isolation: it is only when we perform \( \CoSuFo{\CoPrFo{\vert{N} \coPrFo \vert{E}} \coSuFo \CoPrFo{\vert{S} \coPrFo \vert{W}}} \) simultaneously that we preserve local uniqueness.
Contraction order #
Let's compute the complete contraction order:
In the section Contraction lattices we will examine this object from an order-theoretic point of view, establishing the structure of an order-theoretic lattice (which is a different usage of the word "lattice" than that in Lattice quivers).
Path homomorphisms #
Let's now turn to the question of the connection between path homomorphisms and quiver coverings.
Pictured below is a quiver \( \graph{G} \), and 5 quivers that it covers: \( \graph{H_1},\graph{H_2},\graph{H_3},\graph{H_4},\graph{H_5} \).
These form a partial order as before, which looks like this:
Let's focus on a particular covering \( \QuInCoFoⅡ{\quiver{G}}{\quiver{H_1}}{\pathHomomorphism{ \pi }} \), which is associated with some graph (quiver) homomorphism \( \graphHomomorphism{ \pi } = \TuFo{\graphHomomorphism{ \pi _E}, \graphHomomorphism{ \pi _V}} \).
An alternative way of expressing a quiver homomorphism is via a path homomorphism \( \functionSignature{\pathHomomorphism{ \rho }}{\pathGroupoid{\graph{G}}}{\pathGroupoid{\graph{H_1}}} \). Why is this? I'll illustrate by providing a particular \( \pathHomomorphism{ \rho } \) that corresponds to \( \graphHomomorphism{ \pi } \), and illustrating its behavior with a path table:
As for any path homomorphism, empty paths are sent to empty paths, \( \pathHomomorphism{ \rho }(\paren{\pathWord{\vert{s}}{\emptyWord{}}{\vert{s}}}) = \paren{\pathWord{\vert{t}}{\emptyWord{}}{\vert{t}}} \), giving us the vertex covering \( \graphHomomorphism{ \pi _V}(\vert{s}) = \vert{t} \).
Additionally, this homomorphism is length-preserving: 1-paths are sent to 1-paths, \( \pathHomomorphism{ \rho }(\paren{\pathWord{\vert{u}}{\word{\card{c}}}{\vert{\primed{u}}}}) = \paren{\pathWord{\vert{v}}{\word{\card{c}}}{\vert{\primed{v}}}} \), giving us the edge covering \( \graphHomomorphism{ \pi _E}(\tde{\vert{u}}{\primed{u}}{\card{c}}) = \tde{\vert{v}}{\primed{v}}{\card{c}} \).
What about the compatibility condition between \( \graphHomomorphism{ \pi _E} \) and \( \graphHomomorphism{ \pi _V} \)? This is a consequence (easily checked) of the ordinary compatibility condition of path homomorphisms:
\[ \pathHomomorphism{ \rho }(\pathCompose{\path{P_1}}{\path{P_2}}) = \pathCompose{\pathHomomorphism{ \rho }(\path{P_1})}{\pathHomomorphism{ \rho }(\path{P_2})} \]Ok, so coverings can be described by path homomorphisms. But are they uniquely so described? And do all path homomorphisms yield corresponding coverings?
Surjective path homomorphisms to coverings #
To answer the latter question, let's answer a simpler question: can a path homomorphism send an empty path to a non-empty path? As we saw in Path homomorphisms, the answer is no. Therefore we can always obtain a vertex cover \( \graphHomomorphism{ \pi _V} \) from a surjective path homomorphism, since this will guarantee that every vertex (= empty path) of the covered quiver has at least one corresponding vertex (= empty path) of the covering quiver.
Ok, so the \( \graphHomomorphism{ \pi _V} \) story seems clear. To know that we can obtain an edge cover \( \graphHomomorphism{ \pi _E} \) from \( \pathHomomorphism{ \rho } \), let's imagine how it could go wrong: can a 1-path can be sent to e.g. a 2-path? Again, we saw examples of path-lengthening homomorphisms already in [[[Path homomorphisms]], but here is a path table showing a simple example:
This path homomorphism is not surjective, of course: the 1-paths in \( \quiver{H} \) have no preimage under \( \pathHomomorphism{ \rho } \). However, we can construct a more elaborate surjective homomorphism that is still path lengthening? Here is such an example:
Clearly, if the covering quiver is disconnected we have considerable freedom in defining path homomorphisms.
Another counterexample to the hypothesis that surjective path homomorphisms yield coverings is given by the following surjective path shortening homomorphism:
Here, in moving from \( \quiver{G} \) to \( \quiver{H} \), we have contracted the edge labeled with cardinal \( \grFo{\card{g}} \), effectively deleting that cardinal from the path word of any path that passes through it. This is not a covering, because a covering must send edges of \( \quiver{G} \) to edges of \( \quiver{H} \).
The tentative answer then seems to be that without additional restrictions, a surjective path homomorphism does not automatically yield a covering. But the requirement we need is easily guessed: we must have a length-preserving path homomorphism, since this defines a unique (oriented) edge in the covered graph for every edge in the covering graph in a compatible way.
Coverings to surjective path homomorphisms #
Does a covering \( \QuInCoFoⅡ{\quiver{G}}{\quiver{H}}{\function{ \pi }} \) induce a unique path homomorphism \( \pathHomomorphism{ \rho } \)? The answer here is more satisfying: yes! The reason of course is simple: the data of \( \graphHomomorphism{ \pi _E} \) and \( \graphHomomorphism{ \pi _V} \) does uniquely determine the behavior of \( \pathHomomorphism{ \rho } \) on 0-paths and 1-paths. And since all longer paths in \( \graph{G} \) can be constructed from compositions of 1-paths, and composition must be preserved by \( \pathHomomorphism{ \rho } \), we have no choice in how to define \( \pathHomomorphism{ \rho } \) on such longer paths. Hence, a covering yields (or generates) a path homomorphism.
We write this as \( \QuInCoFoⅡ{\quiver{G}}{\quiver{H}}{\pathHomomorphism{ \gamma }} \), and call \( \pathHomomorphism{ \gamma } \) a covering homomorphism.
Path quiver homomorphism #
A more subtle kind of path homomorphism has been latent since we introduced path quivers: the path homomorphisms from a quiver to its forward path quiver. To construct these, we need to map every path in the quiver to a path in the path quiver (a “path of paths”). Let’s start with the easy part: if the path in the base quiver starts at the origin, we form the path in the path quiver by taking the sequence of extensions that extend the empty path into the full path:
In this example, we’ve sent a path in the base quiver with path word \( \word{\grFo{\card{g}}}{\grFo{\card{g}}}{\reFo{\card{r}}} \) to a path in the path quiver with path word \( \word{\grFo{\card{g}}}{\grFo{\card{g}}}{\reFo{\card{r}}} \).
But to define a path homomorphism, we also need to figure out where to send paths which do not start at the origin. For the tree quiver example, this is straightforward: for a path \( \path{P} \) in the base quiver starting at \( \vert{t} \neq \vert{o} \), we choose a vertex in the path quiver corresponding to the path taking us from the origin \( \vert{o} \) to \( \vert{t} \), then use the path word as before:
In the case of trees the of this path homomorphism from a quiver to its path quiver is trivial, because the path quivers of trees are already isomorphic to them. But it turns out a related construction will work for all finite connected quivers, not just trees. Let’s look at a simple base quiver that is not a tree:
Because there is a cycle \( \paren{\pathWord{\vert{1}}{\word{\reFo{\card{r}}}{\blFo{\card{b}}}{\reFo{\ncard{r}}}{\blFo{\ncard{b}}}}{\vert{1}}} \), the path quiver will be infinite, so we’ll only draw the subgraph of the path quiver in which this cycle is “wound” a maximum of one time. Choosing the origin as \( \vert{1} \), we again have no problem with the “easy” part of where to send paths starting at the origin, since they just have the same cardinal word. For example, the path \( \paren{\pathWord{\vert{1}}{\word{\blFo{\card{b}}}{\reFo{\card{r}}}{\blFo{\card{b}}}}{\vert{6}}} \):
The “hard” part consists of dealing with paths like this:
To figure out where our path homomorphism \( \pathHomomorphism{ \rho } \) sends this path \( \path{P} = \paren{\pathWord{\vert{5}}{\word{\blFo{\ncard{b}}}{\reFo{\card{r}}}{\blFo{\card{b}}}}{\vert{6}}} \) must first choose a vertex \( \elemOf{\vert{t}}{\forwardPathQuiver{\quiver{Q}}{\vert{1}}} \) that corresponds to the tail vertex of \( \path{P} \), which is \( \vert{5} \). Now \( \pathHomomorphism{ \rho }(\vert{5}) \) is a path with head vertex \( \vert{5} \). One we’ve chosen \( \pathHomomorphism{ \rho }(\vert{t}) \), there is nothing more to do, since the path word of \( \path{P} \) gives the path word of \( \pathHomomorphism{ \rho }(\path{P}) \). However, whatever choice we make for \( \pathHomomorphism{ \rho }(\vert{5}) \) must be compatible with other choices we make for other vertices in \( \quiver{Q} \). Luckily, this isn’t as tricky as it sounds. All we need to do is choose a spanning tree of the base quiver.
Fundamental quiver #
We now return to the situation of a lattice quiver \( \quiver{Q} \) generated by a fundamental quiver \( \bindCards{\quiver{F}}{\card{\card{c}_1},\card{\elSy},\card{\card{c}_{\sym{i}}}} \) with the representation associated with a cardinal valuation \( \functionSignature{\groupoidFunction{ \phi }}{\cardinalList(\quiver{Q})}{\group{G}} \). That \( \quiver{Q} \) is generated by \( \quiver{F} \) is the statement:
\[ \quiver{Q} = \compactQuotient{\quiver{F}}{\vert{v}}{\groupoidFunction{ \phi }} \]An important fact about lattice quivers is they cover their fundamental quivers: \( \QuInCoFoⅡ{\quiver{Q}}{\quiver{F}}{\pathHomomorphism{ \pi }} \). To this covering is associated a path homomorphism \( \pathHomomorphism{ \rho } \), which we use to define the covering as follows:
\[ \begin{aligned} \pathHomomorphism{ \rho }(\pathWord{\vert{\primed{t}}}{\wordSymbol{W}}{\vert{\primed{h}}})&\defEqualSymbol \pathWord{\vert{t}}{\wordSymbol{W}}{\vert{h}}\\ \vert{\primed{t}}&\defEqualSymbol \TuFo{\vert{t}, \groupoidElement{g_1}}\\ \vert{\primed{h}}&\defEqualSymbol \TuFo{\vert{h}, \groupoidElement{g_2}}\end{aligned} \]Here we use the fact that \( \elemOf{\primed{\vert{v}}}{\vertexList(\quiver{Q})} \) are precisely pairs \( \TuFo{\vert{v}, \groupoidElement{g}} \), where \( \elemOf{\vert{t}}{\vertexList(\quiver{F})} \) and \( \groupoidElement{g} \) are elements of the group associated with the cardinal valuation \( \groupoidFunction{ \phi } \).