\( \gdef\badDispatch#1{\textbf{\textcolor{e1432d}{#1}}} \gdef\rarrbar{ {\raisebox{-0.05em}{→}\mkern{-0.13em}{\large\shortmid}}} \gdef\larrbar{ { {\large\shortmid}\mkern{-0.13em}{\raisebox{-0.05em}{←}}}} \gdef\suptrans{^\mathsf{T}} \gdef\supdagger{^\dagger} \gdef\rawsymbol#1{\operatorname{#1}} \gdef\colorsymbol#1#2{\textcolor{#1}{\rawsymbol{#2}}} \gdef\lsymbol#1{\colorsymbol{262626}{#1}} \gdef\msymbol#1{\colorsymbol{b50800}{#1}} \gdef\osymbol#1{\colorsymbol{00427f}{#1}} \gdef\lstring#1{\textcolor{666666}{\textrm{\textquotedblleft{#1}\textquotedblright}}} \gdef\boldForm#1{\textbf{#1}} \gdef\rform#1{ {\textcolor{e1432d}{#1}}} \gdef\gform#1{ {\textcolor{4ea82a}{#1}}} \gdef\bform#1{ {\textcolor{3e81c3}{#1}}} \gdef\rgform#1{ {\textcolor{dc841a}{#1}}} \gdef\gbform#1{ {\textcolor{47a5a7}{#1}}} \gdef\rbform#1{ {\textcolor{c74883}{#1}}} \gdef\waform#1{ {\textcolor{6b6b6b}{#1}}} \gdef\wbform#1{ {\textcolor{929292}{#1}}} \gdef\wcform#1{ {\textcolor{c5c5c5}{#1}}} \gdef\barToken{\mathbf{|}} \gdef\filledRectangleToken{▮} \gdef\emptyRectangleToken{▯} \gdef\filledToken{∙} \gdef\emptyToken{∘} \gdef\cardinalRewrite#1#2{\rewrite{#1}{#2}} \gdef\primed#1{ {#1}^{\prime}} \gdef\tinybullet{ {\tiny●}} \gdef\forwardFactor{\uparrow} \gdef\backwardFactor{\downarrow} \gdef\neutralFactor{\mid} \gdef\arrowhead{⏵} \gdef\deSymbol{ { { {\raisebox{1.1pt}{\tinybullet}\mkern{-1pt}{→}}}\,}} \gdef\ueSymbol{ {\raisebox{1pt}{\tinybullet\raisebox{-0.03em}{\mkern{-0.3pt}{\tiny──}\mkern{-0.3pt}}\tinybullet}\,}} \gdef\ldeSymbol{ { { {\raisebox{1.1pt}{\tinybullet}\mkern{-1pt}{\longrightarrow}}}\,}} \gdef\lueSymbol{ {\raisebox{1pt}{\tinybullet\raisebox{-0.03em}{\mkern{-0.3pt}{\tiny────}\mkern{-0.3pt}}\tinybullet}\,}} \gdef\de#1#2{ { {#1} \deSymbol {#2}}} \gdef\ue#1#2{ { {#1} \ueSymbol {#2}}} \gdef\tde#1#2#3{ { {#1} \overset{#3}{\deSymbol} {#2}}} \gdef\tue#1#2#3{ { {#1} \overset{#3}{\ueSymbol} {#2}}} \gdef\ltde#1#2#3{ { {#1} \overset{#3}{\ldeSymbol} {#2}}} \gdef\ltue#1#2#3{ { {#1} \overset{#3}{\lueSymbol} {#2}}} \gdef\mapsfrom{\htmlClass{hreflect}{\mapsto}} \gdef\longmapsfrom{\htmlClass{hreflect}{\longmapsto}} \gdef\diffd{𝕕} \gdef\partialdof#1{\partial {#1}} \gdef\emptySet{\empty} \gdef\unknown{\wbform{\text{?}}} \gdef\notApplicable{\wbform{\text{---}}} \gdef\isomorphicSymbol{\cong} \gdef\homotopicSymbol{\simeq} \gdef\approxEqualSymbol{\approx} \gdef\defEqualSymbol{\;≝\;} \gdef\ruledelayed{:\to} \gdef\mathdollar{\text{\textdollar}} \gdef\hyphen{\text{-}} \gdef\endash{\text{--}} \gdef\emdash{\text{---}} \gdef\updownarrows{\uparrow\!\downarrow} \gdef\vthinspace{\mkern{1pt}} \gdef\dlq{\text{\textquotedblleft}} \gdef\drq{\text{\textquotedblright}} \gdef\dprime{ {\prime\prime}} \gdef\inverse#1{ { {#1}^{-1}}} \gdef\inverseSymbol{\inverse{□}} \gdef\groupInverse{\inverse} \gdef\groupPower#1#2{ {#1}^{#2}} \gdef\groupCommutator#1#2{\left[{#1},{#2}\right]} \gdef\groupoidInverse{\inverse} \gdef\latticeBFS#1{\textrm{bfs}({#1})} \gdef\pathHomomorphism#1{#1} \gdef\groupoidFunction#1{#1} \gdef\affineModifier#1{\overrightharpoon{#1}} \gdef\supercirc#1{#1^{\circ}} \gdef\supercircb#1{#1\!\degree} \gdef\toroidalModifier#1{\supercirc{#1}} \gdef\modulo#1{\supercirc{#1}} \gdef\dividesSymbol{\,|\,} \gdef\groupFunction#1{#1} \gdef\gl#1#2{GL({#1},#2)} \gdef\automorphisms{\operatorname{Aut}} \gdef\transportMap#1{\transportMapSymbol_{#1}} \gdef\transportMapSymbol{\tau} \gdef\cardinalGroup#1{G^*({#1})} \gdef\signed#1{ {#1}^*} \gdef\transportAtlas#1{T_{#1}} \gdef\negated#1{\underline{#1}} \gdef\mirror#1{\overline{#1}} \gdef\pathComposeSymbol{ {\,∷\,}} \gdef\pathCompose#1#2{ {#1}\pathComposeSymbol{#2}} \gdef\translateSymbol{\uparrow} \gdef\backwardTranslateSymbol{\downarrow} \gdef\pathTranslate#1#2{ {#1}\,\translateSymbol\,{#2}} \gdef\pathLeftTranslate#1{ {#1}{\,\translateSymbol}} \gdef\pathBackwardTranslate#1#2{ {#1}{\,\backwardTranslateSymbol\,}{#2}} \gdef\pathLeftBackwardTranslate#1{ {#1}{\,\backwardTranslateSymbol}} \gdef\forwardDifference{\Delta^{+}} \gdef\backwardDifference{\Delta^{-}} \gdef\centralDifference{\Delta} \gdef\pathForwardDifference#1{\forwardDifference_{#1}} \gdef\pathBackwardDifference#1{\backwardDifference_{#1}} \gdef\pathCentralDifference#1{\centralDifference_{#1}} \gdef\pathHeadVector#1{ {#1}^{\bullet}} \gdef\pathTailVector#1{ {#1}_{\bullet}} \gdef\pathReverse#1{ {#1}^{\dagger}} \gdef\pathIntegral#1#2{ {#1} \int {#2}} \gdef\pathIntegralSymbol{ {\int}} \gdef\pathDot#1#2{ {#1} \cdot {#2}} \gdef\pathDotSymbol{ {\cdot}} \gdef\compactBasis#1{\mathscr{B}} \gdef\length{\operatorname{len}} \gdef\signedLength{\operatorname{len^*}} \gdef\andFn{\operatorname{and}} \gdef\orFn{\operatorname{or}} \gdef\notFn{\operatorname{not}} \gdef\vertexList{\operatorname{vertices}} \gdef\vertexList{\operatorname{vertices}} \gdef\edgeList{\operatorname{edges}} \gdef\pathList{\operatorname{paths}} \gdef\cardinalList{\operatorname{cards}} \gdef\signedCardinalList{\operatorname{cards^*}} \gdef\wordOf{\operatorname{word}} \gdef\headVertex{\operatorname{head}} \gdef\tailVertex{\operatorname{tail}} \gdef\basis{\operatorname{basis}} \gdef\split{\operatorname{split}} \gdef\lcm{\operatorname{lcm}} \gdef\minimalContractionSets{\operatorname{MCSets}} \gdef\minimalContractions{\operatorname{MC}} \gdef\grade{\operatorname{grade}} \gdef\support{\operatorname{support}} \gdef\isPrime#1{#1\textrm{ prime}} \gdef\blank{\_} \gdef\emptyWord{} \gdef\wordSymbol#1{\mathtt{#1}} \gdef\word#1{#1} \gdef\pathMap#1{#1} \gdef\function#1{#1} \gdef\pathWord#1#2#3{ {#1}\!:\!{#2}\!:\!{#3}} \gdef\nullPath{\bot} \gdef\nullElement{\bot} \gdef\path#1{#1} \gdef\vert#1{#1} \gdef\tvert#1{\underset{\raisebox{0.3em}{.}}{#1}} \gdef\hvert#1{\dot{#1}} \gdef\edge#1{#1} \gdef\card#1{\mathtt{#1}} \gdef\path#1{#1} \gdef\quiver#1{#1} \gdef\bindSize#1#2{#1(#2)} \gdef\bindCards#1#2{#1[#2]} \gdef\subSize#1#2{#1_{#2}} \gdef\gridQuiver#1{\textrm{Grid}^{#1}} \gdef\treeQuiver#1{\textrm{Tree}^{#1}} \gdef\bouquetQuiver#1{\textrm{Bq}^{#1}} \gdef\lineQuiver{\textrm{L}} \gdef\cycleQuiver{\textrm{C}} \gdef\squareQuiver{\textrm{Sq}} \gdef\cubicQuiver{\textrm{Cbc}} \gdef\triangularQuiver{\textrm{Tri}} \gdef\hexagonalQuiver{\textrm{Hex}} \gdef\rhombilleQuiver{\textrm{Rmb}} \gdef\limit#1#2{\lim_{#2}\,#1} \gdef\groupoid#1{#1} \gdef\group#1{#1} \gdef\field#1{#1} \gdef\ring#1{#1} \gdef\semiring#1{#1} \gdef\sym#1{#1} \gdef\matrix#1{#1} \gdef\matrixDotSymbol{\cdot} \gdef\wordGroup#1{\Omega_{#1}} \gdef\basisPath#1#2{\mathbf{#1}_{#2}} \gdef\basisPathWeight#1#2{ {#1}_{#2}} \gdef\unitSymbol{\mathbf{e}} \gdef\unitVertexField{\unitSymbol_1} \gdef\forwardSymbol{f} \gdef\backwardSymbol{b} \gdef\symmetricSymbol{s} \gdef\antisymmetricSymbol{a} \gdef\wordVector#1#2{\unitSymbol_{#1}^{#2}} \gdef\gradOf#1{\grad\,{#1}} \gdef\grad{\nabla} \gdef\divOf#1{\div\,{#1}} \gdef\div{\dot{\nabla}} \gdef\laplacianOf#1{\laplacian\,{#1}} \gdef\laplacian{\ddot{\nabla}} \gdef\suchThat#1#2{ {#1}|{#2}} \gdef\chart#1{\chartSymbol_{#1}} \gdef\chartSymbol{C} \gdef\graphRegionIntersectionSymbol{\cap} \gdef\graphRegionUnionSymbol{\cup} \gdef\pathIso{\simeq} \gdef\power#1#2{ {#1}^{#2}} \gdef\repeatedPower#1#2{ {#1}^{#2}} \gdef\contractionLattice#1{\operatorname{Con}(#1)} \gdef\contractedRelation#1{\sim_{#1}} \gdef\isContracted#1#2{ {#1} \sim {#2}} \gdef\isContractedIn#1#2#3{ {#1} \sim_{#3} {#2}} \gdef\isNotContracted#1#2{ {#1} \not \sim {#2}} \gdef\isNotContractedIn#1#2#3{ {#1} \not \sim_{#3} {#2}} \gdef\contractionSum#1{#1} \gdef\contractionSumSymbol{\sqcup} \gdef\contractionProduct#1{#1} \gdef\contractionProductSymbol{ {\cdot}} \gdef\graph#1{#1} \gdef\graphHomomorphism#1{#1} \gdef\coversSymbol{\sqsupseteq} \gdef\coveredBySymbol{\sqsubseteq} \gdef\strictlyCoversSymbol{\sqsupset} \gdef\strictlyCoveredBySymbol{\sqsubset} \gdef\covering#1#2#3{ {#2} \sqsupseteq_{#1} {#3}} \gdef\powerSet#1{\powerSetSymbol({#1})} \gdef\powerSetSymbol{\mathsc{P}} \gdef\notted#1{\notSymbol {#1}} \gdef\andSymbol{\land} \gdef\orSymbol{\lor} \gdef\notSymbol{\lnot} \gdef\latticeElement#1{#1} \gdef\latticeMeetSymbol{\wedge} \gdef\latticeJoinSymbol{\vee} \gdef\latticeTop{\top} \gdef\latticeBottom{\bot} \gdef\latticeGreaterSymbol{>} \gdef\latticeGreaterEqualSymbol{\ge} \gdef\latticeLessSymbol{<} \gdef\latticeLessEqualSymbol{\le} \gdef\symmetricGroup#1{Sym_{#1}} \gdef\groupPresentation#1#2{\left\langle\,{#1}\,\,\middle|\mathstrut\,\,{#2}\,\right\rangle} \gdef\groupRelationIso{=} \gdef\groupGenerator#1{#1} \gdef\groupElement#1{#1} \gdef\groupoidElement#1{#1} \gdef\setConstructor#1#2{\left\{\,{#1}\,\,\middle|\mathstrut\,\,{#2}\,\right\}} \gdef\constructor#1#2{\left.{#1}\,\,\middle|\mathstrut\,\,{#2}\right.} \gdef\elemOf#1#2{ { {#1} \in {#2} }} \gdef\edgeOf#1#2{ { {#1} {\in}_E {#2} }} \gdef\vertOf#1#2{ { {#1} {\in}_V {#2} }} \gdef\pathOf#1#2{ { {#1} {\in}_P {#2} }} \gdef\vertices#1{ V_{#1} } \gdef\edges#1{ E_{#1} } \gdef\vertexField#1{#1} \gdef\edgeField#1{#1} \gdef\pathVector#1{\mathbf{#1}} \gdef\pathVectorSpace#1{\mathscr{#1}} \gdef\baseField#1{#1} \gdef\finiteField#1{\mathbb{F}_{#1}} \gdef\functionSpace#1#2{#2^{#1}} \gdef\pathGroupoid#1{ { \Gamma_{#1} }} \gdef\forwardPathQuiver#1#2{ {\overrightharpoon{#1}_{#2}}} \gdef\backwardPathQuiver#1#2{ {\overrightharpoon{#1}^{#2}}} \gdef\pathQuiver#1{ {\overrightharpoon{#1}}} \gdef\mto#1#2{ {#1}\mapsto{#2}} \gdef\mtoSymbol{\mapsto} \gdef\rewrite#1#2{ {#1}\mapsto{#2}} \gdef\rewritingRule#1#2{ {#1}\mapsto{#2}} \gdef\rewritingSystem#1{\mathcal{#1}} \gdef\multiwayBFS#1{\textrm{bfs}({#1})} \gdef\rewritingStateBinding#1#2{ {\left.{#1}\!\mid\!{#2}\right.}} \gdef\rewritingRuleBinding#1#2{#1{\left[\,{#2}\,\right]}} \gdef\namedSystem#1{\mathsf{#1}} \gdef\genericRewritingSystem{\namedSystem{System}} \gdef\stringRewritingSystem{\namedSystem{Str}} \gdef\turingMachineRewritingSystem{\namedSystem{TM}} \gdef\cellularAutomatonRewritingSystem{\namedSystem{CA}} \gdef\graphRewritingSystem{\namedSystem{Gr}} \gdef\hypergraphRewritingSystem{\namedSystem{HGr}} \gdef\petriNetRewritingSystem{\namedSystem{Petri}} \gdef\ncard#1{\card{\negated{#1}}} \gdef\mcard#1{\card{\mirror{#1}}} \gdef\nmcard#1{\card{\negated{\mirror{#1}}}} \gdef\assocArray#1{\left\langle {#1} \right\rangle} \gdef\list#1{\{ {#1} \}} \gdef\tuple#1{( {#1} )} \gdef\concat#1{ {#1} } \gdef\paren#1{\left( {#1} \right)} \gdef\ceiling#1{\lceil{#1}\rceil} \gdef\floor#1{\lfloor{#1}\rfloor} \gdef\translationVector#1{\left[{#1}\right]_{\textrm{T}}} \gdef\quotient#1#2{ {#1} / {#2}} \gdef\compactQuotient#1#2#3{ {#1}\;{\upharpoonright_{#2}}\;{#3}} \gdef\multilineQuotient#1#2{\frac{#1}{#2}} \gdef\idElem#1{e_{#1}} \gdef\minus#1{-{#1}} \gdef\elem{\ \in\ } \gdef\gmult{\,\ast\,} \gdef\Gmult{\,\ast\,} \gdef\ellipsis{\dots} \gdef\appliedRelation#1{#1} \gdef\setUnionSymbol{\cup} \gdef\setIntersectionSymbol{\cap} \gdef\cartesianProductSymbol{\times} \gdef\functionSignature#1#2#3{ { {#1} : {#2} \to {#3}}} \gdef\poly#1{#1} \gdef\quiverProdPoly#1{#1} \gdef\quiverProdPower#1#2{#1^{#2}} \gdef\quiverProdTimes#1{#1} \gdef\parenLabeled#1#2{#1\ ({#2})} \gdef\modLabeled#1#2{ {#1 }\textrm{ mod }{#2}} \gdef\cyclicGroup#1{\mathbb{Z}_{#1}} \gdef\componentSuperQuiverOfSymbol{\succ} \gdef\setCardinality#1{|{#1}|} \gdef\dependentQuiverProductSymbol{\,\times\,} \gdef\independentQuiverProductSymbol{\,⨝\,} \gdef\graphUnionSymbol{\sqcup} \gdef\graphProductSymbol{\times} \gdef\inlineProdSymbol{\mid} \gdef\serialCardSymbol{ {:}} \gdef\parallelCardSymbol{ {\mid}} \gdef\cardinalSequenceSymbol{ {:}} \gdef\cardinalProductSymbol{\inlineProdSymbol} \gdef\vertexProductSymbol{\!\inlineProdSymbol\!} \gdef\edgeProductSymbol{\inlineProdSymbol} \gdef\indexSum#1#2#3{ {\sum_{#2}^{#3} #1}} \gdef\indexProd#1#2#3{ {\prod_{#2}^{#3} #1}} \gdef\indexMax#1#2#3{ {\max_{#2}^{#3} #1}} \gdef\indexMin#1#2#3{ {\min_{#2}^{#3} #1}} \gdef\oneTo#1{1..{#1}} \gdef\zeroTo#1{0..{#1}} \gdef\qstring#1{\mathtt{"}{#1}\mathtt{"}} \gdef\qchar#1{\mathtt{'}{#1}\mathtt{'}} \gdef\lstr#1{\mathtt{#1}} \gdef\lchar#1{\mathtt{#1}} \gdef\string#1{ {#1}} \gdef\character#1{ {#1}} \gdef\translationCardinalValuation#1{\textrm{T}_{#1}} \gdef\starTranslationCardinalValuation#1{\textrm{T}^*_{#1}} \)
Coverings

Coverings

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. 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. Coverings are also naturally associated with contractions in which we "glue together" sets of vertices, and we can interpret any covering in this way.

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" 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 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, we can construct a more elaborate surjective homomorphism that nevertheless still "lengthens" some paths:

Clearly, having the covering graph be disconnected gives us considerable freedom.

Another counterexample to the hypothesis that (surjective) path homomorphisms yield coverings involves a 1-path being 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. 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:

\[ \quiver{Q} = \compactQuotient{\quiver{F}}{\vert{v}}{\groupoidFunction{ \phi }} \]

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