# 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{\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 compatibility condition that the vertices of the projection of an edge must be the projection of the vertices of that edge:

\[ \begin{array}{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{array} \]### 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" 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}}{\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* edges with the cardinal \(\rform{\card{r}}\) betwen the glued vertices \(\contractionProduct{\vert{N}\contractionProductSymbol \vert{E}}\) and \(\contractionProduct{\vert{S}\contractionProductSymbol \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 \(\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 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 \(\covering{\graphHomomorphism{ \pi }}{\graph{G}}{\graph{H_1}}\), which is associated with some quiver homomorphism \(\graphHomomorphism{ \pi } = \tuple{\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-lengethening** 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 \(\graph{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 graph is disconnected we have considerable freedom in defining path homomorphisms.

Another counterexample to the hypothesis that surjective path homomorphisms yield coverings is given by a surjective **path shortening**:

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. 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 \(\covering{\graphHomomorphism{ \pi }}{\graph{G}}{\graph{H_1}}\) 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.

## 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:

An 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} \]Here 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 }\).