# The weak categorical quiver minor theorem and its applications: matchings,
multipaths, and magnitude cohomology

Luigi Caputi  ,  Carlo Collari  and  Eric Ramos

###### Abstract.

Building upon previous works of Proudfoot and Ramos, and using the categorical
framework of Sam and Snowden, we extend the weak categorical minor theorem
from undirected graphs to quivers. As case of study, we investigate the
consequences on the homology of multipath complexes; eg. on its torsion.
Further, we prove a comparison result: we show that, when restricted to
directed graphs without oriented cycles, multipath complexes and matching
complexes yield functors which commute up to a blow-up operation on directed
graphs. We use this fact to compute the homotopy type of matching complexes
for a certain class of bipartite graphs also known as half-graphs or ladders.
We complement the work with a study of the (representation) category of cones,
and with analysing related consequences on magnitude cohomology of quivers.

##  1\. Introduction

The graph minor theorem of Robertson and Seymour [RS04] states that the
undirected graphs, partially ordered by the graph minor relationship, form a
well-quasi-ordering. If one restricts to graphs with bounded combinatorial
genus, this fact has a categorical enhancement which was recently explored by
Miyata and the third author in [MR23]. It is shown in [MR23] that the (weak)
categorical minor theorem is related to Noetherian properties of the
(representation) category of undirected graphs with bounded genus. Remarkably,
this relationship has non-trivial topological and combinatorial consequences.
With a view to such consequences, in this paper we extend the (weak)
categorical version of the graph minor theorem to quivers and directed graphs.
Inspired by previous works, and in particular by [Bar15, PR19, PR22], we
borrow techniques from representation theory of categories. Sam and Snowden,
in fact, developed a fascinating and powerful machinery to prove that a
certain representation category is Noetherian [SS17]. Their approach makes use
of combinatorial properties – called _(quasi-) Gröbner_ properties – on the
base category: if a category $\mathbf{C}$ is quasi-Gröbner, then its category
of representations $\mathbf{Rep}_{R}\mathbf{C}$, over a Noetherian ring $R$,
is Noetherian.

The category $\mathbf{Graph}_{\leq g}^{\mathrm{op}}$ of undirected graphs with
bounded genus $g$, and opposite minor morphisms, was shown to be quasi-Gröbner
in [PR22]. As a consequence, all subrepresentations of finitely generated
representations of $\mathbf{Graph}_{\leq g}^{\mathrm{op}}$ are also finitely
generated. This fact has some striking applications to the study of certain
simplicial complexes associated to graphs, such as those arising from monotone
properties of graphs, cf. [PR22, MR23]. The study of such simplicial complexes
and, in particular, of matching complexes is a well-established [Wac03, SW04,
Jon08a] and yet vibrant area of research [ĬPVZ20, MJMV22, Sin22, Mat22,
MMS23]. In particular, the behaviour of the torsion appearing in the homology
of matching complexes has been a subject of considerable attention – see
[SW04, Jon10], and references therein. Using the fact that the category
$\mathbf{Graph}_{\leq g}^{\mathrm{op}}$ is quasi-Gröbner, Miyata and the third
author approached the study of torsion of matching complexes from a different
perspective. They proved, in [MR23], that if one considers graphs of bounded
genus, then the homology of their matching complexes has universally bounded
torsion. It is an open conjecture whether a similar statement holds true when
considering the whole category of graphs, with no restriction on the genus –
see [MR23, Conjecture 3.3].

In this work, we go beyond the undirected case, and prove that also the
category of quivers $\mathbf{Quiver}$, and minor morphisms, is combinatorially
well-behaved;

######  Theorem 1.1 (Weak categorical quiver minor theorem).

The category $\mathbf{Quiver}_{\leq g}^{\mathrm{op}}$ is quasi-Gröbner.

As a consequence, simplicial complexes associated to quivers of bounded genus,
such as those arising from monotone properties of directed graphs, are
finitely generated (under some additional mild assumptions). As case of study
we consider _multipath complexes_ [CCDTS24], which also include cycle-free
chessboard complexes [VŽ09]. The interest in studying the homology of
multipath complexes stems from their subtle relations with Hochschild homology
[TW12] and symmetric homology of algebras [AF07, Aul10]. Furthermore,
multipath complexes are related to, and sometimes coincide with, matching
complexes, see [CCC]. In the spirit of [MR23], we use Theorem 1.1 to
investigate the global behaviour of the homology of multipath complexes. Let
$X\colon\mathbf{Quiver}^{\mathrm{op}}\to\textbf{SimplComp}$ be the functor
associating to each quiver its multipath complex. First, we prove that, for
any fixed $i,g\in\mathbb{N}$, the homology
$\mathrm{H}_{i}(X(-);\mathbb{Z})\colon\mathbf{Quiver}^{\mathrm{op}}_{\leq
g}\to\mathbf{Mod}_{R}$ is a finitely generated
$\mathbf{Quiver}^{\mathrm{op}}_{\leq g}$-module (Proposition 4.6). Then, we
show that the torsion in $\mathrm{H}_{i}(X(-);\mathbb{Z})$ is universally
bounded for quivers of bounded genus (Proposition 4.7).

In a different direction, we analyse further the connection between matching
and multipath complexes. To this end, we introduce the notion of blow-up
$B({\tt G})$ of a directed graph ${\tt G}$, see Definition 4.15. We show, in
Theorem 4.20, that the multipath complex of a directed graph ${\tt G}$ without
oriented cycles and the matching complex of the underlying undirected graph of
$B({\tt G})$ are isomorphic. The blow-up construction defines a functor
$\mathbf{B}$ from the category of directed graphs without oriented cycles (and
injective morphisms of digraphs) $\mathbf{Digraph}_{o}$ to the opposite of the
category of undirected graphs (and minor morphisms)
$\mathbf{Graph}^{\mathrm{op}}$. Then, Theorem 4.20 can be restated by saying
that the diagram

(1)
${\mathbf{Digraph}_{o}}$${\mathbf{Graph}^{\mathrm{op}}}$${\mathbf{SimpCompl}}$$\scriptstyle{\mathbf{B}}$$\scriptstyle{X}$$\scriptstyle{M}$

is commutative up to isomorphism of simplicial complexes; see also Corollary
4.22. Here, we have denoted with $M$ the functor associating to each
undirected graph its matching complex. We infer the following direct
comparison result:

######  Theorem 1.2.

Multipath complexes of directed graphs without oriented cycles are isomorphic
to (joins of) matching complexes of bipartite graphs.

$p_{1}$$p_{2}$$p_{3}$$q_{1}$$q_{2}$$q_{3}$ Figure 1. The bipartite graph ${\tt
B}_{3}$.

Diagram (1) and Theorem 1.2 show that, when restricting to digraphs without
oriented cycles, computations of matching complexes can be obtained by
equivalent computations of multipath complexes, in turn providing a way to
compute the homotopy type of new families of matching complexes. We give here
a main example. Let ${\tt B}_{n}$ be the undirected graph – sometimes called
half-graph or ladder [NORS21] – on $2n$ vertices $p_{1},\dots,p_{n}$ and
$q_{1},\dots,q_{n}$, and edges $(p_{i},q_{j})$ for all $i\leq j$ – see Figure
1.

######  Theorem 1.3.

The matching complex of ${\tt B}_{n}$ is either contractible or homotopy
equivalent to a wedge of spheres.

We complement the paper with two more main directions. The first, regarding
the theoretical description of the combinatorial properties of the category of
quivers, aims to shed light on the analog of [MR23, Conjecture 3.3] for
quivers. Trying to enlarge the category for which the weak categorical minor
theorem is true, we prove in Proposition 3.10 that the category of cones of
graphs with bounded genus is also quasi-Gröbner. This is beneficial to
(partially) get around the restriction of bounded genus. For instance, the
cone category includes such families as the wheel graphs, which are cones over
cycles, and the Thagomizer graphs, which are cones over star trees. The second
direction concerns some applications of the categorical machinery of Sam and
Snowden to homology theories of digraphs which do not (directly) arise from
monotone properties of digraphs. Our main example is _magnitude homology_ of
graphs [HW17]. Magnitude homology is the categorification of magnitude, as
defined by Leinster – see, for example, the book [Lei21] – capturing many
interesting properties of graphs [Gom19, Asa21, Asa23, AHK23, TY23]. In
[CC23], the first two authors proved that magnitude cohomology of undirected
graphs is finitely generated; in turn, getting new insight about the torsion
in magnitude homology – see also [KY21, SS21]. We extend in Section 5 the
results of [CC23] to the category of quivers. Using the work of Asao [Asa23],
we also get in Corollary 5.11 some insight on the torsion of the path homology
of quivers, introduced in [GMVY18].

We conclude with a perspective on homology theories of digraphs and quivers,
whose interest in recent years has skyrocketed due to connections to
persistence and topological data analysis. If [MR23, Conjecture 3.3] were
true, we could extend the results of this paper to all (directed) graphs,
without restriction on the genus. In this work, we focused on two main
examples of cohomology theories of simplicial complexes deriving from quivers.
However, in view of a better understanding of the (weak) categorical minor
theorem, it would be interesting to investigate also further cohomology
theories of graphs, quivers and categories. To name a few, some recent
intriguing examples, related to magnitude homology, are for example
reachability homology [HR23, CR23], spectral homology [Iva23], or those
introduced in [IP23, Rof23].

### Conventions and notation

All (directed) graphs and quivers are assumed to be finite, and are denoted in
typewriter font, e.g. ${\tt Q},{\tt G}$. Unless otherwise specified, $R$ will
denote a Noetherian commutative ring with identity. All categories are in bold
font. We mainly use the following categories of graphs:

$\mathbf{Graph}$ | undirected graphs and minor morphisms
---|---
$\mathbf{Digraph}$ | digraphs and minor morphisms
$\mathbf{Quiver}$ | quivers and minor morphisms
$\mathbf{CGraph}$ | undirected graphs and contractions
$\mathbf{CDigraph}$ | digraphs and contractions
$\mathbf{CQuiver}$ | quivers and contractions
$\mathbf{Digraph}_{o}$ | directed graphs without directed cycles and injective morphisms of digraphs
$\mathbf{Graph}_{g}$ | undirected graphs of genus $g$ and contractions
$\mathbf{Digraph}_{g}$ | digraphs of genus $g$ and contractions
$\mathbf{Quiver}_{g}$ | quivers of genus $g$ and contractions
$\mathbf{CGraph}_{\leq g}$ | undirected graphs of genus at most $g$ and contractions
$\mathbf{CDigraph}_{\leq g}$ | digraphs of genus at most $g$ and contractions
$\mathbf{CQuiver}_{\leq g}$ | quivers of genus at most $g$ and contractions
$\mathbf{Graph}_{\leq g}$ | undirected graphs of genus at most $g$ and minor morphisms
$\mathbf{Digraph}_{\leq g}$ | digraphs of genus at most $g$ and minor morphisms
$\mathbf{Quiver}_{\leq g}$ | quivers of genus at most $g$ and minor morphisms
$\text{Cone}(\mathbf{Quiver}_{\leq g})$ | cone over quivers of genus at most $g$ and minor morphisms of the base quiver

While we listed them here for the readers’ convenience, the precise definition
of these categories will be given throughout the paper.

##  2\. Basic notions

In this section, we recall some basic notions and set the notations needed
throughout.

###  2.1. Quivers

Recall that a (finite) _quiver_ ${\tt Q}$ consists of two finite sets $V({\tt
Q})$ and $E({\tt Q})$, together with a pair of functions $s,t\colon E({\tt
Q})\to V({\tt Q})$. The elements of $V({\tt Q})$ are called _vertices_ , while
the elements of $E({\tt Q})$ are called  _edges_. For each $e\in E({\tt Q})$
the vertices $s(e)$ and $t(e)$ are the _source_ and the _target_ of $e$,
respectively, and they are collectively called the _endpoints_ of $e$. A
_morphism of quivers_ $f\colon{\tt Q}\to{\tt Q^{\prime}}$ is given by a pair
of functions $f_{V}\colon V({\tt Q})\to V({\tt Q}^{\prime})$ and $f_{E}\colon
E({\tt Q})\to E({\tt Q}^{\prime})$, such that the two diagrams

${E({\tt Q})}$${V({\tt Q})}$${E({\tt Q}^{\prime})}$${V({\tt
Q}^{\prime})}$$\scriptstyle{f_{E}}$$\scriptstyle{s}$$\scriptstyle{f_{V}}$$\scriptstyle{s^{\prime}}$

and ${E({\tt Q})}$${V({\tt Q})}$${E({\tt Q}^{\prime})}$${V({\tt
Q}^{\prime})}$$\scriptstyle{f_{E}}$$\scriptstyle{t}$$\scriptstyle{f_{V}}$$\scriptstyle{t^{\prime}}$

commute. Note that morphisms of quivers can send an edge to a self-loop.

Special cases of quivers are _digraphs_. These are quivers such that each edge
$e$ is completely determined by the (ordered) pair of its endpoints
$(s(e),t(e))$. An _undirected graph_ ${\tt G}$ is a quiver together with a map
$r\colon E({\tt G})\to E({\tt G})$, called _reflection_ , which is an
involution such that $s\circ r=t$. An undirected edge in an undirected graph
refers to a pair of edges in the underlying quiver which are swapped by the
reflection. Note that any morphism of quivers between two undirected graphs
commutes with the respective reflections.

######  Remark 2.1.

We will often identify each edge $e$ in a digraph with the ordered pair
$(s(e),t(e))$. Similarly, if the quiver underlying an undirected graph is a
digraph, we will identify each undirected edge with the unordered collection
of its endpoints.

A _subquiver_ ${\tt H}$ of a quiver ${\tt Q}$ is a quiver such that $V({\tt
H})\subseteq V({\tt Q})$, $E({\tt H})\subseteq E({\tt Q})$, and both source
and target functions are given by restriction. If ${\tt H}$ is a subquiver of
${\tt Q}$, we write ${\tt H}\leq{\tt Q}$. If ${\tt H}$ is a subquiver of ${\tt
Q}$, and $V({\tt H})=V({\tt Q})$, then we say that ${\tt H}$ is _spanning_ in
${\tt Q}$. A subquiver of a digraph is automatically a digraph. However, a
subquiver of an undirected graph may not be an undirected graph. Subquivers of
undirected graphs which are undirected graphs with reflection defined by
restriction are called _subgraphs_. To be coherent with the classical
terminology, we will refer also to subquivers of digraphs as _subgraphs_.

A quiver ${\tt Q}$ has a geometric realization $|{\tt Q}|$. This is the
geometric realization of the CW complex whose $0$-cells are the vertices of
the quiver, $1$-cells are the edges of the quiver, and the attaching maps are
given by the source and target maps. In the case of undirected graphs we will
take the quotient by the action of the reflection. We define the _genus_ of a
quiver (resp. undirected graph) as the first Betti number of its geometric
realisation. A (_directed_) _tree_ ${\tt T}$ is an undirected graph (resp.
quiver) whose genus is $0$ or, equivalently, whose geometric realization
$|{\tt T}|$ is contractible.

Given a quiver ${\tt Q}$ and an edge $e\in E({\tt Q})$, we can define two
quivers ${\tt Q}\setminus e$ and ${\tt Q}/e$, called respectively the
_deletion_ and the _contraction_ of $e$. The former is the subquiver of ${\tt
Q}$ obtained by removing $e$ from the set of edges. The latter is the quiver
whose edges are $E({\tt Q})\setminus e$, whose vertices are the quotient of
$V({\tt Q})$ by the identification $t(e)=s(e)$, and whose source and target
maps are defined as follows: $s(e^{\prime})=[s(e^{\prime})]$ and
$t(e^{\prime})=[t(e^{\prime})]$, where the brackets denote the equivalence
class. Less formally, ${\tt Q}/e$ is obtained from (the geometric realization
of) ${\tt Q}$ by contracting $e$ to a point. Contraction and deletion of
undirected graphs are defined similarly; the only change is that we remove
both $e$ and $r(e)$, and then we define the reflection as the map induced by
the original reflection.

Note that the operation of contracting edges does not change the homotopy type
of the geometric realization, unless the edge contracted is a self loop. We
are not going to consider this latter case, and only allow contractions of
edges with distinct endpoints. Similarly, when dealing with deletions, we will
only allow deletions whose geometric realization is connected.

A minor of a quiver (resp. undirected graph) ${\tt Q}^{\prime}$ is a quiver
(resp. undirected graph) ${\tt Q}$ that is isomorphic to a quiver (resp.
undirected graph) obtained from ${\tt Q}^{\prime}$ by iterative contractions
and deletions. More formally, we have the following definition of minor
morphisms of quivers.

######  Definition 2.2.

A _minor morphism_ $\phi\colon{\tt G}^{\prime}\to{\tt G}$ of quivers is a map
of sets

$\phi\colon V({\tt G}^{\prime})\sqcup E({\tt G}^{\prime})\sqcup\\{\star\\}\to
V({\tt G})\sqcup E({\tt G})\sqcup\\{\star\\}\ ,$

such that:

  * •

$\phi(V({\tt G}^{\prime}))=V({\tt G})$ and $\phi(\star)=\star$;

  * •

if an edge $e\in E({\tt G}^{\prime})$ has endpoints $(s(e),t(e))=(v,w)$, and
$\phi(e)\neq\star$, then either $\phi(e)=\phi(v)=\phi(w)$ is a vertex of ${\tt
G}$, or $\phi(e)$ is an edge of ${\tt G}$ with endpoints $s(\phi(e))=\phi(v)$
and $t(\phi(e))=\phi(w)$;

  * •

there is a bijection between $\phi^{-1}(E({\tt G}))$ and $E({\tt G})$;

  * •

for each vertex $v\in{\tt G}$, the preimage $\phi^{-1}(v)$ as a subquiver of
${\tt G}^{\prime}$ is a directed tree.

If there is a minor morphism $\phi\colon{\tt G}^{\prime}\to{\tt G}$ we will
say that ${\tt G}$ is a _minor_ of ${\tt G}^{\prime}$. The definition of minor
morphism of undirected graphs is the same, but the words “edge”, “directed
tree”, and “subquiver” are replaced by “undirected edge”‘, “tree”, and
“subgraph”, respectively.

The preimage of $\star$ under $\phi$ consists of deleted edges, whereas the
edges that are mapped to vertices of ${\tt G}$ represent the contracted ones.
Furthermore, the last item in the definition implies that self loops cannot be
contracted, but only deleted.

A _simple path_ , or _directed path_ , in a quiver ${\tt Q}$ is subquiver
whose edges can be ordered $e_{1},...,e_{n}$ in such a way that (i)
$s(e_{i+1})=t(e_{i})$ for each $i<n$, (ii) no vertex is encountered twice,
i.e. if $s(e_{i})=s(e_{j})$ or $t(e_{i})=t(e_{j})$ then $i=j$, and (iii)
$s(e_{1})\neq t(e_{n})$. A subquiver of ${\tt Q}$ satisfying properties (i)
and (ii), but not (iii), in the definition of simple path is called _oriented
cycle_. We call _alternating_ any quiver ${\tt Q}$ such that the sets
$t(E({\tt Q})),s(E({\tt Q}))\subset V({\tt Q})$ are disjoint.

######  Example 2.3.

The alternating quiver ${\tt A}_{n}$ in Figure 2 has a simple path ${\tt
I}_{m}$, with $m\leq\lfloor\frac{n}{2}\rfloor$ edges, as a minor (but not as a
subquiver). More generally, the simple path ${\tt I}_{1}$ is a minor of any
directed tree.

We get the categories $\mathbf{Graph}$ and $\mathbf{Quiver}$ of undirected
graphs and quivers, respectively, with minor morphisms. The category
$\mathbf{Digraph}$ is the full subcategory of $\mathbf{Quiver}$ spanned by
digraphs. Analogously, we denote by $\mathbf{CGraph}$ and $\mathbf{CQuiver}$
the categories of graphs and quivers, respectively, with only contractions as
allowed morphisms. The category $\mathbf{CDigraph}$ is also defined, as the
full subcategory of $\mathbf{CQuiver}$ spanned by digraphs.

######  Remark 2.4.

There is a pair of functors $\iota\colon\mathbf{Quiver}\to\mathbf{Graph}$ and
$\rho\colon\mathbf{Graph}\to\mathbf{Quiver}$. The latter is just the forgetful
functor which forgets the reflection. Intuitively, $\rho$ makes each
undirected edge of a graph bidirectional. The functor $\iota$ instead replaces
each edge with an undirected edge. We will refer to $\iota({\tt Q})$ as the
underlying graph of ${\tt Q}$.

$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{n-1}$$\dots$$v_{n}$ Figure 2.
The alternating linear quiver ${\tt A}_{n}$ on $n+1$ vertices. The edge
between $v_{n-1}$ and $v_{n}$ can be oriented either way depending on the
parity of $n$.

###  2.2. Finitely generated $\mathbf{C}$-modules

Let $\mathbf{C}$ be a (essentially) small category, and $A$ be a ring. A
_representation_ of $\mathbf{C}$, or _${\bf C}$ -module_, _over $A$_ is a
functor $\mathcal{M}\colon\mathbf{C}\to A\text{\bf-Mod}$ with values in the
category of (left) $A$-modules. Denote by ${\mathbf{Rep}}_{A}(\mathbf{C})$ the
category of $\mathbf{C}$-modules over $A$ where morphisms are given by natural
transformations.

A _submodule_ of a $\mathbf{C}$-module $\mathcal{M}$ is a $\mathbf{C}$-module
$\mathcal{N}$ such that $\mathcal{N}(c)$ is a $A$-submodule of
$\mathcal{M}(c)$, for each object $c\in\mathbf{C}$. If $S$ is a subset of
$\bigoplus_{c\in\mathbf{C}}\mathcal{M}(c)$, the _span of $S$_, denoted by
$\mathrm{span}(S)$, is the minimal $\mathbf{C}$-submodule of $\mathcal{M}$
containing $S$.

######  Definition 2.5.

A $\mathbf{C}$-module $\mathcal{M}$ is _finitely generated_ if there is a
finite set $S\subseteq\bigoplus_{c\in\mathbf{C}}\mathcal{M}(c)$, such that
$\mathrm{span}(S)=\mathcal{M}$.

We can also characterise finitely generated modules in terms of simpler
modules. For each object $c$ of $\mathbf{C}$, define a _principal projective
$\mathbf{C}$-module_ $\mathcal{P}_{c}$, as follows

$\mathcal{P}_{c}(c^{\prime})\coloneqq
A\langle\operatorname{\mathrm{Hom}}_{\mathbf{C}}(c,c^{\prime})\rangle,\quad\text{for
each }c^{\prime}\in\mathbf{C}\ ,$

i.e. the free (left) $A$-module spanned by
$\operatorname{\mathrm{Hom}}_{\mathbf{C}}(c,c^{\prime})$, and
$\mathcal{P}_{c}$ is then defined on morphisms by (post)composition. Given a
morphism $\gamma\colon c\to c^{\prime}$, we denote by $e_{\gamma}$ the
corresponding element in $\mathcal{P}_{c}(c^{\prime})$.

######  Lemma 2.6 ([CEFN14, Proposition 2.3]).

A $\mathbf{C}$-module $\mathcal{M}$ is finitely generated if and only if there
exists a surjection

$\bigoplus_{i=1}^{n}\mathcal{P}_{c_{i}}\to\mathcal{M}$

for some objects $c_{1},\dots,c_{n}$ of $\mathbf{C}$.

For a finitely generated $\mathbf{C}$-module $\mathcal{M}$, we refer to the
objects $c_{1},\dots,c_{n}$ of $\mathbf{C}$ in the lemma as _generators_ of
$\mathcal{M}$.

######  Definition 2.7.

A $\mathbf{C}$-module $\mathcal{M}$ is _Noetherian_ if all its submodules are
finitely generated. The category ${\mathbf{Rep}}_{A}(\mathbf{C})$ is (locally)
Noetherian if all finitely generated $\mathbf{C}$-modules over $A$ are
Noetherian.

Observe that, in discussing properties related to finite generation, it is
often possible to restrict to principal projective modules. Indeed, by [SS17,
Proposition 3.1.1], the category ${\mathbf{Rep}}_{A}(\mathbf{C})$ is
Noetherian if and only if every principal projective module $\mathcal{P}_{c}$
is Noetherian.

######  Example 2.8.

Let $\mathbf{FI}$ be the category of finite sets and injective maps. Then, by
[CEFN14, Theorem A], the category ${\mathbf{Rep}}_{R}(\mathbf{FI})$ is
Noetherian, for any (commutative Noetherian) ring $R$.

Noetherian properties of various other categories have been extensively
investigated, in particular thanks to the techniques developed by Sam and
Snowden in [SS17]. One of the main results in the latter paper is that, for a
given category $\mathbf{C}$ (under some combinatorial assumptions), and a
(possibly non-commutative) left Noetherian ring $R$, the associated category
of representations is Noetherian as well. Before recalling the combinatorial
conditions to be required on the category $\mathbf{C}$, and stating the main
result in this section, we need a definition. Let
$\mathcal{F}\colon\mathbf{C}\to\mathbf{D}$ be a functor between essentially
small categories.

######  Definition 2.9.

We say that $\mathcal{F}$ satisfies _property (F)_ if for every object
$d\in\mathbf{D}$ there exist finitely many objects $c_{1},\dots,c_{n}$ of
$\mathbf{C}$, and morphisms $\delta_{i}\colon d\to\mathcal{F}(c_{i})$, such
that: for any object $c$ in $\mathbf{C}$, and morphism $\delta\colon
d\to\mathcal{F}(c)$, there exists a morphism $\gamma_{i}\colon c_{i}\to c$
satisfying $\delta=\mathcal{F}(\gamma_{i})\circ\delta_{i}$.

Observe that a functor that is surjective on both objects and morphisms
satisfies property (F). Property (F) allows us to transfer finitely generated
properties through functors. In fact, the following holds:

######  Proposition 2.10 ([SS17, Proposition 3.2.3]).

If a functor $\mathcal{F}\colon\mathbf{C}\to\mathbf{D}$ satisfies property
(F), and $\mathcal{M}\colon\mathbf{D}\to R\text{\bf-Mod}$ is finitely
generated, then
$\mathcal{F}^{*}\mathcal{M}\coloneqq\mathcal{M}\circ\mathcal{F}\colon\mathbf{C}\to
R\text{\bf-Mod}$ is finitely generated.

We need to introduce some further notation and terminology; see also [SS17,
Section 4.1] for a more extensive overview. Let ${\bf
S}\colon\mathbf{C}\to\mathbf{Set}$ be a functor with values in the category of
sets. We associate a poset $|{\bf S}|$ to ${\bf S}$ as follows. First, take
$\widetilde{{\bf S}}$ to be the union $\bigcup_{c\in\mathbf{C}}{\bf S}(c)$.
Then, for an element $f$ in ${\bf S}(c)$ and an element $g$ in ${\bf
S}(c^{\prime})$, set $f\leq g$ if and only if there exists a morphism $h\colon
c\to c^{\prime}$ in $\mathbf{C}$ such that ${{\bf S}(h)(f)=}h_{*}(f)=g$.
Consider the equivalence relation $\sim$ defined by $f\sim g$ if and only if
$f\leq g$ and $g\leq f$. Then, the poset $|{\bf S}|$ is defined as the
quotient of the set $\widetilde{{\bf S}}$ with respect to $\sim$, equipped
with the partial order induced from $\leq$.

######  Definition 2.11.

An _ordering_ on ${\bf S}\colon\mathbf{C}\to\mathbf{Set}$ is a choice of a
well-order on ${\bf S}(c)$ for each $c$ in $\mathbf{C}$, such that for every
morphism $c\to c^{\prime}$ the induced map ${\bf S}(c)\to{\bf S}(c^{\prime})$
is strictly order-preserving; in such a case, we say that ${\bf S}$ is
_orderable_.

We say that a poset $P$ is Noetherian if, for every infinite sequence
$x_{1},x_{2},\dots$ in $P$, there exist indices $i<j$ such that $x_{i}\leq
x_{j}$ (cf. [SS17, Proposition 2.1]). We can now recall the fundamental
definition of Gröbner category.

######  Definition 2.12.

An essentially small category $\mathbf{C}$ is _Gröbner_ if, for all objects
$c$ of $\mathbf{C}$, the functor ${\bf
S}_{c}\coloneqq\operatorname{\mathrm{Hom}}_{\mathbf{C}}(c,-)$ is orderable,
and the associated poset $|{\bf S}_{c}|$ is Noetherian. An essentially small
category $\mathbf{C}$ is _quasi-Gröbner_ if there exists a Gröbner category
$\widetilde{\mathbf{C}}$ and an essentially surjective functor
$\widetilde{\mathbf{C}}\to\mathbf{C}$ satisfying property (F).

Roughly speaking, a category is said to be _Gröbner_ if its slice categories
are restrictive enough, so that representations of the category allow for a
theory of “Gröbner bases”. The category ${\bf FI}$ from Example 2.8 is not a
Gröbner category, as its automorphism groups are symmetric groups, hence non-
trivial. However, ${\bf FI}$ is quasi-Gröbner:

######  Remark 2.13.

Let $\mathbf{OI}$ be the category of linearly ordered finite sets and ordered
inclusions. This is a “rigidified” version of the category ${\bf FI}$; in
particular, it has trivial automorphism groups. It was shown in [SS17, Theorem
7.1.2] that $\mathbf{OI}$ is indeed a Gröbner category, and that the functor
$\mathbf{OI}\to{\bf FI}$ is an essentially surjective functor satisfying
property (F). As a consequence, ${\bf FI}$ is quasi-Gröbner.

The next result follows readily from the definitions:

######  Proposition 2.14.

Let $\mathcal{F}\colon\mathbf{C}\to\mathbf{D}$ be a functor satisfying
property (F). If $\mathbf{C}$ is a quasi-Gröbner category, and $\mathcal{F}$
is essentially surjective, then $\mathbf{D}$ is a quasi-Gröbner category.

###### Proof.

Composition of essentially surjective functors is essentially surjective.
Moreover, the composition of functors satisfying property (F) satisfies
property (F) by [SS17, Proposition 3.2.6]. ∎

Assume now that $R$ is a left Noetherian ring. The following is one of the
main results connecting combinatorial properties of a category with the
Noetherianity of the category of representations.

######  Theorem 2.15 ([SS17, Theorem 1.1.3]).

If $\mathbf{C}$ is a quasi-Gröbner category, then the category
${\mathbf{Rep}}_{A}(\mathbf{C})$ is Noetherian.

In particular, if $R$ is a left Noetherian ring and $\mathbf{C}$ is quasi-
Gröbner, all submodules and quotients of finitely generated functors
$\mathcal{M}\colon\mathbf{C}\to R\text{\bf-Mod}$ are also finitely generated.

##  3\. Gröbner properties of $\mathbf{Quiver}$ and $\mathbf{Digraph}$

The primary goal of this section is to prove that certain subcategories of
$\mathbf{Quiver}^{\mathrm{op}}$ and $\mathbf{Digraph}^{\mathrm{op}}$ are
Noetherian.

######  Definition 3.1.

Let $g$ be a non-negative integer. The category $\mathbf{Quiver}_{g}$ (resp.
$\mathbf{Quiver}_{\leq g}$) is the full subcategory of $\mathbf{Quiver}$ whose
objects are quivers of genus $g$ (resp. at most $g$). The categories
$\mathbf{Digraph}_{g}$ and $\mathbf{Digraph}_{\leq g}$ are defined in the same
fashion.

Observe that in both $\mathbf{Quiver}_{g}$ and $\mathbf{Digraph}_{g}$, the
only minor morphisms that appear are automorphisms and contractions, as
deletions never preserve genus. On the other hand, among the morphisms in
$\mathbf{Quiver}_{\leq g}$ and $\mathbf{Digraph}_{\leq g}$ there are both
deletions and contractions.

For technical reasons, we need to define “rigidified” versions of the above
categories. These will play a prominent role in the proof of this section’s
main theorem. First, recall that a _rooted spanning tree_ for a quiver ${\tt
G}$ is a pair $({\tt T},v_{r})$, where ${\tt T}$ is a spanning subquiver of
${\tt G}$ which is a directed tree, and $v_{r}$ is a fixed vertex of ${\tt T}$
called root. Note that, just as any connected subquiver, ${\tt T}$ is obtained
from ${\tt G}$ by subsequent deletions. We set $P\mathbf{Quiver}_{g}$ to be
the category whose objects are _undirected_ graphs of genus $g$, enhanced with
the following extra information:

  1. (1)

a choice of rooted spanning tree;

  2. (2)

a choice of planar embedding for the aforementioned spanning tree;

  3. (3)

a choice of orientation for the edges outside of this spanning tree;

  4. (4)

at each non-root vertex, a label indicating whether that vertex is the source
or target of the (unique) edge of the spanning tree leading from the vertex to
the root.

The morphisms of this category will be edge contractions (and automorphisms)
of the underlying graphs, which preserve all of the above structure. We
similarly define $P\mathbf{Digraph}_{g}$.

######  Remark 3.2.

The reader might find it strange that we defined the category
$P\mathbf{Quiver}_{g}$ by starting with undirected graphs, and then adding
extra information that effectively orients them. The reason for this relates
with our ultimate proof that this category is Gröbner. The idea is that we
start with planar trees, and then add the data of the edge orientations and
the extra edges in such a way that they can be encoded into the vertices of
the tree. This way, we will be able to use a version of Kruskal’s Tree
theorem, which allows for the vertices of the tree to be labelled.

######  Remark 3.3.

We observe that our category $P\mathbf{Quiver}_{g}$ is a minor modification of
the category $\mathcal{P}\mathcal{G}_{g}$ in [PR22]. Indeed, the main
difference between the two categories lies in the labels on the vertices of
the spanning tree. The important point is that this extra data is _finite_ in
nature; this means that our vertices are being given labels from a finite set
(source and target). This will allow us to apply [PR22, Corollary 3.7].

To prove that representations of $\mathbf{Quiver}_{\leq g}^{\mathrm{op}}$ and
$\mathbf{Digraph}_{\leq g}^{\mathrm{op}}$ have our desired Noetherian
property, we will use the Gröbner methods of Sam and Snowden [SS17]. To
summarize, for each fixed $g$, we will proceed as follows:

  * •

We show that the category $P\mathbf{Quiver}_{g}^{\mathrm{op}}$ is Gröbner;

  * •

we show that the forgetful functor
$P\mathbf{Quiver}_{g}^{\mathrm{op}}\rightarrow\mathbf{Quiver}_{g}^{\mathrm{op}}$
has Property (F) and is essentially surjective;

  * •

finally, we argue that the natural inclusion $\bigsqcup_{q\leq
g}\mathbf{Quiver}_{q}^{\mathrm{op}}\hookrightarrow\mathbf{Quiver}_{\leq
g}^{\mathrm{op}}$ has Property (F) and is essentially surjective.

Once we have completed each of the above steps, [SS17, Theorem 1.1.3] (cf.
Theorem 2.15) will immediately imply our desired Noetherian Property.

Note that in our outline we have not said anything about the category
$\mathbf{Digraph}_{\leq g}$! To justify why, we have the following standard
proposition.

######  Proposition 3.4.

The category $P\mathbf{Digraph}_{\leq g}^{\mathrm{op}}$ is Gröbner provided
that $P\mathbf{Quiver}_{\leq g}^{\mathrm{op}}$ is.

###### Proof.

By construction the category $P\mathbf{Digraph}_{\leq g}$ is a full
subcategory of $P\mathbf{Quiver}_{\leq g}$. The Gröbner property is inherited
by full subcategories per [SS17, Proposition 4.4.2]. ∎

The above proposition justifies why the first step in our outline need not be
repeated for the two categories. We will see that the latter two steps can be
proven identically in the digraph case, and therefore it is unnecessary to
repeat them. In particular, the above represents the crux of why we will only
be working with the quiver categories from this point forward in this section.

######  Proposition 3.5.

For any $g\geq 0$ the category $P\mathbf{Quiver}_{g}^{\mathrm{op}}$ is
Gröbner.

###### Proof.

In [PR22, Theorem 3.10] it is proven that the category
$\mathcal{P}\mathcal{G}_{g,S}^{\mathrm{op}}$ is Gröbner where $S$ is any
finite (or even well-quasi-ordered) set of permissible vertex labels. Consider
the case wherein $S=\\{s,t\\}$. $P\mathbf{Quiver}_{g}$ is a full subcategory
of $\mathcal{P}\mathcal{G}_{g,S}^{\mathrm{op}}$ in this case. It follows that
$\mathcal{P}\mathcal{G}_{g,S}^{\mathrm{op}}$ is Gröbner by the same argument
given in the prior proposition. ∎

Following our outline, our next goal is to now show that the forgetful functor
$P\mathbf{Quiver}_{g}\rightarrow\mathbf{Quiver}_{g}$ has Property (F) and is
essentially surjective. It is clear that every quiver in $\mathbf{Quiver}_{g}$
is in the image of the forgetful functor. Property (F) follows immediately
from [PR22, Lemma 3.11]. To conclude our proof it therefore remains to show
that the embedding $\bigsqcup_{q\leq
g}\mathbf{Quiver}_{q}^{\mathrm{op}}\hookrightarrow\mathbf{Quiver}_{\leq
g}^{\mathrm{op}}$ is essentially surjective with property (F).

######  Lemma 3.6.

Fix $g\geq 0$. The embedding $\bigsqcup_{q\leq
g}\mathbf{Quiver}_{q}^{\mathrm{op}}\hookrightarrow\mathbf{Quiver}_{\leq
g}^{\mathrm{op}}$ is essentially surjective with property (F).

###### Proof.

Let ${\tt Q}$ be a quiver of genus at most $g$, and let $\\{\phi_{i}\colon{\tt
Q}_{i}\rightarrow{\tt Q}\\}$ be an exhaustive list of all possible _deletions_
that terminate at ${\tt Q}$. Note that by a deletion we mean a minor morphism
for which no edge is contracted and at least one edge is deleted. Further note
that because our genus $g$ is fixed, and because deletions always strictly
decrease genus when applied, this collection is finite.

To prove that our embedding has (F), we must argue that for any quiver ${\tt
Q}^{\prime}$ of genus at most $g$ and any minor morphism $\psi\colon{\tt
Q}^{\prime}\rightarrow{\tt Q}$ we can find an $i$ and an edge contraction
$\eta\colon{\tt Q}^{\prime}\rightarrow{\tt Q}_{i}$, such that
$\psi=\phi_{i}\circ\eta$. Indeed, this just amounts to the statement that any
minor morphism can be written as a composition of a deletion followed by an
edge contraction. ∎

Let going forward, we will write $\mathbf{CQuiver}_{\leq g}$ to denote the
category $\bigsqcup_{q\leq g}\mathbf{Quiver}_{q}^{\mathrm{op}}$, of quivers of
genus at most $g$ and contractions. To summarize the work of this section, we
have proven the following.

######  Theorem 3.7.

The categories $\mathbf{Quiver}_{\leq g}^{\mathrm{op}}$,
$\mathbf{CQuiver}_{\leq g}^{\mathrm{op}}$, and $\mathbf{Digraph}_{\leq
g}^{\mathrm{op}}$ are quasi-Gröbner.

Consider the _edge module_

$\mathcal{E}_{g}\colon(\mathbf{Quiver}_{\leq
g})^{\mathrm{op}}\to\mathbf{Mod}_{R}$

which associates to a quiver ${\tt Q}$ the free $R$-module
$\mathcal{E}_{g}({\tt Q})$ generated by the set $E({\tt Q})$ of edges of ${\tt
Q}$. For any minor morphism, there is a well-defined inclusion of edges in the
opposite direction of the contraction. This in turn induces maps between the
aforementioned free modules.

######  Proposition 3.8.

Let $d$ be a natural number. Then, the module $\mathcal{E}_{g}^{\otimes d}$ is
a finitely generated $\mathbf{Quiver}_{\leq g}^{\mathrm{op}}$-module.

###### Proof.

The proof follows the same arguments of [MR23, Lemma 4.2]; by replacing the
sets of edges with the sets of _directed_ edges. ∎

Although defined in a similar way, note that the vertex module

$\mathcal{V}\colon\mathbf{Quiver}_{\leq g}^{\mathrm{op}}\to\mathbf{Mod}_{R}$

is not finitely generated. However, we have the following:

######  Proposition 3.9.

Let $R$ be a ring with identity. Then, ${\rm Hom}(\mathcal{V}^{\oplus k},R)$
is finitely generated, as $\mathbf{Quiver}^{\mathrm{op}}_{\leq g}$-module, for
each $k$.

###### Proof.

The proof follows the same arguments of [CC23, Theorem 3.11], with only two
small changes: the edges of ${\tt R}(m)$ have to be oriented, and the quiver
${\tt S}(m_{1},m_{2},m_{2}^{\prime},m_{3})$ in Figure 3 replaces the graph
${\tt S}(m_{1},m_{2},m_{3})$ used in [CC23].

$\dots$$\dots$$m_{1}$$m_{3}$$\vdots$$\vdots$$m_{2}$$m^{\prime}_{2}$ Figure 3.
The graph ${\tt S}(m_{1},m_{2},m_{2}^{\prime},m_{3})$. The edge in blue goes
from $v_{1}$ to $v_{2}$.

∎

###  3.1. Categories of directed cones

For a given quiver ${\tt G}$, a _cone_ over ${\tt G}$, denoted
$\text{Cone}({\tt G})$, is a quiver obtained by adding a new vertex to ${\tt
G}$, while also adding (directed) edges to connect it with every vertex of
${\tt G}$. Note that for our purposes, the added _cone point_ is connected to
each vertex of ${\tt G}$ by exactly one edge. In other words, we do not allow
for multi-edges connected to the cone point.

Let ${\tt G},{\tt G}^{\prime}$ be two quivers. Then a _base contraction_ from
$\text{Cone}({\tt G})$ to $\text{Cone}({\tt G}^{\prime})$ is a minor morphism
$\text{Cone}({\tt G})\rightarrow\text{Cone}({\tt G}^{\prime})$ involving the
contraction of edges of ${\tt G}$, thought of as living inside of
$\text{Cone}({\tt G})$, followed by the deletion of the newly created
multiedges that are connected to the cone point of $\text{Cone}({\tt
G}^{\prime})$. Similarly, a _base deletion_ is a minor morphism
$\text{Cone}({\tt G})\rightarrow\text{Cone}({\tt G}^{\prime})$ involving the
deletion of edges of ${\tt G}$, thought of as a subquiver of $\text{Cone}({\tt
G})$. More generally, a _base minor morphism_ is any minor morphism
$\text{Cone}({\tt G})\rightarrow\text{Cone}({\tt G}^{\prime})$ that can be
written as a composition of base contractions and base deletions. We will
write $\text{Cone}(\mathbf{Quiver}_{\leq g})$ for the category of directed
cones whose base graph has genus at most $g$, and whose morphisms are base
minor morphisms.

Our first result will tell us that representations of the cone category
satisfy a Noetherian Property.

######  Proposition 3.10.

The category $\text{Cone}(\mathbf{Quiver}_{\leq g})^{\mathrm{op}}$ is quasi-
Gröbner. In particular, subrepresentations of finitely generated
representations of $\text{Cone}(\mathbf{Quiver}_{\leq g})^{\mathrm{op}}$ are
also finitely generated.

###### Proof.

We begin with the category $P\mathbf{Quiver}_{\leq g}^{\mathrm{op}}$, and
modify its objects to add an extra label to each vertex. Specifically, this
label will be either ’u’ (for up) or ’d’ (for down). We also modify our
morphisms to insist that the newly added label must be preserved. This new
category will be Gröbner following an essentially identical proof to
Proposition 3.5.

Consider now the functor from our new category to
$\text{Cone}(\mathbf{Quiver}_{\leq g})^{\mathrm{op}}$, which sends every
object to the cone over its underlying graph, while orienting the cone edges
in the direction dictated by the vertex labels. A morphism in our category
naturally defines a morphism in $\text{Cone}(\mathbf{Quiver}_{\leq
g})^{\mathrm{op}}$ by performing the analogous base deletions and
contractions. In the case of a contraction, the cone edges which are deleted
by the corresponding base contraction are precisely those whose vertices were
originally further from the selected spanning tree’s root.

Our functor is essentially surjective by constuction, and it is immediate that
every base deletion and contraction appears in the image of some map. In
particular, our functor has property (F), as desired. ∎

One benefit of the cone category is that it allows us to (partially) get
around the restriction of bounded genus. For instance,
$\text{Cone}(\mathbf{Quiver}_{\leq g})^{\mathrm{op}}$ includes such families
as the Wheel graphs, which are cones over cycles, and the Thagomizer graphs,
which are cones over star trees.

######  Remark 3.11.

The idea to expand categories of bounded genus by considering cones was first
done by Proudfoot and the third author in [PR19]. In that work, only
undirected trees are considered. This work will therefore expand previous
applications both by allowing for higher genera bases, and also allowing for
the edges - cone or otherwise - to be directed.

For our applications in the sections that follow, we will need to state an
analogous result to Proposition 3.8. Once again the proof is similar to that
of [MR23].

######  Proposition 3.12.

The $\text{Cone}(\mathbf{Quiver}_{\leq g})^{\mathrm{op}}$-module,

${\tt G}\mapsto\mathbb{Z}^{|E({\tt G})|}$

is finitely generated. Moreover, the same is true of its tensor powers.

##  4\. Applications to multipath complexes

In this section, we apply the abstract technology of Section 3 to simplicial
complexes arising from monotone properties of directed graphs [Jon08b]. More
specifically, we will deal with multipath complexes [CCDTS24].

###  4.1. Multipath complexes and their torsion

We are interested in the monotone property of digraphs on disjoint sets of
simple paths; following [TW12, CCDT], we call them multipaths:

######  Definition 4.1.

A _multipath_ of a quiver ${\tt G}$ is a spanning subquiver such that each
connected component is either a vertex or a simple path. The _length_ of a
multipath is the number of its edges.

The _path poset_ of a quiver ${\tt G}$ is the poset $(P({\tt G}),\leq)$, where
$P({\tt G})$ is the set of multipaths in ${\tt G}$ (including the multipath
with no edges), ordered by the relation of being a subgraph. To the path poset
$P({\tt G})$ we associate a simplicial complex:

######  Definition 4.2 ([CCDT23, Definition 6.2]).

For a quiver ${\tt G}$, the _multipath complex_ $X({\tt G})$ is the simplicial
complex whose face poset (augmented to include the empty simplex $\emptyset$)
is the path poset $P({\tt G})$.

$v_{0}$$v_{1}$$v_{2}$$v_{3}$$(v_{0},v_{1})$$(v_{1},v_{2})$$(v_{2},v_{3})$

Figure 4. The coherently oriented linear graph ${\tt I}_{3}$ (top left), the
multipath complex $X({\tt I}_{3})$ (top right), and the path poset $P({\tt
I}_{3})$ (bottom).

Equivalently, $X({\tt G})$ is the simplicial complex on the edges of ${\tt G}$
whose $k$-simplices are given by the multipaths in ${\tt G}$ of length $k-1$.
When ${\tt G}$ is the complete digraph, the associated simplicial complex is
also called _cycle free chessboard complex_ , denoted $\Omega_{n}$ in [VŽ09].
Since being a multipath is a monotone property of digraphs, that is it is
closed under subgraphs – cf. [BW99] or [Jon08b], it follows that $X({\tt G})$
is a well-defined simplicial complex.

######  Lemma 4.3.

The association ${\tt G}\mapsto X({\tt G})$ yields a functor

$X\colon\mathbf{Quiver}^{\mathrm{op}}\to\mathbf{SimplComp}$

to the category of simplicial complexes and simplicial maps.

###### Proof.

Let $\phi\colon{\tt G}^{\prime}\to{\tt G}$ be a minor morphism of quivers.
Then, the morphism $\phi^{\mathrm{op}}$ is injective on the set of edges: for
$e$ an edge of ${\tt G}$, $\phi^{\mathrm{op}}(e)$ is again an edge, of ${\tt
G}^{\prime}$. Furthermore, $\phi^{\mathrm{op}}$ preserves the adjacency
relation, hence it sends simple paths to simple paths, and, in turn,
multipaths to multipaths. Lengths and containment relations are also
preserved, from which we get a simplicial map $X({\tt G})\to X({\tt
G}^{\prime})$. As the construction preserves identities and compositions, the
statement follows. ∎

Denote by $\ast$ the join operation of simplicial complexes – cf. [Koz08,
Definition 2.16]. Then, for quivers ${\tt G}$ and ${\tt H}$, we have
isomorphisms

(2) $X({\tt G}\sqcup{\tt H})\cong X({\tt G})\ast X({\tt H})\ ,$

where $\sqcup$ denotes the disjoint union; see also [CCDTS24, Remark 2.6]. We
observe that the disjoint union on $\mathbf{Quiver}$ and the join on ${\bf
SimplComp}$ yields monoidal structures on the respective categories. Equaition
(2) implies that the functor $X$ is symmetric monoidal, up to isomorphism of
simplicial complexes.

######  Example 4.4.

Consider the coherently oriented linear digraph ${\tt I}_{n}$ – see Figure 4
for an illustration of the quiver ${\tt I}_{3}$. The path poset $(P({\tt
I}_{n}),\leq)$ is isomorphic to the Boolean poset $\mathbb{B}(n)$. Thence, the
associated multipath complex is an $(n-1)$-dimensional simplex. Likewise,
consider the coherently oriented polygonal digraph ${\tt P}_{n}$ with $n$
edges, obtained from ${\tt I}_{n}$ by identifying the vertices $v_{0}$ and
$v_{n}$. Then, the path poset $(P({\tt P}_{n}),\leq)$ is isomorphic to the
Boolean poset $\mathbb{B}(n)$ minus its maximum, and the corresponding
multipath complex is a $(n-2)$-dimensional sphere. Further, if we consider the
minor morphism $\phi\colon{\tt I}_{n}\to{\tt I}_{n-1}$ given by the
contraction of the edge $(v_{n-1},v_{n})$, then $X(\phi^{\mathrm{op}})$ is the
inclusion of the $(n-2)$-dimensional simplex into the boundary of the
$(n-1)$-dimensional simplex as the subcomplex of the latter spanned by all
vertices, but one.

As often happens to simplicial complexes associated to monotone properties of
graphs, it is easy to find multipath complexes which are homotopy equivalent
to wedges of spheres, and, in particular, torsion free. Examples of such
complexes are those associated to directed trees. In fact, as we shall see
below, the multipath complex of a directed tree is homotopy equivalent to the
join of matching complexes of undirected trees, cf. Proposition 4.11. On the
other hand, matching complexes of trees are contractible or homotopy
equivalent to wedges of spheres [MT08, Theorem 4.13]. It follows that the
multipath complex of a directed tree is either contractible or homotopy
equivalent to a wedge of spheres. Further, the complexity of wedges of spheres
which can be realised, up to homotopy, as multipath complexes of directed
trees can be arbitrarily high; for instance, for each $n$, multipath complexes
of directed trees homotopy equivalent to the wedge of an arbitrary number of
$n$-dimensional spheres are given in the proof of [CCDT23, Proposition 6.12].

The fact that the multipath complex of an alternating digraph coincides with
the matching complex of the underlying undirected graph [CCC] can be used to
find multipath complexes whose homology is not torsion free:

######  Example 4.5.

Let ${\tt K}_{n,m}$ be the complete bipartite (undirected) graph on $m,n$
vertices. When equipped with an alternating orientation, the multipath complex
$X({\tt K}_{n,m})$ coincides with the matching complex of ${\tt K}_{n,m}$ and
its homology groups can have torsion. The minimal values of $m$ and $n$ for
which the homology groups of $X({\tt K}_{n,m})$ have torsion are $m=n=5$, and
in such case there is $3$-torsion [SW04].

The torsion in the homology of matching complexes of undirected graphs with
genus less or equal than a fixed number was shown to be bounded in [MR23,
Theorem 1.2]. Therefore, when restricting to complete bipartite graphs with
alternating orientation, the torsion of multipath complexes is also bounded.
We want to extend this result to categories of quivers with bounded genus. In
the spirit of the techniques presented in Section 3, we first need to show
that the homology of multipath complexes yields a finitely generated module.

######  Proposition 4.6.

For each $i\in\mathbb{N}$, the homology functor

$\mathrm{H}_{i}(X(-);\mathbb{Z})\colon\mathbf{Quiver}^{\mathrm{op}}_{\leq
g}\to\mathbf{Mod}_{R}$

is a finitely generated $\mathbf{Quiver}^{\mathrm{op}}_{\leq g}$-module.

###### Proof.

The proof follows the same ideas as [MR23, Theorem 4.3]. First, we observe
that taking chain complexes and homology in a fixed degree is functorial with
respect to taking minors. Using Lemma 4.3, we infer that the functor
$\mathrm{H}_{i}(X(-);\mathbb{Z})$ is a $\mathbf{Quiver}^{\mathrm{op}}_{\leq
g}$-module. Furthermore, $\mathrm{H}_{i}(X(-);\mathbb{Z})$ is a subquotient of
the tensor product $\mathcal{E}_{g}^{\otimes i}$ of the edge module; this
module is finitely generated over $\mathbf{Quiver}^{\mathrm{op}}_{\leq g}$ by
Proposition 3.8. The statement follows by Theorem 2.15. ∎

As a consequence of Proposition 4.6, we have that torsion of multipath
complexes is bounded:

######  Proposition 4.7.

For every pair of integers $i,g\geq 0$, there exists $m=m(g,i)\in\mathbb{Z}$
which annihilates the torsion subgroup of $H_{i}(X({\tt G});\mathbb{Z})$, for
each quiver ${\tt G}$ of genus at most $g$.

###### Proof.

The proof follows the arguments of [MR23, Theorem 3.20], which we include for
the sake of completeness. Denote by $T_{i}({\tt G})$ the torsion submodule of
the homology of multipath complex of ${\tt G}$ in (homological) degree $i$.
The functor $T_{i}$ is a $\mathbf{Quiver}_{\leq g}^{\mathrm{op}}$-submodule of
$\mathrm{H}_{i}(X(-);\mathbb{Z})$. Then, in virtue of Proposition 4.6 and by
Theorem 2.15, it follows that $T_{i}$ is a finitely generated
$\mathbf{Quiver}_{\leq g}^{\mathrm{op}}$-module. By Lemma 2.6, there is a
finite number of quivers ${\tt G}_{1},\dots,{\tt G}_{k}$, such that there is a
surjective group homomorphism

$\bigoplus_{j=1}^{k}T_{i}({\tt G}_{j})\twoheadrightarrow T_{i}({\tt G})\,,$

for each quiver ${\tt G}$ of genus at most $g$. Thus, the least common
multiple of the exponents of $T_{i}({\tt G}_{1}),\dots,T_{i}({\tt G}_{k})$
gives the desired $m(g,i)$. ∎

We wish to point out here that the statements in Proposition 4.6 and
Proposition 4.7 can be extended to monotone properties $P$ of directed graphs,
or quivers, which satisfy the following additional property: if
$\phi\colon{\tt G}\to{\tt G}^{\prime}$ is a minor morphism and
$\sigma^{\prime}$ is a simplex in $X_{P}({\tt G}^{\prime})$, then the subgraph
of ${\tt G}$ induced by the image $\phi^{*}(E(\sigma^{\prime}))$ is also in
$P$. Here we have denoted by $X_{P}({\tt G})$ the simplicial complex
associated to ${\tt G}$ via the monotone proeperty $P$. In the case of the
multipaths, note that the corresponding monotone property satisfies this
condition. Another interesting monotone property of digraphs is given by (the
complex of) directed forests. In such case, as by [Eng09], the complex of
directed forests of graphs without oriented cycles is shellable; hence, it has
no torsion. This observation leads to the following question, whose answer is
not known to the authors:

######  Question 4.8.

Does the complex of directed forests of graphs with oriented cycles contain
torsion?

The terminology of this last part of the section is taken from [CCDTS24], and
we will limit our discussion to digraphs (rather than all quivers).

Let ${\tt G}$ be a digraph, and let ${\tt G}^{\prime}\leq{\tt G}$ be a
subgraph. The _complement_ $C_{{\tt G}}({\tt G}^{\prime})$ of ${\tt
G}^{\prime}$ in ${\tt G}$ is the subgraph of ${\tt G}$ spanned by the edges in
$E({\tt G})\setminus E({\tt G}^{\prime})$. The _boundary_ $\partial_{{\tt
G}}{\tt G}^{\prime}$ of ${\tt G}^{\prime}$ in ${\tt G}$, or simply
$\partial{\tt G}^{\prime}$ when ${\tt G}$ is clear from the context, is
defined as $\partial_{{\tt G}}{\tt G}^{\prime}=V({\tt G}^{\prime})\cap
V(C_{{\tt G}}({\tt G}^{\prime}))$.

######  Definition 4.9.

Let ${\tt G}$ be a connected digraph with at least one edge and without self-
loops. A vertex $v\in V({\tt G})$ is called _stable_ if it is not, at the same
time, a source and a target (i.e. if it does not belong to the intersection
$s(E({\tt G}))\cap t(E({\tt G}))$), and is _unstable_ otherwise. A _dynamical
region_ in ${\tt G}$ is a connected subgraph ${\tt R}\leq{\tt G}$, with at
least one edge, such that:

  1. (a)

all vertices in the boundary of ${\tt R}$ are unstable in ${\tt G}$, but
stable in both ${\tt R}$ and $C_{{\tt G}}({\tt R})$;

  2. (b)

no edge of ${\tt R}$ belongs to any oriented cycle in ${\tt G}$ which is not
contained in ${\tt R}$.

A dynamical region is called _stable_ if all its non-boundary vertices are
stable. It is called _unstable_ if all its non-boundary vertices are unstable,
and it has at least one non-boundary vertex. A dynamical region which has no
proper subgraph which is itself a dynamical region is called a _dynamical
module_.

######  Lemma 4.10.

Let ${\tt M}$ be a dynamical module of a connected directed tree. Then, ${\tt
M}$ is stable.

###### Proof.

Let ${\tt T}$ be a directed tree, and ${\tt M}\leq{\tt T}$ a dynamical module.
Assume, by contradiction, that ${\tt M}$ is not stable. Then, there is at
least an unstable vertex $v$ not in the boundary of ${\tt M}$. Since $v$ is an
unstable vertex in ${\tt M}$ there are some edges, say $e_{1},\dots,e_{h}\in
E({\tt M})$, such that $s(e_{i})=v$, and some edges, say $f_{1},\dots,f_{k}\in
E({\tt M})$, such that $t(f_{j})=v$, for $k,h\geq 1$.

Since ${\tt T}$ is a directed tree, so is ${\tt M}$. In particular, deleting
the edges $e_{1},...,e_{h}$ disconnects ${\tt M}$. Denote by ${\tt R}$ the
connected component containing the edges $f_{1},...,f_{k}$. We argue that
${\tt R}$ is a dynamical region of ${\tt M}$, and this yields the desired
contradiction. First, ${\tt R}$ being a subgraph of ${\tt M}\leq{\tt T}$
implies that item (b) in the definition of dynamical region is automatically
satisfied. Observe that $v$ is the unique vertex in the boundary of ${\tt R}$
in ${\tt M}$. In fact, given $w\neq v$ in $V({\tt R})$ all edges of ${\tt M}$
incident in $w$ are also edges of ${\tt R}$. Otherwise, one of the $e_{i}$’s
would be incident to $w$ and we would have a closed loop in (the geometric
realisation of) ${\tt T}$, e.g. by taking an (unoriented) path from $v$ to $w$
in ${\tt R}$ and then adding $e_{i}$. Since $v$ is unstable in ${\tt M}$ and
is, by construction, stable both in ${\tt R}$ and in $C_{{\tt M}}({\tt R})$,
the statement follows. ∎

Stable dynamical regions are alternating digraphs. Therefore, the multipath
complex of a stable dynamical region ${\tt R}$ in a directed graph ${\tt G}$
is the matching complex of the underlying undirected graph of ${\tt R}$ – cf.
[CCDTS24, Lemma 4.8]. As a consequence of this fact, we get the following:

######  Proposition 4.11.

Let ${\tt T}$ be a connected directed tree. Then, $X({\tt T})$ is homotopy
equivalent to a join of matching complexes of (undirected) trees.

###### Proof.

By [CCDTS24, Theorem 1], there is a unique (up to re-ordering) decomposition
of ${\tt G}$ into dynamical modules ${\tt M}_{1},...,{\tt M}_{k}$, and we have
an isomorphism

$X({\tt G})\cong X({\tt M}_{1})\ast\cdots\ast X({\tt M}_{k})\ .$

By Lemma 4.10, each ${\tt M}_{i}$ is stable, hence each $X({\tt M}_{i})$ is
the matching complex of the underlying undirected tree of ${\tt M}_{i}$. The
statement follows. ∎

A straightforward corollary follows, strengthening some of the results
contained in [CCDTS24].

######  Corollary 4.12.

The multipath complex of a forest is either contractible or homotopy
equivalent to a wedge of spheres.

Hence, a direct consequence of Proposition 4.11 is that the homology of
multipath complexes of directed trees does not contain any torsion. In order
to get interesting torsion, one needs to consider non-acyclic quivers.
However, when the quivers contain directed cycles, computations of the
homology groups are more involved – and often computationally exponential.
Therefore, it would be interesting to know more about the global growth of the
ranks of the homology groups. By applying similar arguments as in [PR22,
Proposition 4.3], the ranks have a polynomial growth, and they could be packed
into a Hilbert series. Let us recall the definition of Hilbert series. Denote
by ${\bf C}$ a(n essentially) small category. A  _norm_ on ${\bf C}$ is a
function $\nu$ from the objects of ${\bf C}$ modulo isomorphism to
$\mathbb{N}$.

######  Definition 4.13.

Given a finitely generated ${\bf C}$-module (over $R$) $\mathcal{F}$ and a
norm $\nu$ on ${\bf C}$, the _Hilbert series_ (with respect to $\mathcal{F}$
and $\nu$) is defined as

${S}_{\mathcal{F},\nu}(t)=\sum_{x\in{\bf
C}}\text{rank}_{R}(\mathcal{F}(x))t^{\nu(x)}\ .$

If ${\bf C}$ is a category of graphs we will take $\nu$ to be the number of
edges, and omit it from the notation.

We know from [Ram21] that the Hilbert series of matching complexes of
undirected trees is algebraic. By Proposition 4.11, multipath complexes of
directed trees decompose, up to isomorphism of simplicial complexes, as join
products of matching complexes of trees. As a consequence, we get that their
homology over a field can be expressed in terms of the Künneth formula. This
might suggest that, in complete analogy to what happens with matching
complexes, also the Hilbert series of multipath complexes is algebraic.

######  Question 4.14.

Denote by ${\bf T}_{k}$ the subcategory of $\mathbf{CDigraph}$ spanned by
trees with at most $k$ unstable vertices. Is the Hilbert series with respect
to $\mathrm{H}_{i}(X_{-};\mathbb{Z})\colon{\bf T}_{k}\to R\text{-}{\bf Mod}$
algebraic for each choice of $i,k\in\mathbb{N}$?

###  4.2. Multipath complexes and matching complexes

In the previous section we used the observation, from [CCC], that the
multipath complexes of trees are strictly related to matching complexes. The
aim of this section is to extend the relation between multipath complexes and
matching complexes to a wider class of quivers, and, as a consequence, to
generalise Proposition 4.11. We will make use of a blow-up operation. To avoid
further technical assumptions, we work also in this section with digraphs
rather than with quivers.

Recall that the _indegree_ (resp. _outdegree_) of a vertex $v$ is the number
of edges with target (resp. source) $v$.

######  Definition 4.15.

Let ${\tt G}$ be a digraph, and let $v\in V({\tt G})$ with both indegree and
outdegree different from $0$. The _blow-up_ of ${\tt G}$ at $v$ is the digraph
$B({\tt G},v)$ obtained from ${\tt G}$ as follows: the vertices of $B({\tt
G},v)$ are the same as ${\tt G}$ except for $v$, which is replaced by
$v_{\mathrm{in}}$ and $v_{\mathrm{out}}$. Given
$v^{\prime},v^{\prime\prime}\in V(B({\tt G},v))$ the edges from $v^{\prime}$
to $v^{\prime\prime}$ are in bijection with

  1. (a)

the edges between the corresponding vertices in ${\tt G}$, if
$\\{v^{\prime},v^{\prime\prime}\\}\cap\\{v_{\mathrm{in}},v_{\mathrm{out}}\\}=\emptyset$;

  2. (b)

the edges from $v^{\prime}$ to $v$, if $v^{\prime}\neq v_{\mathrm{out}}$ and
$v^{\prime\prime}=v_{\mathrm{in}}$;

  3. (c)

the edges from $v$ to $v^{\prime\prime}$, if $v^{\prime}=v_{\mathrm{out}}$ and
$v^{\prime\prime}\neq v_{\mathrm{in}}$;

  4. (d)

the empty set, in the remaining cases.

If the indegree or the outdegree of $v$ are zero, then we set $B({\tt
G},v)\coloneqq{\tt G}$. The _blow-up_ of ${\tt G}$ is the digraph $B({\tt G})$
obtained from ${\tt G}$ by iteratively blowing-up all vertices in ${\tt G}$
one after the other; see Figure 6 for an illustrative example.

Note that the blow-up of digraphs does not depend on the order we blow-up the
vertices. Furthermore, blowing-up a vertex $v$ yield a pair of vertices
$v_{\mathrm{in}}$ and $v_{\mathrm{out}}$. The blow-up of either
$v_{\mathrm{in}}$ or $v_{\mathrm{out}}$ yields just the identity. Therefore,
the blow-up is a trivial operation on the class of alternating digraphs.

######  Remark 4.16.

Blow-ups of digraphs are alternating digraphs, and, in particular, bipartite.

Note that blow-ups of digraphs might yield disconnected digraphs. In fact, it
is not difficult to check that the connected components of the blow-up $B({\tt
G})$ of a digraph ${\tt G}$ without oriented cycles are in one-to-one
correspondence with the dynamical modules of ${\tt G}$.

######  Example 4.17.

The blow-up of ${\tt I}_{n}$ is the disconnected digraph
$\bigsqcup_{i=1}^{n}{\tt I}_{1}$. While the blow-up of ${\tt A}_{n}$ is ${\tt
A}_{n}$.

Locally, blowing-up a vertex corresponds to blowing-up a dandelion subdigraph
at its central vertex:

######  Example 4.18.

Consider the dandelion ${\tt D}_{n,m}$ on $(n+m+1)$ vertices, and $(m+n)$
edges, defined as follows:

  1. (1)

$V({\tt D}_{n,m})=\\{v_{0},w_{1},....,w_{n},x_{1},...,x_{m}\\}$;

  2. (2)

$E({\tt D}_{n,m})=\\{(w_{i},v_{0}),(v_{0},x_{j})\mid i=1,...,n;j=1,...,m\\}$.

$v_{0}$$w_{1}$$w_{2}$$w_{3}$$x_{1}$$x_{2}$ Figure 5. The graph ${\tt
D}_{3,2}$.

In other words we have a single $(m+n)$-valent vertex $v_{0}$, all remaining
vertices are univalent, there are $n$ edges with target $v_{0}$, and there are
$m$ edges with source $v_{0}$ – cf. Figure 5. Then, the blow-up of ${\tt
D}_{n,m}$ is the blow-up $B({\tt D}_{n,m},v_{0})$ of ${\tt D}_{n,m}$ at the
central vertex $v_{0}$, which is the disjoint union of a source with $m$
edges, and a sink with $n$ edges. Note that maximal multipaths of ${\tt
D}_{n,m}$ are of type $\\{(w_{i},v_{0}),(v_{0},x_{j})\\}$, whereas maximal
multipaths of $B({\tt D}_{n,m},v_{0})$ are of type
$\\{\\{(w_{i},v_{0})\\},\\{(v_{0},x_{j})\\}\\}$.

$0$$1$$2$$3$$0$$1_{\mathrm{out}}$$2_{\mathrm{out}}$$1_{\mathrm{in}}$$2_{\mathrm{in}}$$3$$0$$1_{\mathrm{out}}$$2_{\mathrm{out}}$$1_{\mathrm{in}}$$2_{\mathrm{in}}$$3$
Figure 6. Transitive tournament ${\tt T}_{3}$ (in red on the left), its blow-
up (in blue at the center), and the associated bipartite graph ${\tt B}_{3}$
(in orange on the right).

######  Proposition 4.19.

Let ${\tt G}$ be a digraph. Suppose that $v\in V({\tt G})$ does not belong to
any oriented cycle in ${\tt G}$. Then, the multipath complex $X({\tt G})$ is
canonically isomorphic, as a simplicial complex, to $X(B({\tt G},v))$.

###### Proof.

By definition, there is a natural bijection $b\colon E({\tt G})\to E(B({\tt
G},v))$ given by

$b((v_{1},v_{2}))=\begin{cases}(v_{1},v_{\mathrm{in}})&\text{if }v_{2}=v,\\\
(v_{\mathrm{out}},v_{2})&\text{if }v_{1}=v,\\\
(v_{1},v_{2})&\text{otherwise}\end{cases}$

for each $(v_{1},v_{2})\in E({\tt G})$. Given a multipath ${\tt M}$ in ${\tt
G}$, we define $b({\tt M})$ as the spanning subgraph of $B({\tt G},v)$ spanned
by the edges in $b(E({\tt M}))\subseteq E(B({\tt G},v))$. To prove the
statement is sufficient to show that $b$ gives a well-defined bijection
between multipaths in ${\tt G}$ and multipaths in $B({\tt G},v)$.

The image of a multipath in ${\tt G}$ is a multipath in $B({\tt G},v)$; if at
most one edge in the multipath has $v$ as endpoint, then the statement is
clear. If two edges of the multipath have $v$ as endpoint, then the connected
component of the multipath containing these two edges splits into the disjoint
union of two paths (one containing $v_{\mathrm{in}}$ and the other containing
$v_{\mathrm{out}}$).

We claim that every multipath ${\tt M}^{\prime}$ in $B({\tt G},v)$ is the
image of a multipath in ${\tt G}$. To this end we show that there is at most
one edge in each connected component of ${\tt M}^{\prime}$ that has one
endpoint in $\\{v_{\mathrm{in}},v_{\mathrm{out}}\\}$. Assume, by
contradiction, that there are two edges of the multipath, say $e_{1}$ and
$e_{2}$, incident in $v_{\mathrm{out}}$ and $v_{\mathrm{in}}$, respectively.
If $e_{1}$ and $e_{2}$ belong to the same component $\gamma$ of ${\tt
M}^{\prime}$ we get a contradiction. By construction, there is no edge $e$ in
$B({\tt G},v)$ such that $t(e)=v_{\mathrm{out}}$ or $s(e)=v_{\mathrm{in}}$.
Thus, $e_{1}$ is the first edge in $\gamma$ and $e_{2}$ the last edge in
$\gamma$. Therefore, $b^{-1}(\gamma)$ is an oriented cycle in ${\tt G}$ which
has $v$ as a vertex. This is absurd since $v$ does not belong to any oriented
cycle in ${\tt G}$. It follows that $b^{-1}({\tt M}^{\prime})$ is a well-
defined multipath, and the claim follows.

Since $b$ is a bijection between the edges of the two digraphs, the induced
map on multipaths is injective. This concludes the proof. ∎

We are now ready to state the main technical result of the section. Recall by
Remark 2.4 that the functor $\iota$ associates to a quiver the underlying
undirected graph.

######  Theorem 4.20.

Let ${\tt G}$ be a digraph without oriented cycles. Then, the multipath
complex $X({\tt G})$ is isomorphic, as simplicial complex, to the matching
complex of $\iota(B({\tt G}))$.

###### Proof.

Since no vertex of ${\tt G}$ is contained in any oriented cycle, by
Proposition 4.19, $X({\tt G})$ is canonically isomorphic to $X(B({\tt G}))$.
The digraph $B({\tt G})$, and, in particular, each connected component of
$B({\tt G})$, is alternating – cf. Remark 4.16. Hence, by [CCC, Theorem 4.1],
for each connected component ${\tt H}$ of $B({\tt G})$, we have an isomorphism
of simplicial complexes $M(\iota({\tt H}))\cong X({\tt H})$. Let ${\tt
H}_{1},\dots,{\tt H}_{n}$ be the connected components of $B({\tt G})$. Then,
by Equation (2), we have

$X({\tt G})\equiv X({\tt H}_{1})\ast\dots\ast X({\tt H}_{n})\cong M(\iota({\tt
H}_{1}))\ast\dots\ast M(\iota({\tt H}_{n}))\ ,$

where $M$ denotes the matching complex. As also the matching complex of a
disjoint union is, up to isomorphism, the join product of the matching
complexes, this fact implies the statement. ∎

Let $\mathbf{Digraph}_{o}$ be the category of directed graph without oriented
cycles, and _regular_ morphisms of directed graphs; that means, injective maps
$\phi\colon{\tt G}_{1}\to{\tt G}_{2}$ of digraphs such that $(v,w)\in E({\tt
G}_{1})\implies\phi(v)\neq\phi(w)$. Note, that this is the same as the
opposite category of digraphs without cycles, and deletions.

######  Remark 4.21.

The blow-up construction lifts to a functor

$\mathbf{B}\coloneqq
B\circ\iota\colon\mathbf{Digraph}_{o}\to\mathbf{Graph}^{\mathrm{op}}\ .$

In fact, it is easy to see that the blow-up extends to regular morphims of
digraphs, and preserves compositions and identities. Note that we do not allow
contractions here because contractions may generate new oriented cycles.

######  Corollary 4.22.

The following diagram

${\mathbf{Digraph}_{o}}$${\mathbf{Graph}^{\mathrm{op}}}$${\mathbf{SimpCompl}}$$\scriptstyle{\mathbf{B}}$$\scriptstyle{X}$$\scriptstyle{M}$

is commutative up to isomorphism of simplicial complexes.

###### Proof.

The statement follows in view of Theorem 4.20 and Remark 4.21. ∎

We can use the identification with the matching complex given in Theorem 4.20
to get new computations of the homotopy type of matching complexes. In fact,
let ${\tt B}_{n}$ be the undirected graph on $2n$ vertices $p_{1},\dots,p_{n}$
and $q_{1},\dots,q_{n}$, and edges $(p_{i},q_{j})$ for all $i\leq j$.
Sometimes, these are called half-graphs or ladders [NORS21].

######  Theorem 4.23.

The matching complex of ${\tt B}_{n}$ is either contractible or homotopy
equivalent to a wedge of spheres.

###### Proof.

Let ${\tt T}_{n}$ be the transitive tournament on $n+1$ vertices (with only
edges of type $(i,j)$ for $i<j$). Then, we can identify its blow-up with the
bipartite graph ${\tt B}_{n}$ – see also Figure 6. In light of Theorem 4.20,
the multipath complex of ${\tt T}_{n}$ is isomorphic to the matching complex
of $\iota({\tt B}_{n})$. The statement now follows directly from [CCDTS24,
Theorem 5.1]. ∎

######  Remark 4.24.

In view of Theorem 4.23 and [CCDTS24, Lemma 5.7], we get that the matching
complexes of bipartite graphs obtained from ${\tt B}_{n}$ by deletion of a
subset of vertices in $\\{p_{1},\dots,p_{n}\\}$ are either contractible or
homotopy equivalent to wedges of spheres.

Let ${\tt G}$ be a digraph without oriented cycles. Assume that, for each
embedded cycle (possibly of length $2$), the induced orientation on it is not
alternating. In such case, we say that ${\tt G}$ is a _digraph without
oriented and alternating cycles_. In particular, ${\tt G}$ does not have pairs
of edges of the form $(v,w)$ and $(w,v)$. With this terminology, we directly
get the following:

######  Theorem 4.25.

Let ${\tt G}$ be a digraph without any oriented or alternating cycle. Then,
the multipath complex of ${\tt G}$ is either contractible or a wedge of
spheres.

###### Proof.

By assumption, the induced orientation on each embedded cycle is not
alternating. This means that, for each embedded cycle ${\tt H}$, we can find a
vertex $v_{\tt H}$ with both indegree and outdegree non zero. Blowing-up ${\tt
G}$ at $v_{\tt H}$ breaks the cycle ${\tt H}$. Therefore, the blow-up of ${\tt
G}$ is a directed forest. The statement follows by Theorem 4.20 and [MT08,
Theorem 4.13]. ∎

The class of digraphs without oriented and alternating graphs is not big. For
example, cones of cycles or of trees with at least an unstable vertex contain
oriented or alternating cycles. Therefore, we can not apply Theorem 4.25 to
such digraphs, and cone graphs may contain torsion. However, in complete
analogy with Proposition 4.7, we get that such torsion is also bounded:

######  Proposition 4.26.

For every pair of integers $k,g\geq 0$, there exists $m=m(g,k)\in\mathbb{Z}$
which annihilates the torsion subgroup of $\mathrm{H}_{i}(X(\text{Cone}({\tt
Q}));\mathbb{Z})$, for each quiver ${\tt Q}$ of genus at most $g$.

###### Proof.

Use Proposition 3.12 and then proceed as for [MR23, Theorem 1.2]. ∎

##  5\. Applications to magnitude homology

We start by recalling the definition of magnitude homology, following [HW17,
Asa23].

A directed graph ${\tt G}$ can be seen as a metric space with the path metric
$d$, where $d(v,w)$ is the minimum length across all directed paths between
$v$ and $w$. If $v$ and $w$ are not connected by a directed path, we set
$d(v,w)\coloneqq\infty$. Given a non-negative integer $k$ and a commutative
ring $R$, let $\Lambda_{k}({\tt G};R)\coloneqq R\langle(v_{0},\dots,v_{k})\mid
v_{i}\in V({\tt G})\rangle$ be the $R$-module freely generated by
$(k+1)$-tuples of vertices of ${\tt G}$. We admit the empty tuple, and set
$\Lambda_{k}({\tt G};R)\coloneqq 0$ for $k\leq-2$. For a $k$-tuple
$(v_{0},\dots,v_{k})$ of vertices of ${\tt G}$, with $v_{i}\neq v_{i+1}$ and
$d(v_{i},v_{i+1})<\infty$ for each $i$, the _length_ of $(v_{0},\dots,v_{k})$
in ${\tt G}$ is the number

$\ell(v_{0},\dots,v_{k})\coloneqq\sum_{i=0}^{k-1}d(v_{i},v_{i+1})\ .$

Furthermore, we define a differential on $\Lambda_{k}(G;R)$ by setting

$\delta(v_{0},\dots,v_{k})\coloneqq\sum_{i=1}^{k-1}(-1)^{i}\delta_{i}(v_{0},\dots,v_{k})\
,$

where
$\delta_{i}(v_{0},\dots,v_{k})=(v_{0},\dots,v_{i-1},v_{i+1},\dots,v_{k})$ if
$\ell(v_{0},\dots,v_{k})=l=\ell(v_{0},\dots,v_{i-1},v_{i+1},\dots,v_{k})$, and
it is set to $0$ otherwise.

Consider the submodule $I_{k}({\tt G};R)\coloneqq
R\langle(v_{0},\dots,v_{k})\mid v_{i}=v_{i+1}\text{ for some }i\rangle$ of
$\Lambda_{k}({\tt G};R)$, where $I_{0}({\tt G})$ is set to $0$. The family of
such modules can be equipped with the differential $\delta$, yielding a chain
complex. As we have the inclusions $I_{k}({\tt G};R)\subseteq\Lambda_{k}({\tt
G};R)$ for all $k$, we can form the quotient chain complex with modules
$R_{k}({\tt G};R)\coloneqq\Lambda_{k}({\tt G};R)/I_{k}({\tt G};R)$. The
magnitude chain complex $\operatorname{\mathrm{MC}}_{k,l}({\tt G};R)$ is
defined as the submodule of $R_{k}({\tt G};R)$ given by all those tuples of
length $l$; this is compatible with the chain complex structure – cf. [Asa23,
Lemma 2.14]. Hence, the pair $(\operatorname{\mathrm{MC}}_{*,l}({\tt
G};R),\delta)$ is a chain complex, and its homology called _magnitude
homology_ (of ${\tt G}$) with coefficients in $R$.

######  Remark 5.1.

A contraction $\phi\colon{\tt G}\to{\tt H}$ of directed graphs induces a chain
map

$\phi_{\\#}\colon\operatorname{\mathrm{MC}}_{*,*}({\tt
G};R)\to\operatorname{\mathrm{MC}}_{*,*}({\tt H};R)$

which, to the tuple $(v_{0},\dots,v_{k})$ of ${\tt G}$, associates the tuple
$(\phi(v_{0}),\dots,\phi(v_{k}))$ if
$\ell(\phi(v_{0}),\dots,\phi(v_{k}))=\ell(v_{0},\dots,v_{k})$, and it is set
to be $0$ otherwise. The map $\phi_{\\#}$ is a chain map, as it commutes with
the differential $\delta$, and it induces a map in magnitude homology.

For the following result, we refer the reader to [HW17, Proposition 3.3] or
[Asa23, Lemma 3.6].

######  Proposition 5.2.

Magnitude homology is a functor

$\operatorname{\mathrm{MH}}_{*,*}\colon\mathbf{CDigraph}\to\mathbf{BiGrMod}_{R}$

from the contraction category of digraphs to the category of bigraded
$R$-modules.

The dual version of magnitude homology, called _magnitude cohomology_

${\rm MC}_{l}^{k}({\tt G};R)\coloneqq{\rm Hom}({\rm MC}_{l,k}({\tt G};R);R)\
,$

was introduced in [Hep22]. It also yields a functor
$\operatorname{\mathrm{MH}}_{*}^{*}\colon\mathbf{CDigraph}^{\mathrm{op}}\to\mathbf{BiGrMod}_{R}$.

We have recalled here the definition of magnitude homology of directed graphs.
Almost _verbatim_ we could have defined magnitude homology of undirected
graphs. In fact, the two notions are related:

######  Remark 5.3.

Let ${\tt G}$ be an (undirected) graph. Then, in the notation of Remark 2.4,
we have that the magnitude (co)homology of the digraph $\rho({\tt G})$
coincides with the magnitude (co)homology (of undirected graphs) of ${\tt G}$
– see also [Asa23, Remark 2.16].

More generally, the definitions of magnitude homology and magnitude cohomology
can also be extended to quivers, yielding functors on the whole category
$\mathbf{CQuiver}$ of quivers and contractions. Let $R$ be a commutative
Noetherian ring, with identity. Then, we have the following extension of
[CC23, Theorem 3.11]:

######  Theorem 5.4.

The $\mathbf{CQuiver}^{\mathrm{op}}_{\leq g}$-module ${\rm
MH}^{k}_{l}(-;R)\colon\mathbf{CQuiver}^{\mathrm{op}}_{\leq
g}\to\mathbf{Mod}_{R}$ is finitely generated.

###### Proof.

By Theorem 3.7, the (opposite) category $\mathbf{CQuiver}^{\mathrm{op}}_{\leq
g}$ of quivers of bounded genus, and contractions, is quasi-Gröbner. Hence,
subquotients of finitely generated $\mathbf{CQuiver}^{\mathrm{op}}_{\leq
g}$-modules are finitely generated. By Theorem 3.9, the
$\mathbf{CQuiver}^{\mathrm{op}}_{\leq g}$-module
$\operatorname{\mathrm{Hom}}(\mathcal{V}^{\oplus k},R)$ is finitely generated.
The statement now follows using the same arguments of [CC23, Proposition
3.10], adapted to the case of quivers. ∎

Using Theorem 5.4, we can extend the results of [CC23] to the more general
setting of quivers. In particular, a straightforward adaptation of the
arguments in [CC23] yields:

######  Corollary 5.5.

For every pair of integers $k,g\geq 0$, there exists $m=m(g,k)\in\mathbb{Z}$
which annihilates the torsion subgroup of
$\operatorname{\mathrm{MH}}^{k}_{*}({\tt G};\mathbb{Z})$, for each quiver
${\tt G}$ of genus at most $g$.

######  Corollary 5.6.

Let $\mathbb{K}$ be a field, and $g\geq 0$. Then, there exists a polynomial
$f\in\mathbb{Z}[t]$ of degree at most $g+1$, such that, for all quivers ${\tt
G}$ of genus at most $g$, we have

$\dim_{\mathbb{K}}\operatorname{\mathrm{MH}}_{*}^{k}({\tt G};\mathbb{K})\leq
f(\\#E({\tt G}))\ ,$

where $\\#E({\tt G})$ is the number of edges of ${\tt G}$.

Corollary 5.5 says that says that the order of torsion classes in integral
magnitude (co)homology of quivers of genus at most $g$, in a fixed
(co)homological degree $k$, is bounded. By Remark 5.3 and using the results of
[KY21] and, in particular, [SS21, Theorem 3.13], we know that magnitude
homology and cohomology of quivers can contain torsion. However, we do not
know if such torsion always comes from undirected graphs via the functor
$\rho$, or not.

######  Question 5.7.

Is it possible to extend the constructions of [KY21] and [SS21] so to get
torsion of directed graphs which does not come from the essential image of
$\rho\colon\mathbf{Graph}\to\mathbf{Quiver}$ of Remark 2.4?

In view of the algebraicity results of Section 4, we ask the following:

######  Question 5.8.

Is the Hilbert series of the magnitude homology of (directed) graphs
algebraic?

######  Question 5.9.

The categories $\mathbf{Graph}$ and $\mathbf{Quiver}$ are related by the
functors $\iota$ and $\rho$. What is the relation between generators of
magnitude homology of graphs and magnitude homology of quivers?

Magnitude homology has strong connections with another homological invariant
of digraphs, the so-called _path homology_ – cf. [GLMY20]. More precisely,
path homology is the diagonal component of a certain spectral sequence
involving magnitude homology [Asa23]. Despite torsion in magnitude homology of
digraphs is yet unclear, when we turn to path homology we have more
information; to be more precise, we have the following:

######  Remark 5.10.

Path homology of digraphs can contain arbitrary torsion: if $X$ is a
simplicial complex, and ${\tt G}_{X}$ the Hasse digraph associated to $X$,
then the path homology of ${\tt G}_{X}$ is isomorphic to the (simplicial)
homology of $X$ – see, e.g., [GMY14], or [GMY16] for the cohomological
version.

The following corollary tells us that also in the case of path homology of
digraphs, torsion has to be bounded:

######  Corollary 5.11.

For each $g,k$ positive integers, there exists a $d=d({g,k})\in\mathbb{Z}$
such that, for each digraph ${\tt G}$ of genus $g$, the torsion part of the
path cohomology $\mathrm{PH}^{k}({\tt G},\mathbb{Z})$ has exponent at most
$d$.

###### Proof.

Path (co)homology groups appear as groups in the second page of a spectral
sequence whose $0$-th page features magnitude chain groups. Turning the pages
of the spectral sequence corresponds to taking subsequent subquotients of the
$0$-th page. Therefore, the statement follows thanks to Theorem 5.4. ∎

## References

  * [AF07] S. Ault and Z. Fiedorowicz.  Symmetric homology of algebras, 2007.  ArXiv:0708.1575.
  * [AHK23] Y. Asao, Y. Hiraoka, and S. Kanazawa.  Girth, magnitude homology and phase transition of diagonality.  Proceedings of the Royal Society of Edinburgh Section A: Mathematics, page 1–27, 2023.
  * [Asa21] Y. Asao.  Magnitude homology of geodesic metric spaces with an upper curvature bound.  Algebr. Geom. Topol., 21(2):647–664, 2021.
  * [Asa23] Y. Asao.  Magnitude homology and path homology.  Bull. Lond. Math. Soc., 55(1):375–398, 2023.
  * [Aul10] S. Ault.  Symmetric homology of algebras.  Algebr. Geom. Topol., 10(4):2343–2408, 2010.
  * [Bar15] D. Barter.  Noetherianity and rooted trees, 2015.
  * [BW99] A. Björner and V. Welker.  Complexes of directed graphs.  SIAM J. Discrete Math., 12:413–424, 10 1999.
  * [CC23] L. Caputi and C. Collari.  On finite generation in magnitude (co)homology, and its torsion, 2023\.  ArXiv:2302.06525.
  * [CCC] L. Caputi, D. Celoria, and C. Collari.  Monotone cohomologies and oriented matchings.  Homology, Homotopy & Applications.  In press. ArXiv:2203.03476.
  * [CCDT] L. Caputi, C. Collari, and S. Di Trani.  Multipath cohomology of directed graphs.  Algebraic & Geometric Topology.  In press. ArXiv:2108.02690.
  * [CCDT23] L. Caputi, C. Collari, and S. Di Trani.  Combinatorial and topological aspects of path posets, and multipath cohomology.  J. Algebr. Comb., 57(2):617–658, 2023.
  * [CCDTS24] L Caputi, C Collari, S Di Trani, and J P. Smith.  On the homotopy type of multipath complexes.  Mathematika, 70(1):e12235, 2024.
  * [CEFN14] T. Church, J. S. Ellenberg, B. Farb, and R. Nagpal.  $\mathrm{FI}$-modules over Noetherian rings.  Geometry & Topology, 18(5):2951 – 2984, 2014.
  * [CR23] L. Caputi and H. Riihimäki.  On reachability categories and commuting algebras of quivers, 2023.
  * [Eng09] A. Engström.  Complexes of directed trees and independence complexes.  Discrete Math., 309(10):3299–3309, 2009.
  * [GLMY20] A. A. Grigor’yan, Yong Lin, Y. V. Muranov, and S.-T. Yau.  Path complexes and their homologies.  Journal of Mathematical Sciences, 248:564–599, 2020.
  * [GMVY18] A. A. Grigor’yan, Y. V. Muranov, V. Vershinin, and S.-T. Yau.  Path homology theory of multigraphs and quivers.  Forum Mathematicum, 30(5):1319–1337, 2018.
  * [GMY14] A. Grigor’yan, Yu. V. Muranov, and Shing-Tung Yau.  Graphs associated with simplicial complexes.  Homology, Homotopy and Applications, 16(1):295 – 311, 2014.
  * [GMY16] A. Grigor’yan, Y. Muranov, and S.-T. Yau.  On a cohomology of digraphs and Hochschild cohomology.  Journal of Homotopy and Related Structures, 11:209–230, 2016.
  * [Gom19] K. Gomi.  Magnitude homology of geodesic space, 2019.
  * [Hep22] R. Hepworth.  Magnitude cohomology.  Math. Z., 301(4):3617–3640, 2022.
  * [HR23] R. Hepworth and E. Roff.  The reachability homology of a directed graph, 2023.
  * [HW17] R. Hepworth and S. Willerton.  Categorifying the magnitude of a graph.  Homology Homotopy Appl., 19(2):31–60, 2017.
  * [IP23] S. O Ivanov and F. Pavutnitskiy.  Simplicial approach to path homology of quivers, subsets of groups and submodules of algebras.  Journal of the LMS, 2023.
  * [ĬPVZ20] D. Ĭoich, G. Panina, S. T. Vrechitsa, and R. T. Zhivalevich.  Generalized chessboard complexes and discrete Morse theory.  Chebyshevskiĭ Sb., 21(2):207–227, 2020.
  * [Iva23] S. O. Ivanov.  Nested homotopy models of finite metric spaces and their spectral homology, 2023.
  * [Jon08a] J. Jonsson.  Exact sequences for the homology of the matching complex.  Journal of Combinatorial Theory, Series A, 115(8):1504–1526, 2008\.
  * [Jon08b] J. Jonsson.  Simplicial complexes of graphs, volume 1928 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin, 2008.
  * [Jon10] J. Jonsson.  More torsion in the homology of the matching complex.  Experiment. Math., 19(3):363–383, 2010.
  * [Koz08] D. N. Kozlov.  Combinatorial algebraic topology, volume 21 of Algorithms and computation in mathematics.  Springer, Berlin
  * [KY21] R. Kaneta and M. Yoshinaga.  Magnitude homology of metric spaces and order complexes.  Bull. Lond. Math. Soc., 53(3):893–905, 2021.
  * [Lei21] T. Leinster.  Entropy and diversity. The axiomatic approach.  Cambridge: Cambridge University Press, 2021.
  * [Mat22] T. Matsushita.  Matching complexes of polygonal line tilings.  Hokkaido Mathematical Journal, 51(3):339 – 359, 2022.
  * [MJMV22] M. J. Milutinović, H. Jenne, A. McDonough, and J. Vega.  Matching complexes of trees and applications of the matching tree algorithm.  Ann. Comb., 26(4):1041–1075, 2022.
  * [MMS23] A. Mondal, S. Mukherjee, and K. Saha.  Discrete morse theoretic computations in the matching complex of $k_{7}$, 2023.
  * [MR23] D. Miyata and E. Ramos.  The graph minor theorem in topological combinatorics.  Advances in Mathematics, 430:109203, 2023.
  * [MT08] M. Marietti and D. Testa.  A uniform approach to complexes arising from forests.  Electron. J. Combin., 15(1):Research Paper 101, 18, 2008.
  * [NORS21] J. Nešetřil, P. Ossona de Mendez, R. Rabinovich, and S. Siebertz.  Classes of graphs with low complexity: The case of classes with bounded linear rankwidth.  European Journal of Combinatorics, 91:103223, 2021.  Colorings and structural graph theory in context (a tribute to Xuding Zhu).
  * [PR19] N. Proudfoot and E. Ramos.  Functorial invariants of trees and their cones.  Selecta Mathematica, 25:1–28, 2019.
  * [PR22] N. Proudfoot and E. Ramos.  The contraction category of graphs.  Representation Theory of the American Mathematical Society, 26(23):673–697, 2022.
  * [Ram21] E. Ramos.  Hilbert series in the category of trees with contractions.  Math. Z., 298(3-4):1831–1852, 2021.
  * [Rof23] E. Roff.  Iterated magnitude homology, 2023.
  * [RS04] N. Robertson and P. D. Seymour.  Graph minors. XX: Wagner’s conjecture.  J. Comb. Theory, Ser. B, 92(2):325–357, 2004.
  * [Sin22] A. Singh.  Higher matching complexes of complete graphs and complete bipartite graphs.  Discrete Mathematics, 345(4):112761, 2022.
  * [SS17] S. Sam and A. Snowden.  Gröbner methods for representations of combinatorial categories.  Journal of the American Mathematical Society, 30(1):159–203, 2017\.
  * [SS21] R. Sazdanovic and V. Summers.  Torsion in the magnitude homology of graphs.  J. Homotopy Relat. Struct., 16(2):275–296, 2021.
  * [SW04] J. Shareshian and M. L. Wachs.  Torsion in the matching complex and chessboard complex.  Advances in Mathematics, 212:525–570, 2004.
  * [TW12] P. Turner and E. Wagner.  The homology of digraphs as a generalisation of Hochschild homology.  Journal of Algebra and Its Applications, 11(02):1250031, 2012.
  * [TY23] Y. Tajima and M. Yoshinaga.  Causal order complex and magnitude homotopy type of metric spaces, 2023\.
  * [VŽ09] S. T. Vrećica and R. T. Živaljević.  Cycle-free chessboard complexes and symmetric homology of algebras.  European J. Combin., 30(2):542–554, 2009.
  * [Wac03] M. L. Wachs.  Topology of matching, chessboard, and general bounded degree graph complexes.  volume 49, pages 345–385. 2003.  Dedicated to the memory of Gian-Carlo Rota.