# Covers

## Motivation

In earlier sections we defined the **path groupoid** \(\pathGroupoid{\quiver{Q}}\) of a quiver \(\quiver{Q}\), and the notion of a **groupoid homomorphism** \(\functionSignature{\groupoidFunction{ \phi }}{\groupoid{G}}{\groupoid{H}}\) between groupoids \(\groupoid{G}\), \(\groupoid{H}\). We will now explore the notion of a **path homomorphism** \(\functionSignature{\pathHomomorphism{ \rho }}{\pathGroupoid{\quiver{Q}}}{\pathGroupoid{\quiver{F}}}\), which is groupoid homomorphism between the path groupoids of two quivers.

This will turn out to be a useful way to understand the topological idea of **quiver coverings** or **covers**. A quiver \(\quiver{Q}\) is said to **cover** another quiver \(\quiver{F}\) if paths in \(\quiver{Q}\) can be sent to paths in \(\quiver{F}\) in a surjective way that *respects composition* – where path homomorphism is the constraint that makes this idea precise.

## Graph covers

### Graph homomorphisms

Before we can define quiver covers, we'll briefly review **graph covers** and **graph homomorphisms**.

Formally, a (directed) graph cover \(\functionSignature{\function{\graphHomomorphism{ \pi }}}{\graph{G}}{\graph{H}}\) is a **surjective graph homomorphism** \(\graphHomomorphism{ \pi }\) between directed graphs \(\graph{G}\) and \(\graph{H}\). \(G\) is then called a **cover** of \(\graph{H}\), written \(\graph{G}\coversSymbol \graph{H}\). We'll also write \(\covering{\graphHomomorphism{ \pi }}{\graph{G}}{\graph{H}}\) 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 consists of a map \(\functionSignature{\graphHomomorphism{ \pi _V}}{\vertexList(\graph{G})}{\vertexList(\graph{H})}\) and a map \(\functionSignature{\graphHomomorphism{ \pi _E}}{\edgeList(\graph{G})}{\edgeList(\graph{H})}\), subject to the fairly obvious consistency condition that the vertices of the projection of an edge must be the projection of the vertices of that edge:

\[ \begin{matrix*}[c] \graphHomomorphism{ \pi _E}(\de{\vert{g_1}}{\vert{g_2}}) = \de{\vert{h_1}}{\vert{h_2}}\\ \implies \\\paren{\graphHomomorphism{ \pi _V}(\vert{g_1})\orSymbol \vert{h_1}}\andSymbol \paren{\graphHomomorphism{ \pi _V}(\vert{g_2})\orSymbol \vert{h_2}}\end{matrix*} \]### Graph covers

A graph cover \(\graph{G}\coversSymbol \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 \(\rform{\filledToken }\), \(\gform{\filledToken }\), \(\bform{\filledToken }\). 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}}(\rgform{\filledToken }) = \list{\rform{\filledToken },\gform{\filledToken }}\), \(\inverse{\graphHomomorphism{ \pi _V}}(\wcform{\filledToken }) = \list{\rform{\filledToken },\gform{\filledToken },\bform{\filledToken }}\). Similarly we'll color the edges: \(\inverse{\graphHomomorphism{ \pi _E}}(\waform{\barToken }) = \list{\barToken ,\wcform{\barToken }}\).

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 \(\rgform{\filledToken }\) vertex of \(\graph{H}\) is covered by the \(\rform{\filledToken }\) and \(\gform{\filledToken }\) vertices of \(\graph{G}\), and the \(\bform{\filledToken }\) vertex of \(\graph{H}\) by the \(\bform{\filledToken }\) vertex of \(\graph{G}\). We’ll refer to these pre-images as **contractions**, so that we say \(\rgform{\filledToken }\) is the **contraction** of \(\rform{\filledToken }\) and \(\gform{\filledToken }\). We've also shown dotted lines to their original positions to indicate that the \(\rform{\filledToken }\) and \(\gform{\filledToken }\) vertices were contracted together by this covering to form the \(\rgform{\filledToken }\) vertex. The two edges are mapped uniquely here, and so remain colored \(\barToken\) and \(\wcform{\barToken }\), hence there are no edge contractions. However, the edge between \(\rform{\filledToken }\) and \(\gform{\filledToken }\) now become a self-loop on \(\rgform{\filledToken }\).

### 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 \(\graph{G}\coversSymbol \graph{H}\coversSymbol \graph{J}\), it's clear that \(\graph{G}\coversSymbol \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 betwen 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, which as we can see is far more intricate:

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}}{\rform{\card{r}},\bform{\card{b}}}\):

Here we illustrate a particular *graph* covering:

Here, we have performed the contraction \(\contractionProduct{\vert{N}\contractionProductSymbol \vert{E}}\), where \(\contractionProductSymbol\) represents the contraction of two vertices. However the result is *no longer a quiver*, as the contracted vertex \(\contractionProduct{\vert{n}\contractionProductSymbol \vert{e}}\) now has two incoming \(\rform{\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 \(\contractionSum{\contractionProduct{\vert{N}\contractionProductSymbol \vert{E}}\contractionSumSymbol \contractionProduct{\vert{S}\contractionProductSymbol \vert{W}}}\), which consists of the simultaneous gluings \(\contractionProduct{\vert{N}\contractionProductSymbol \vert{E}}\) and \(\contractionProduct{\vert{S}\contractionProductSymbol \vert{W}}\):

(You might object that there should be *two* copies of the cardinal \(\rform{\card{r}}\) betwen the glued vertices \(\contractionProduct{\vert{N}\contractionProductSymbol \vert{E}}\) and \(\contractionProduct{\vert{S}\contractionProductSymbol \vert{W}}\). However, since these cardinals connect the same head and tail vertex, we collapse them into a single cardinal: they are indistinguishable as transitions).

The requirement of preserving the local uniqueness property is what makes gluings such as \(\contractionProduct{\vert{n}\contractionProductSymbol \vert{e}}\) impossible to perform in isolation: it is only when we perform \(\contractionSum{\contractionProduct{\vert{N}\contractionProductSymbol \vert{E}}\contractionSumSymbol \contractionProduct{\vert{S}\contractionProductSymbol \vert{W}}}\) simultaneously that we preserve local uniqueness.

#### Contraction order

Let's compute the complete contraction order:

In this example, these quivers represent the possible ways of taking subsets of the following gluings (in a suitable sense we will shortly define):

\[ \list{\contractionSum{\contractionProduct{\vert{E}\contractionProductSymbol \vert{W}}},\contractionSum{\contractionProduct{\vert{N}\contractionProductSymbol \vert{S}}},\contractionSum{\contractionProduct{\vert{N}\contractionProductSymbol \vert{E}}\contractionSumSymbol \contractionProduct{\vert{S}\contractionProductSymbol \vert{W}}},\contractionSum{\contractionProduct{\vert{N}\contractionProductSymbol \vert{W}}\contractionSumSymbol \contractionProduct{\vert{S}\contractionProductSymbol \vert{E}}}} \]In the section Contraction lattice 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 **graph covers**.

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 \(\covering{\graphHomomorphism{ \pi }}{\graph{G}}{\graph{H_1}}\), which is associated with some quiver homomorphism \(\graphHomomorphism{ \pi } = \tuple{\graphHomomorphism{ \pi _E},\graphHomomorphism{ \pi _V}}\).

I claim 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 explaining how it works. Since \(\graph{G}\) is 1-dimensional, there are only a finite number of paths – just 6 (modulo reversal), and so to describe \(\pathHomomorphism{ \rho }\) we can simply visualize how these 6 paths in \(\graph{G}\) are mapped into paths in \(\graph{H_1}\) by \(\pathHomomorphism{ \rho }\):

Two points are obviously true of this particular \(\pathHomomorphism{ \rho }\): first, 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}\).

Second, the 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 of the general fact (easily checked) that path homomorphisms preserve the property of being a left or right identity. Then since \(\paren{\pathWord{\vert{s}}{\emptyWord{}}{\vert{s}}}\) is the unique left identity of any path like \(\paren{\pathWord{\vert{s}}{\word{\card{c}}}{\vert{\primed{s}}}}\), we must have that \(\pathHomomorphism{ \rho }(\paren{\pathWord{\vert{s}}{\emptyWord{}}{\vert{s}}}) = \paren{\pathWord{\vert{t}}{\emptyWord{}}{\vert{t}}}\) is the left identity of the path \(\pathHomomorphism{ \rho }(\paren{\pathWord{\vert{s}}{\word{\card{c}}}{\vert{\primed{s}}}}) = \paren{\pathWord{\vert{v}}{\word{\card{c}}}{\vert{\primed{v}}}}\), uniqueness yielding \(\vert{v} = \vert{t}\), giving us the left form of the consistency condition: \(\graphHomomorphism{ \pi _E}(\tde{\vert{s}}{\primed{s}}{\card{c}}) = \tde{\vert{t}}{\primed{t}}{\card{c}}\implies \graphHomomorphism{ \pi _V}(\vert{s}) = \vert{t}\). The right form is similar.

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? No: empty paths are their own left and right identities, and hence their own inverses, but non-empty paths are not, and so empty paths *must* be sent to empty paths. So we can always obtain a vertex cover \(\graphHomomorphism{ \pi _V}\) from a *surjective* path homomorphism.

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? Yes. Here is a concrete example:

This path homomorphism is not surjective, of course. However, this more elaborate surjective example that still "lengthens" some paths:

Clearly, having the covering graph be disconnected gives us considerable freedom. Another counterexample is where a 1-path is sent to a 0-path.

Here in moving from \(\graph{G}\) to \(\graph{H}\) we have **contracted** the edge with cardinal \(\gform{\card{g}}\), effectively deleting that cardinal from the path word of any path that passes through it.

The tentative answer then seems to be that without additional restrictions, a surjective path homomorphism does not automatically yield a covering.

#### Coverings to surjective path homomorphisms

Does a covering \(\covering{\graphHomomorphism{ \pi }}{\graph{G}}{\graph{H_1}}\) induce a *unique* path homomorphism \(\pathHomomorphism{ \rho }\)? The answer here is more satisfying: yes! The reason 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.

## 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 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{\gform{\card{g}}}{\gform{\card{g}}}{\rform{\card{r}}}\) to a path in the path quiver with path word \(\word{\gform{\card{g}}}{\gform{\card{g}}}{\rform{\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{\rform{\card{r}}}{\bform{\card{b}}}{\rform{\ncard{r}}}{\bform{\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{\bform{\card{b}}}{\rform{\card{r}}}{\bform{\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{\bform{\ncard{b}}}{\rform{\card{r}}}{\bform{\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{\ellipsis },\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:

A centrally important fact about lattice quivers is they cover their fundamental quivers: \(\covering{\graphHomomorphism{ \pi }}{\quiver{Q}}{\quiver{F}}\). To this covering is associated a path homomorphism \(\pathHomomorphism{ \rho }\), which we use to define the covering as follows:

\[ \begin{aligned} \pathHomomorphism{ \rho }(\pathWord{\primed{\vert{t}}}{\wordSymbol{W}}{\primed{\vert{h}}}) &\defEqualSymbol \pathWord{\vert{t}}{\wordSymbol{W}}{\vert{h}}\\ \primed{\vert{t}} &\defEqualSymbol \tuple{\vert{t},\groupoidElement{g}_1}\\ \primed{\vert{h}} &\defEqualSymbol \tuple{\vert{h},\groupoidElement{g}_2}\\ \end{aligned} \]where we use the fact that \(\elemOf{\primed{\vert{v}}}{\vertexList(\quiver{Q})}\) are precisely pairs \(\tuple{\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 }\).