# On finite generation in magnitude (co)homology, and its torsion

Luigi Caputi  and  Carlo Collari

###### Abstract.

The aim of this paper is to apply the framework, which was developed by Sam
and Snowden, to study structural properties of graph homologies, in the spirit
of Ramos, Miyata and Proudfoot. Our main results concern the magnitude
homology of graphs introduced by Hepworth and Willerton. More precisely, for
graphs of bounded genus, we prove that magnitude cohomology, in each
homological degree, has rank which grows at most polynomially in the number of
vertices, and that its torsion is bounded. As a consequence, we obtain
analogous results for path homology of (undirected) graphs. We complement the
work with a proof that the category of planar graphs of bounded genus and
marked edges, with contractions, is quasi-Gröbner.

## Introduction

Magnitude is a numerical invariant of isometry classes of metric spaces, and
it finds its motivations in the study of species similarity [SP94] – see
[Lei21] for a general overview on the topic. From the mathematical point of
view, the definition of magnitude was motivated, and naturally arose, from
considerations on Euler characteristic in enriched category theory [Lei13] –
see also [LW13, Lei21]. Aside from category theory and metric geometry,
magnitude has also many interesting connections with other areas of
mathematics, such as differential geometry [Wil14], minimal surfaces [GG23],
geometric measure theory, and potential theory [LM17].

Graphs, endowed with the shortest path distance, are prominent examples of
metric spaces. In this context, magnitude was studied first in [Lei19].
Leinster showed that magnitude of graphs has a wealth of interesting
properties. Among these, we have that magnitude is a rational function which
can be expressed as an integral power series, that is multiplicative with
respect to the Cartesian product of graphs, and that it satisfies an
inclusion-exclusion formula. Remarkably, magnitude shares similar features
with – and yet is not determined by – the Tutte polynomial, see [Lei19].

Rather than on magnitude itself, here we focus on its categorification:
magnitude (co)homology, as defined by Hepworth and Willerton [HW17, Hep22],
see also [LS21]. As with magnitude, also its categorification has attracted
some attention – see, for instance, the recent papers [Gu18, AHK21, SS21,
Asa22]. In this context, categorification means to associate to a numerical
(or polynomial) invariant a whole homology theory, whose Euler characteristic
recovers the original invariant. The simplest example of categorification is
given by the classical Euler-Poincaré characteristic of simplicial complexes,
which is categorified by simplicial homology. The categorification of the
Jones polynomial introduced by Khovanov [Kho00] has shown the advantage of the
homological and categorical approaches to the study of (polynomial) invariants
of graphs, knots, _etc_. After Khovanov’s discovery, the interest in
categorification of knots and graphs invariants, and their properties,
skyrocketed. Among the well-known graphs invariants which have been
categorified using Khovanov’s framework, we can find the chromatic polynomial
[HGR05], and the Tutte polynomial [JHR06]. Magnitude homology follows similar
ideas. A consequence of the more general framework is that the new viewpoint
brings more refined invariants. This is also the case for magnitude homology:
there exist graphs with same magnitude, but non-isomorphic magnitude homology
groups [Gu18, Appendix A]. Furthermore, the categorical approach allows us to
explain some intrinsic properties of the magnitude of graphs, in homological
terms; for example, the multiplicative property with respect to Cartesian
products descends from a Künneth theorem, and a Mayer-Vietoris theorem
categorifies the inclusion-exclusion formula.

### Statement of results

We now come to the main point of this paper. It was asked in [HW17] whether
there are graphs with torsion in their magnitude homology. This question was
positively answered, first by Kaneta and Yoshinaga [KY21], and then extended
by Sazdanovic and Summers [SS21]. Computations show that any finitely
generated Abelian group appears as a subgroup of the magnitude homology of a
graph [SS21, Theorem 3.14]. However, to get such torsion, Sazdanovic and
Summers increased the combinatorial complexity of the graphs. It is not clear
from their proof whether this behaviour is a structural property of magnitude
homology, or it depends on the methods developed in [KY21, SS21]. Instead of
working with magnitude homology, here we use its cohomological version
[Hep22], and we will confine ourselves within the category of finite,
connected, undirected graphs. As magnitude homology and cohomology are related
by a short exact sequence [Hep22, Remark 2.5], passing to cohomology is not a
restriction.

The main goal of this work is to prove that, to get torsion of higher order in
magnitude cohomology, it is indeed necessary to increase the combinatorial
complexity of the graphs. Therefore, this behaviour is somehow due to a
structural property of magnitude (co)homology. To achieve such result, we
borrow methods from representation stability [CEF15] of (combinatorial)
categories, as recently developed by Sam and Snowden [SS17]. The categorical
viewpoint enables us to gain a deeper understanding of the behaviour of
magnitude (co)homology (and of its torsion), by looking at combinatorial
properties of the category of graphs considered. Our ideas were inspired by
works from Ramos, Miyata and Proudfoot [MR20, Ram22, PR22], who proved similar
statements for matching complexes and unordered configuration spaces of
graphs. Recall that the magnitude cohomology of a graph ${\tt G}$. with
coefficients in a ring $R$, is a bigraded module
$\operatorname{\mathrm{MH}}^{*}_{*}({\tt
G};R)=\bigoplus_{k,l}\operatorname{\mathrm{MH}}^{k}_{l}({\tt G};R)$, where $k$
is the cohomological grading, and $l$ is the length. The main result of the
paper is the following – _cf._ Theorem 3.18;

######  Theorem 1.

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 graph ${\tt
G}$ of genus at most $g$.

Roughly speaking, the order of torsion classes in integral magnitude
(co)homology of connected graphs of genus at most $g$, in a fixed
(co)homological degree $k$, is bounded. In fact, to apply the ideas of Ramos,
Miyata and Proudfoot to our context, we consider the category
$\mathbf{C}\mathbf{Graph}_{g}$ of graphs with genus at most $g$ – _cf_. Remark
2.4. This category is well-behaved in the sense of [SS17], as proved in
[PR22]. We prove that magnitude cohomology is a finitely generated functor on
the category $\mathbf{C}\mathbf{Graph}^{\rm op}_{g}$, and the technology
developed in [SS17] allows us to infer the result. As a byproduct, we also
obtain an estimate of the growth of the ranks of magnitude (co)homology groups
– _cf._ Corollary 3.13;

######  Theorem 2.

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 ${\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}$.

This last result says that the growth of the ranks of magnitude cohomology, in
a fixed cohomological degree $k$, is at most polynomial, provided to restrict
to graphs of bounded genus – _cf._ Corollary 3.15. We remark here that the
results are consistent with previous computations – see also Example 3.16, and
the text thereafter – for example, in computations of magnitude homology of
cycle graphs [Gu18]. An immediate question is whether the polynomial nature of
these estimates is also structural for the category of graphs. However, this
is not the case, as there are examples of cohomology theories of (directed)
graphs which follow different (exponential) growths – see, for example, the
growth rate of multipath cohomology [CCDT21] with coefficients in an algebra,
see [CCDT22, Table 2].

It was recently shown by Asao [Asa22] that magnitude homology is related to
another homology theory of directed graphs, the so-called _path homology_
[GLMY20]. As a corollary of Asao’s work, we can directly infer similar results
to those above for path (co)homology of undirected graphs. For example, we get
the following – see Corollary 3.19.

######  Theorem 3.

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

The main ingredient in the proof of the above theorems is that magnitude
cohomology is a finitely generated $\mathbf{C}\mathbf{Graph}_{g}^{\rm
op}$-module, in the sense of representation theory of categories – _cf._
Corollary 3.12. It would be interesting to see whether, also in the context of
directed graphs, the usual homology theories considered in the literature are
finitely generated – see [CR22, Section 2] for a short overview. The
categorical framework developed in [SS17] is quite abstract. In order to make
the exposition self-contained, and also to give an idea of the well-behaviour
of the category of graphs considered, we complement the work with a discussion
on combinatorial properties of the category of planar marked graphs. This had
yet to appear in the literature, and it may be of use for future work.

### Conventions

All graphs are assumed to be finite, connected and undirected, and are denoted
in typewriter font, e.g. ${\tt G}$. Unless otherwise specified, $R$ will
denote a commutative ring with identity.

### Acknowledgements

The authors wish to thank Daniele Celoria, for the helpful discussions. The
second section of this paper was initially developed as part of a project in
collaboration with him. The authors are also most grateful to Richard Hepworth
and Yasuhiko Asao, for their valuable comments and feedbacks on the first
draft of the paper. LC warmly thanks Anna Pidnebesna and Isa Dallmer-Zerbe for
the many discussions and support. CC is supported by the MIUR-PRIN project
2017JZ2SW5.

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

In this section, we recall some basic categorical notions needed in the
follow-up, as introduced in [CEF15] in the context of FI-modules. We will
recall the notion of Noetherian modules and quasi-Gröbner categories following
the general framework developed in [SS17].

Let $\mathbf{C}$ be a (essentially) small category, and $R\neq 0$ be a ring. A
_representation_ of the category $\mathbf{C}$, or a _${\bf C}$ -module over
$R$_, is a functor $\mathcal{M}\colon\mathbf{C}\to R\text{\bf-Mod}$ with
values in the category of (left) $R$-modules. A map of $\mathbf{C}$-modules is
a natural transformation of functors. Denote by
${\mathbf{Rep}}_{R}(\mathbf{C})$ the resulting category of
$\mathbf{C}$-modules over $R$. The category $\mathbf{Rep}_{R}(\mathbf{C})$ is
an Abelian category, and all the classical notions as submodules, kernels,
cokernels, injections, surjections, can be defined pointwise. For example, a
_submodule_ of a $\mathbf{C}$-module $\mathcal{M}$ is a $\mathbf{C}$-module
$\mathcal{N}\colon\mathbf{C}\to R\text{\bf-Mod}$ such that $\mathcal{N}(c)$ is
a submodule of $\mathcal{M}(c)$, for each object $c$ of $\mathbf{C}$. A
submodule $\mathcal{N}$ is called _proper_ , if $\mathcal{N}(c)$ is a proper
submodule of $\mathcal{M}(c)$ for at least one $c$. For a given
$\mathbf{C}$-module $\mathcal{M}$, by an _element_ of $\mathcal{M}$ we mean an
element of $\mathcal{M}(c)$ for some object $c$ of $\mathbf{C}$. If $S$ is a
subset of the disjoint union $\bigoplus_{c\in\mathbf{C}}\mathcal{M}(c)$, the
_span_ $\mathrm{span}(S)$ of $S$ is the minimal $\mathbf{C}$-submodule of
$\mathcal{M}$ containing each element of $S$. We are primarily interested in
finitely generated modules, which can be defined as follows:

######  Definition 1.1.

A $\mathbf{C}$-module $\mathcal{M}$ is _finitely generated_ if there exists a
finite set of elements
$m_{1},...,m_{k}\in\bigoplus_{c\in\mathbf{C}}\mathcal{M}(c)$, such that
$\mathrm{span}(m_{1},\dots,m_{k})=\mathcal{M}$.

We can also characterize 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. The functor
$\mathcal{P}_{c}$ is defined on an object $c^{\prime}$ of $\mathbf{C}$ by
setting

$\mathcal{P}_{c}(c^{\prime})\coloneqq
R\,\langle\operatorname{\mathrm{Hom}}_{\mathbf{C}}(c,c^{\prime})\rangle\ ,$

_i.e._ the free (left) $R$-module with basis
$\operatorname{\mathrm{Hom}}_{\mathbf{C}}(c,c^{\prime})$; $\mathcal{P}_{c}$ is
then extended to morphisms accordingly, by compositions. For a morphism
$\gamma\colon c\to c^{\prime}$, we denote by $e_{\gamma}$ the corresponding
element in $\mathcal{P}_{c}(c^{\prime})$. Observe that, for any other
$\mathbf{C}$-module $\mathcal{M}$, we have
$\operatorname{\mathrm{Hom}}_{{\mathbf{Rep}}_{R}(\mathbf{C})}(\mathcal{P}_{c},\mathcal{M})\cong\mathcal{M}(c)$;
hence, the principal module $\mathcal{P}_{c}$ is a projective object in
${\mathbf{Rep}}_{R}(\mathbf{C})$ – which justifies the name principal
projective. The following characterisation of finitely generated
$\mathbf{C}$-modules in terms of principal projectives is well-known – _cf._
[CEFN14, Proposition 2.3]:

######  Lemma 1.2.

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 will also refer
to the objects $c_{1},\dots,c_{n}$ of $\mathbf{C}$ in the lemma as
_generators_ of $\mathcal{M}$. We now recall the notion of Noetherianity in
the context of modules over an arbitrary category, which is central for this
work.

######  Definition 1.3.

A $\mathbf{C}$-module $\mathcal{M}$ is _Noetherian_ if all its submodules are
finitely generated. The category ${\mathbf{Rep}}_{R}(\mathbf{C})$ is
Noetherian if all finitely generated $\mathbf{C}$-modules in it 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}}_{R}(\mathbf{C})$ is
Noetherian if and only if every principal projective module $\mathcal{P}_{c}$
is Noetherian.

######  Example 1.4.

One of the main examples of Noetherian categories is the representation
category of $\mathbf{FI}$-modules. Let $\mathbf{FI}$ be the category of finite
sets and injections. Then, by [CEFN14, Theorem A], the category
${\mathbf{Rep}}_{R}(\mathbf{FI})$ is Noetherian, for any ring $R$.

The category $\mathbf{FI}$ is an example of an $EI$-category, _i.e._ a
category in which every endomorphism is an isomorphism. More generally, it was
proven by Lück [Lüc89, Lemma 16.10] that ${\mathbf{Rep}}_{R}(\mathbf{C})$ is
Noetherian, for any finite $EI$-category $\mathbf{C}$ and Noetherian ring $R$.
This result was further extended to infinite $EI$-categories (satisfying some
mild combinatorial conditions) in [GL15, Theorem 3.7].

######  Example 1.5.

Another example is the category $\mathbf{FA}$ of finite sets and all
functions. If $R$ is a left Noetherian ring, then the category
${\mathbf{Rep}}_{R}(\mathbf{FA})$ is Noetherian by [SS17, Corollary 7.3.5].

Following the seminal paper [CEF15], 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}$ (with some
combinatorial assumptions), and a 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.

######  Definition 1.6.

Let $\mathcal{F}\colon\mathbf{C}\to\mathbf{D}$ be a functor. 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). More generally, by [SS17, Remark 3.2.2], the same
conclusion holds if the functor $\mathcal{F}$ admits a left adjoint, or if
$\mathcal{F}$ is a discrete opfibration surjective on objects [Bur22].
Property (F) allows us to transfer finitely generated properties through
functors. In fact, the following holds:

######  Proposition 1.7 ([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 the pullback functor
$\mathcal{F}^{*}\mathcal{M}\colon\mathbf{C}\to R\text{\bf-Mod}$ is finitely
generated.

###### Proof.

Let $\mathcal{F}\colon\mathbf{C}\to\mathbf{D}$ be a functor satisfying
property (F) and, for $d\in\mathbf{D}$, let $\mathcal{P}_{d}$ be the
corresponding principal projective $\mathbf{D}$-module. Let
$c_{1},\dots,c_{n}$ be objects of $\mathbf{C}$ with morphisms
$\delta_{i}\colon d\to\mathcal{F}(c_{i})$ as in Definition 1.6; note that
$\delta_{i}$ belongs to $\operatorname{\mathrm{Hom}}(d,\mathcal{F}(c_{i}))$,
and is a generator of
$\mathcal{P}_{d}(\mathcal{F}(c_{i}))=(\mathcal{F}^{*}\mathcal{P}_{d})(c_{i})$.
Then, take the set $S\coloneqq\\{e_{\delta_{1}},\dots,e_{\delta_{n}}\\}$ of
such generators in the union
$\bigcup_{i}(\mathcal{F}^{*}\mathcal{P}_{d})(c_{i})$. Now, for an object
$c\in\mathbf{C}$, any element $\psi$ in $(\mathcal{F}^{*}\mathcal{P}_{d})(c)$
can be written as a linear combination of elements in
$\operatorname{\mathrm{Hom}}(d,\mathcal{F}(c))$, by the definition of
principal projective module. As the functor $\mathcal{F}$ satisfies property
(F), each basis element $\delta$ of
$\operatorname{\mathrm{Hom}}(d,\mathcal{F}(c))$ factors through a morphism
coming from $\mathbf{C}$. This means that $\psi$ can be written as a linear
combination in $S$, showing that the $\delta_{i}$ generate the module
$\mathcal{F}^{*}\mathcal{P}_{d}$. Applying Lemma 1.2, so that a finitely
generated module has a surjective map from a finite directed sum of
projectives, the proof extends to any finitely generated module
$\mathcal{M}\colon\mathbf{D}\to R\text{\bf-Mod}$, in turn yielding the
statement. ∎

_Vice versa_ , in order to transfer the property of being finitely generated
from $\mathbf{C}$ to $\mathbf{D}$, it is sufficient to have an essentially
surjective functor, _i.e._ a functor which is surjective on objects up to
isomorphism:

######  Proposition 1.8 ([SS17, Proposition 3.2.4]).

Let $\mathcal{F}\colon\mathbf{C}\to\mathbf{D}$ be essentially surjective, and
let $\mathcal{K}\colon\mathbf{D}\to R\text{\bf-Mod}$ be a functor such that
the pullback $\mathcal{F}^{*}\mathcal{K}\colon\mathbf{C}\to R\text{\bf-Mod}$
is finitely generated (respectively Noetherian). Then, $\mathcal{K}$ is also
finitely generated (respectively Noetherian).

We need to introduce some further notation and terminology; see also [SS17,
Section 4.1] for a more extensive overview. Let
$\mathcal{S}\colon\mathbf{C}\to\mathbf{Set}$ be a functor with values in the
category of sets. We associate a poset $|\mathcal{S}|$ to $\mathcal{S}$ as
follows. First, take $\widetilde{\mathcal{S}}$ to be the union
$\bigcup_{c\in\mathbf{C}}\mathcal{S}(c)$. Then, for an element $f$ in
$\mathcal{S}(c)$ and an element $g$ in $\mathcal{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 $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
$|\mathcal{S}|$ is defined as the quotient of the set
$\widetilde{\mathcal{S}}$ with respect to $\sim$, equipped with the partial
order induced from $\leq$.

######  Definition 1.9.

An ordering on $\mathcal{S}\colon\mathbf{C}\to\mathbf{Set}$ is a choice of a
well-order on $\mathcal{S}(c)$ for each $c$ in $\mathbf{C}$, such that for
every morphism $c\to c^{\prime}$ the induced map
$\mathcal{S}(c)\to\mathcal{S}(c^{\prime})$ is strictly order-preserving; in
such a case, we say that $\mathcal{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 1.10.

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

The category $\mathbf{FI}$ from Example 1.4 is not a Gröbner category, as its
automorphism groups are symmetric groups, hence non-trivial. However,
$\mathbf{FI}$ is quasi-Gröbner:

######  Remark 1.11.

Let $\mathbf{OI}$ be the category of linearly ordered finite sets and ordered
inclusions. This is a “rigidified” version of the category $\mathbf{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\mathbf{FI}$ is an essentially surjective functor satisfying
property (F). As a consequence, $\mathbf{FI}$ is quasi-Gröbner.

The next result follows readily from the definitions:

######  Proposition 1.12.

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 1.13 ([SS17, Theorem 1.1.3]).

If $\mathbf{C}$ is a quasi-Gröbner category, then the category
${\mathbf{Rep}}_{R}(\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.
We refer to [SS17] for complete proofs of these last results.

##  2\. Graphs categories

We collect here basic notions and facts about the category of (plane, rigid,
marked) graphs. The aim of this section is to discuss the combinatorial
properties of these categories of graphs, from the viewpoint of [SS17, PR22].

###  2.1. The (plane) graph category

In the following, a graph ${\tt G}$ is a finite, connected and non-empty
$1$-dimensional CW-complex; it has sets of vertices $V({\tt G})$ and edges
$E({\tt G})$, which are unordered pairs of vertices, possibly with
multiplicities. We recall here the intuitive notions of contractions,
deletions and minor morphisms; for a more detailed account of these
operations, we refer to [MR20, Ram22].

Let ${\tt G}$ be a graph and $e\in E({\tt G})$ be an edge. The _contraction_
of ${\tt G}$ with respect to the edge $e$, is the graph ${\tt G}/e$ obtained
from ${\tt G}$ by contracting $e$ to a point. The _deletion_ of $e$ is the
graph ${\tt G}\setminus e$ obtained from ${\tt G}$ by removing $e$ from the
set of edges of ${\tt G}$. Note that the operation of contracting edges does
not change the homotopy type of ${\tt G}$, 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 of graphs for which ${\tt G}\setminus
e$ is connected. A _minor_ of a graph ${\tt G}^{\prime}$ is a graph ${\tt G}$
that is isomorphic to a graph obtained from ${\tt G}^{\prime}$ by iterative
contractions and deletions. More formally, we have the following definition of
minor morphism of graphs.

######  Definition 2.1 ([Ram22, Definition 2.1]).

A _minor morphism_ $\phi\colon{\tt G}^{\prime}\to{\tt G}$ 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 $\\{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 $\phi(v)$ and
$\phi(w)$;

  * •

$\phi$ maps bijectively $\phi^{-1}(E({\tt G}))$ onto $E({\tt G}^{\prime})$;

  * •

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

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 _planar_ graph is a graph admitting an
embedding in $\mathbb{R}^{2}$. A plane graph is a planar isotopy class of
planar graphs embedded in the plane. It is a well-known result that a plane
graph is uniquely determined by fixing a rotation system on the abstract
planar graph, that is, a consistent circular ordering of the edges around each
vertex.

In the follow-up, we will mainly consider (subcategories of) the category
$\mathbf{Graph}$ of finite, non-empty, connected, graphs, with minor morphisms
of graphs. For example, we can consider its full subcategory $\mathbf{PG}$ of
plane graphs – concretely, a _minor morphism of plane graphs_ is a minor
morphism of the underlying planar graphs which commutes (up to planar isotopy)
with their embeddings. We will also consider the subcategory
$\mathbf{C}\mathbf{Graph}$ of $\mathbf{Graph}$ consisting of finite, non-
empty, connected, graphs, where the morphisms are given by contractions.

A _plane rooted tree_ is a rooted tree $({\tt T},v)$ along with a linear order
on the set of direct descendants of each vertex. We denote by $\mathbf{T}$ the
category whose objects are finite, non-empty, rooted plane trees, and whose
morphisms are _contractions_ of rooted plane trees; which means, contractions
of rooted trees (preserving the root) with the additional property that if a
vertex $w$ comes before $w^{\prime}$ in the depth-first order, then the first
vertex in the preimage of $w$ comes before the first vertex in the preimage of
$w^{\prime}$. Note that in [PR22], this category is denoted by $\mathcal{PT}$.

######  Remark 2.2.

The opposite category $\mathbf{T}^{\rm op}$ has the same objects as
$\mathbf{T}$, but opposite morphisms; it is equivalent to the category whose
objects are planar rooted trees and whose morphisms are pointed order
embeddings that preserve the depth-first linear order considered in [Bar15] –
see [PR22, Remark 2.1].

We have the following theorem:

######  Theorem 2.3.

The category $\mathbf{T}^{\rm op}$ is a Gröbner category.

###### Proof.

The statement follows from Remark 2.2, applying the main result in [Bar15] and
[PR22, Theorem 3.4]. ∎

For a graph ${\tt G}$, we call (combinatorial) _genus_ – also called _circuit
rank_ , but for consistency we follow here the terminology adopted in [PR22] –
of ${\tt G}$ the rank of the first homology group of the geometric realisation
of ${\tt G}$. Equivalently, $\mathrm{genus}({\tt G})\coloneqq|E({\tt
G})|-|V({\tt G})|+1$. Note that contractions do not change the genus of the
graphs.

######  Remark 2.4.

As contractions do not change the genus of a graph, we can consider the full
subcategories $\mathbf{C}\mathbf{Graph}_{g}$ of $\mathbf{C}\mathbf{Graph}$
given by graphs of genus $g$. In particular, $\mathbf{C}\mathbf{Graph}$ can be
seen as the disjoint union of the categories $\mathbf{C}\mathbf{Graph}_{g}$,
for $g\in\mathbb{N}$. We will also denote by $\mathbf{C}\mathbf{Graph}_{\leq
g}$ the category spanned by graphs of genus $\leq g$. Observe that the
category $\mathbf{C}\mathbf{Graph}_{g}$ was denoted by $\mathcal{G}_{g}$ in
[PR22].

We call a _rose_ of genus $g$ the graph ${\tt R}(g)$ consisting of a single
vertex $v$ and $g$ loops, that is, a bouquet of $g$ circles. An _embedded
rose_ of genus $g$ is a plane graph isomorphic to a rose of genus $g$. As an
intermediate step to infer Gröbner type results for such categories of graphs,
we recall the definition of the category of rigidified (plane) graphs.

######  Definition 2.5.

A _rigidified (plane) graph_ of genus $g$ is a $4$-uple $({\tt G},{\tt
T},v,\tau)$ consisting of:

  1. (1)

a (isotopy class of a non-empty, finite, connected) (plane) graph ${\tt G}$ of
combinatorial genus $g$;

  2. (2)

a plane rooted spanning tree $({\tt T},v)$ in ${\tt G}$;

  3. (3)

a contraction $\tau\colon{\tt G}\to{\tt H}$ of (plane) graphs, involving all
edges of ${\tt T}$, with ${\tt H}$ an (embedded) rose;

  4. (4)

an ordering and orientation of all the edges in $E({\tt G})\setminus E({\tt
T})$, called _external edges_.

When not considering the planarity conditions in the above definition, we have
precisely recalled the definition of a rigidified graph as introduced in
[PR22, Section 2.3]. Morphisms of rigidified (plane) graphs are contractions
of (plane) graphs that restrict to contractions of the embedded spanning
rooted trees, and are compatible with the ordering and orientation of all
external edges. We denote by $\mathbf{R}_{g}$ the resulting category of
rigidified graphs of genus $g$, with contractions as morphisms; note that, in
[PR22], $\mathbf{R}_{g}$ was denoted by $\mathcal{PG}_{g}$. Observe that, in
this category, there are no nontrivial automorphisms – the conditions in
Definition 2.5, and in particular the ordering and orientation of the edges,
are required precisely to avoid non-trivial automorphisms in this category. A
further advantage of working with rigidified graphs is that they admit a
natural ordering of their edges.

######  Remark 2.6.

For a rigidified (plane) graph $({\tt G},{\tt T},v,\tau)$ we canonically
define an order of the edges of ${\tt G}$ as follows: first, we consider the
edges of the spanning tree in their order as (plane) rooted tree, and then we
consider the external edges in their order as external edges. Note that
contractions of rigidified graphs preserve this order of the edges.

The same arguments used in the proofs of [PR22, Section 3], together with
[PR22, Theorem 3.10] once properly restated in the setting of rigidified plane
graphs of genus $g$, provide the following result:

######  Theorem 2.7.

For any $g\geq 0$, the category $\mathbf{R}^{\rm op}_{g}$, and its subcategory
given by rigidified plane graphs of genus $g$, and contractions, are Gröbner.

For the sake of completeness, we sketch the arguments here. In the proof we
will abuse the notation and denote each rigidified graph $({\tt G},{\tt
T},v,\tau)$ by the underlying graph ${\tt G}$.

###### Proof of Theorem 2.7.

We first show that, if ${\tt G}=({\tt G},{\tt T},v,\tau)$ is a rigidified
(plane) graph, then the functor $(\mathbf{R}^{\rm op}_{g})_{{\tt
G}}=\operatorname{\mathrm{Hom}}_{\mathbf{R}^{\rm op}_{g}}({\tt G},-)$ is
orderable (see Definition 1.9). First, observe that, as the category
$\mathbf{T}^{\rm op}$ is Gröbner, for each (plane) rooted tree ${\tt T}$,
$\operatorname{\mathrm{Hom}}_{\mathbf{T}^{\rm op}}({\tt T},-)$ is orderable.
Consider the forgetful functor $\mathbf{R}_{g}\to\mathbf{T}$ associating to a
rigidified (plane) graph its underlying rooted spanning tree. Clearly, if
$\phi_{1},\phi_{2}\colon({\tt G},{\tt T},v,\tau)\to({\tt G}^{\prime},{\tt
T}^{\prime},v^{\prime},\tau^{\prime})$ are different morphisms in the category
$\mathbf{R}_{g}^{\rm op}$, then the restrictions $({\tt T},v)\to({\tt
T}^{\prime},v^{\prime})$ must also be different in $\mathbf{T}^{\rm op}$.
Choose a linear ordering $\leq$ on $(\mathbf{R}^{\rm op}_{g})_{{\tt G}}$ such
that the map $(\mathbf{R}^{\rm op}_{g})_{{\tt G}}\to\mathbf{T}^{\rm op}_{\tt
T}$, induced by the forgetful functor, preserves the order – this can be done
by taking a linear refinement of the induced partial order. If
$\phi_{1},\,\phi_{2}\colon{\tt G}\to{\tt G}^{\prime}$ in $(\mathbf{R}^{\rm
op}_{g})_{{\tt G}}$ are such that $\phi_{1}\leq\phi_{2}$, and if
$\psi\colon{\tt G}^{\prime}\to{\tt G}^{\prime\prime}$ is a morphism in
$\mathbf{R}^{\rm op}_{g}$, then we want to prove that
$\psi\circ\phi_{1}\leq\psi\circ\phi_{2}$. The restrictions to the rooted
spanning trees satisfy the inequality
$\psi\circ\phi_{1}\leq_{\mathbf{T}}\psi\circ\phi_{2}$, where
$\leq_{\mathbf{T}}$ is the linear ordering in $\mathbf{T}^{\rm op}_{\tt T}$.
In fact, by assumption, the forgetful functor respects the order, and
$\leq_{\mathbf{T}}$ is preserved with respect to these compositions.
Therefore, we get the inequality $\psi\circ\phi_{1}\leq\psi\circ\phi_{2}$, as
required.

It is left to prove that the poset $|(\mathbf{R}^{\rm op}_{g})_{{\tt G}}|$ is
Noetherian. To do so, we apply the analogue of [PR22, Lemma 3.8] in our
context: to a (plane) rigidified graph $({\tt G},{\tt T},v,\tau)$, there is an
associated $S$-labelled (plane) rooted spanning tree (see [PR22, Section 2.2])
defined on $({\tt T},v)$ and constructed exactly as in [PR22, Lemma 3.8].
Then, sequences of contractions in the poset $|(\mathbf{R}^{\rm op}_{g})_{{\tt
G}}|$ correspond to sequences of contractions of $S$-labelled trees, and since
the category $\mathbf{T}^{\rm op}$ is Gröbner, the result in [PR22, Corollary
3.7] implies that $|(\mathbf{R}^{\rm op}_{g})_{{\tt G}}|$ is Noetherian. ∎

An extremely useful corollary of Theorem 2.7, for us, is the following:

######  Proposition 2.8 ([PR22, Theroem 1.1]).

For any $g\geq 0$, the category ${\bf CGraph}^{{\rm op}}_{g}$ is quasi-
Gröbner.

Although the proof of Theorem 2.7 follows verbatim the proof of [PR22, Theroem
3.10], we do not see how to infer the following corollary directly from it:

######  Proposition 2.9.

The category $\mathbf{P}^{\rm op}_{g}$ of plane graphs of genus $g$, and
contractions, is quasi-Gröbner.

###### Proof.

Consider the forgetful functor that associates to a rigidified plane graph its
underlying plane graph. This functor is clearly essentially surjective. It
also satisfies property (F). Indeed, for a plane graph ${\tt G}$, consider all
possible plane rigidified graphs $({\tt G}_{i},{\tt
T}_{i},v_{i},\tau_{i})_{i=1,\dots,n}$ such that $|E({\tt G}_{i})|\leq|E({\tt
G})|+g$; note that there is only a finite number of such rigidified graphs.
Note also that the images of these graphs via the functor $\mathcal{F}$ have
at most finitely many morphisms from ${\tt G}$. For a rigidified plane graph
$({\tt G}^{\prime},{\tt T}^{\prime},v^{\prime},\tau^{\prime})$ and a morphism
$\phi\colon{\tt G}\to{\tt G}^{\prime}$ in $\mathbf{P}^{\rm op}_{g}$, let $E$
be the collection of edges of ${\tt G}^{\prime}$ that are contracted by the
map $\phi^{\rm op}\colon{\tt G}^{\prime}\to{\tt G}$. We can then consider the
morphism $\mathcal{F}(\psi)$, where $\psi^{\rm op}$ is a contraction of the
graph $({\tt G}^{\prime},{\tt T}^{\prime},v^{\prime},\tau^{\prime})$ on the
edges of ${\tt T}^{\prime}$ corresponding to $E$. By construction, the
morphism $\phi$ then factors through $\mathcal{F}(\psi)$, proving that
$\mathcal{F}$ satisfies property (F). The statement follows by applying
Theorem 2.7 and Proposition 1.12. ∎

Let $(\mathbf{PG}_{\leq g})^{\rm op}$ denote the category of connected plane
graphs ${\tt G}$ such that $\mathrm{genus}({\tt G})\leq g$, with minor
morphisms of plane graphs as morphisms.

######  Corollary 2.10.

For any $g\geq 0$, the categories ${\bf CGraph}^{{\rm op}}_{\leq g}$ and
$(\mathbf{PG}_{\leq g})^{\rm op}$ are quasi-Gröbner.

###### Proof.

It is immediate to see that if a finite number of (small) categories, say
$\mathbf{C}_{1},...,\mathbf{C}_{k}$, are Gröbner, then ${\bf CGraph}^{{\rm
op}}_{\leq g}$ is their disjoint union $\bigsqcup_{i=0}^{k}\mathbf{C}_{k}$ is
Gröbner as well. Then, by Remark 2.4, along with the observation that the
functor $\bigsqcup_{i=0}^{g}\mathbf{R}^{\rm op}_{i}\to{\bf CGraph}^{{\rm
op}}_{\leq g}$ is essentially surjective, and satisfies property (F), imply
that ${\bf CGraph}^{{\rm op}}_{\leq g}$ is quasi-Gröbner.

To prove that $(\mathbf{PG}_{\leq g})^{\rm op}$ is quasi-Gröbner, observe that
minor morphisms involving deletions strictly decrease the genus, hence chains
of deletions are bounded in length. Then, exactly as in the proof of
Proposition 2.9, the forgetful functor is essentially surjective, and
satisfies property (F). Therefore, $(\mathbf{PG}_{\leq g})^{\rm op}$ is also a
quasi-Gröbner category. ∎

As a consequence, for a left-Noetherian ring $R$, submodules of finitely
generated ${\bf CGraph}^{{\rm op}}_{\leq g}$\- and $(\mathbf{PG}_{\leq
g})^{\rm op}$-modules are finitely generated; the following examples of
finitely generated modules are the “plane” analogue of the edge and spanning
module described in [Ram22].

######  Example 2.11.

Consider the _edge module_

$\mathcal{E}_{g}\colon(\mathbf{PG}_{\leq g})^{\rm op}\to
R\text{-}\mathbf{Mod}$

which associates to a plane graph ${\tt G}$ the free $R$-module
$\mathcal{E}_{g}({\tt G})$ generated by the set $E({\tt G})$ of edges of ${\tt
G}$. For any minor morphism, there is a well-defined inclusion of free
$R$-modules. The $(\mathbf{PG}_{\leq g})^{\rm op}$-module $\mathcal{E}_{g}$ is
finitely generated by the line segment, and the loop.

######  Example 2.12.

Consider the _spanning tree module_

$\mathcal{T}_{g}\colon(\mathbf{PG}_{\leq g})^{\rm op}\to
R\text{-}\mathbf{Mod}$

which associates to a plane graph ${\tt G}$ the $R$-module freely generated by
all possible spanning trees of ${\tt G}$. To be more precise,
$\mathcal{T}({\tt G})\coloneqq\bigoplus_{{\tt T}\subseteq{\tt G}}R\langle
x_{\tt T}\rangle$, where the sum ranges over all the spanning trees of ${\tt
G}$. Deletions and contractions induce inclusion maps of $R$-modules. The
$(\mathbf{PG}_{\leq g})^{\rm op}$-module $\mathcal{T}$ is generated by a
single point, as a contraction to a vertex is equivalent to a choice of
spanning tree.

It is not known to the authors if the categories $\mathbf{C}{\bf Graph}^{{\rm
op}}$ and ${\bf CGraph}_{\leq g}$ are quasi-Gröbner, or Noetherian. In the
next section, we will use Theorem 2.7 and the results presented here, to
provide a generalization to the context of (plane) graphs with marked edges.

###  2.2. The category of rigidified marked (plane) graphs

We study the category $\mathbf{RG}_{g}$ (resp. $\mathbf{RPG}_{g}$) of
rigidified marked (resp. plane) graphs of combinatorial genus at most $g$,
equipped with contractions not involving the marked edges as morphisms. The
markings will be precisely needed to indicate which edges cannot be
contracted. The aim of this subsection is then to show that also this category
is Gröbner. We start with the notion of reference graphs, the analogue in this
context of the roses ${\tt R}_{g}$ of the previous subsection. First, we say
that an edge of a graph ${\tt G}$ is _marked_ if it is labelled with a symbol
$*$.

######  Definition 2.13.

A _reference (plane) graph_ is a finite connected (plane) graph ${\tt R}$ such
that all the edges of ${\tt R}$ are marked, with the possible exception of
some self-loops.

A (plane) reference graph generalises the notion of (plane) roses to the
marked case. For example, when we allow at most one marked edge, then all
possible reference graphs are the marked roses, together with the eyeglasses
graphs shown in Figure 1. Observe that, the number of reference graphs with at
most $m$ marked edges and combinatorial genus at most $g$ is finite.

######  Definition 2.14.

A _marked graph_ is a non-empty, finite, connected graph ${\tt G}$ with,
possibly, marked edges.

Formally, a marked graph is a graph together with a function on the edges
assigning a marking to some of them. By abuse of notation, we will write ${\tt
G}$ both for an unmarked and a marked graph. In fact, a graph can be seen as a
marked graph with no marked edges. Minor morphisms of marked graphs are
required to preserve marked edges. This yields a suitable category of marked
graphs. Observe that the category of graphs and minor morphisms is
automatically a subcategory of the category of marked graphs. In the
following, we will also consider marked rooted trees, marked plane graphs,
and, in particular, rigidified marked plane graphs. The rigidified version of
marked graphs that we will use is the following:

$v$$\vdots$$*$$v$$\vdots$$v_{1}$$v_{2}$$\dots$$\dots$$*$ Figure 1. Examples of
reference graphs with at most one marked edge: unmarked and marked roses, and
a pair of marked eyeglasses.

######  Definition 2.15.

A _rigidified marked (plane) graph_ of genus $g$ is a $4$-uple $({\tt G},{\tt
T},v,\tau)$ consisting of:

  1. (1)

a (isotopy class of a non-empty, finite, connected) marked (plane) graph ${\tt
G}$ of combinatorial genus $g$;

  2. (2)

a marked (plane) rooted spanning tree $({\tt T},v)$ in ${\tt G}$;

  3. (3)

a contraction $\tau\colon{\tt G}\to{\tt H}$ of (plane) graphs involving all
edges of ${\tt T}$ except the marked ones, with ${\tt H}$ a reference graph of
genus $g$;

  4. (4)

an ordering and orientation of all the external edges in $E({\tt G})\setminus
E({\tt T})$.

Recall that the (plane) rooted spanning trees in the definition are equipped
with a linear order on the set of direct descendants of each vertex. If the
marked (plane) graph ${\tt G}$ does not contain marked edges, then Definition
2.5 and Definition 2.15 coincide. Given two marked (plane) graphs, a morphism
is a minor morphism of the underlying (plane) graphs involving contractions on
the unlabelled edges, and possibly deletion of the marked edges which do not
disconnect. If no deletion is performed, then the marked edge is required to
be mapped to the corresponding marked edge. We spell this out in the case of
rigidified marked plane graphs:

######  Definition 2.16.

A morphism $\phi\colon({\tt G}_{1},{\tt T}_{1},v_{1},\tau_{1})\to({\tt
G}_{2},{\tt T}_{2},v_{2},\tau_{2})$ of rigidified marked plane graphs of genus
$g$ is a contraction of the underlying plane graphs that restricts to a
contraction $({\tt T}_{1},v_{1})\to({\tt T}_{2},v_{2})$ of the marked rooted
trees and that is the identity on the set of marked edges. Moreover, $\phi$ is
required to be compatible with the order and orientations of the external
edges.

Since morphisms of rigidified marked (plane) graphs are close under
compositions, we can define the category $\mathbf{RG}$ of rigidified marked
graphs, and morphisms of rigidified marked graphs; we denote by
$\mathbf{RG}_{g}$ the full subcategory of graphs whose combinatorial genus is
bounded by $g$. Similarly, for the plane versions.

######  Remark 2.17.

By Remark 2.6, rigidified marked graphs have a canonical ordering of the edges
compatible with morphisms; the order of the edges being given by the order of
the edges obtained by forgetting the markings.

There is a functor $\mathbf{R}_{\leq
g}=\bigsqcup_{i=0}^{g}\mathbf{R}_{i}\to\mathbf{RG}_{g}$ sending a rigidified
graph $({\tt G},{\tt T},v,\tau)$ to itself. The following observation
establishes a relation between the Hom-sets in these two categories; we will
use this relation to deduce that the category $\mathbf{RG}_{g}$ is Gröbner.

######  Remark 2.18.

Let ${\tt G}\coloneqq({\tt G},{\tt T},v,\tau)$ be a rigidified marked graph of
genus $g$. Denote by $\bar{\tt G}\coloneqq(\bar{\tt G},\bar{\tt
T},v,\bar{\tau})$ the rigidified graph obtained from ${\tt G}$ by forgetting
the marking on the edges of ${\tt G}$ (and, consequently, on ${\tt T}$), and
by setting $\bar{\tau}$ to be the composition of $\tau$ and the map which
contracts the marked edge (if possible). Then, we have a (natural)
identification

$\operatorname{\mathrm{Hom}}_{(\mathbf{RG}_{g})^{{\rm op}}}({\tt
G},-)\cong\operatorname{\mathrm{Hom}}_{(\mathbf{R}_{\leq g})^{{\rm
op}}}(\bar{\tt G},-)$

between the sets of morphisms in the two categories. This follows from the
fact that the morphisms come from (opposite morphisms of) contractions. Using
this identification, we can pull-back the order structure from
$\operatorname{\mathrm{Hom}}_{(\mathbf{R}_{\leq g})^{{\rm op}}}(\bar{\tt
G},-)$.

This remark allows to immediately deduce properties of the category
$\mathbf{RG}_{g}$ from properties of $\mathbf{R}_{\leq g}$; in fact, we have
the following:

######  Lemma 2.19.

The opposite category $(\mathbf{RG}_{g})^{\rm op}$ of rigidified marked
graphs, and contractions, is Gröbner.

###### Proof.

By Remark 2.18, for a rigidified marked graph ${\tt G}$, the order properties
of $\operatorname{\mathrm{Hom}}_{(\mathbf{RG}_{g})^{{\rm op}}}({\tt G},-)$ can
be pulled-back from the category $(\mathbf{R}_{\leq g})^{{\rm op}}$. In fact,
since, by Theorem 2.7, $(\mathbf{R}_{\leq g})^{{\rm op}}$ is a Gröbner
category, the posets

$|\operatorname{\mathrm{Hom}}_{(\mathbf{R}_{\leq g})^{{\rm op}}}(\bar{\tt
G},-)|$

are Noetherian and the functors
$\operatorname{\mathrm{Hom}}_{(\mathbf{R}_{\leq g})^{{\rm op}}}(\bar{\tt
G},-)$ orderable. As a consequence, the posets
$|\operatorname{\mathrm{Hom}}_{(\mathbf{RG}_{g})^{{\rm op}}}({\tt G},-)|$ are
directly seen to be Noetherian. By Remark 2.18, we order
$\operatorname{\mathrm{Hom}}_{(\mathbf{RG}_{g})^{{\rm op}}}({\tt G},-)$ by
pulling back the order of $\operatorname{\mathrm{Hom}}_{(\mathbf{R}_{\leq
g})^{{\rm op}}}(\bar{\tt G},-)$; as morphisms of rigidified marked graphs
respect the markings, the induced order is preserved by compositions; hence,
the statement follows. ∎

Note that similar statements are obtained by considering the “plane” versions.
In Lemma 2.19, we have shown that the category $(\mathbf{RG}_{g})^{\rm op}$ is
Gröbner. Despite the similarities between $(\mathbf{RG}_{g})^{\rm op}$ and
$(\mathbf{R}_{\leq g})^{\rm op}$, we cannot directly deduce that a finitely
generated $(\mathbf{R}_{\leq g})^{{\rm op}}$-module is also finitely generated
as an $(\mathbf{RG}_{g})^{\rm op}$-module, since we cannot contract nor delete
marked edges. A simple example is given by the edge module – see Example 2.11
– which is not a finitely generated $(\mathbf{RG}_{g})^{\rm op}$-module. For
this reason, we need to restrict the number of markings. Let
$\mathbf{RG}_{g,n}$ be the full subcategory of $\mathbf{RG}_{g}$ consisting of
rigidified marked graphs with at most $n$ marked edges.

######  Theorem 2.20.

The category $\mathbf{RG}_{g,n}^{\rm op}$ of rigidified marked graphs with
bounded combinatorial genus $\leq g$ and number of marked edges $\leq n$, is
Gröbner.

###### Proof.

By Lemma 2.19, the category $\mathbf{RG}_{g}^{\rm op}$ is Gröbner. Then,
$\mathbf{RG}_{g,n}^{\rm op}$ is Gröbner by [SS17, Proposition 4.4.2]. ∎

Alternatively, the statement follows from the analogue of Remark 2.18 and
Lemma 2.19, applied directly to the category $\mathbf{RG}_{g,n}^{\rm op}$.
Denote by $\mathbf{MG}_{g,n}$ the category of marked finite, connected, and
non-empty (plane) graphs with combinatorial genus bounded by $g$ and number of
marked edges $\leq n$, with marked morphisms (_i.e._ morphisms induced by
contractions of the non-marked edges and deletions of the marked ones). Then,
there is a functor $\mathbf{RG}_{g,n}\to\mathbf{MG}_{g,n}$ obtained by sending
a rigidified marked (plane) graph $({\tt G},{\tt T},v,\tau)$ to the marked
(plane) graph ${\tt G}$.

######  Lemma 2.21.

The functor $\mathcal{F}\colon(\mathbf{RG}_{g,n})^{\rm
op}\to(\mathbf{MG}_{g,n})^{\rm op}$ satisfies property (F).

###### Proof.

Let ${\tt G}$ be a marked graph in $\mathbf{MG}_{g,n}$ and define ${\tt
H}_{1},\dots,{\tt H}_{n}$ to be rigidified marked graphs in the category
$(\mathbf{RG}_{g,n})^{\rm op}$, obtained from ${\tt G}$ as follows:

  * •

if ${\tt G}$ contains a marked edge, then ${\tt H}_{1},\dots,{\tt H}_{m}$ are
all possible rigidified marked graphs with underlying graph ${\tt G}$; there
is a finite number of such graphs, as there are finitely many rigidifications
of ${\tt G}$;

  * •

if ${\tt G}$ does not contain marked edges, let ${\tt H}_{1},\dots,{\tt
H}_{m}$ be the family of all possible rigidified marked graphs obtained from
${\tt G}$, along with all possible rigidified marked graphs on ${\tt
G}\cup\\{e_{1},\dots,e_{k}\\}$ where $\\{e_{i}\\}$ is a marked edge added to
(and incident to vertices of) ${\tt G}$ and $k\leq n$; again, there is a
finite number of such graphs.

Note that there are obvious morphisms ${\tt G}\to\mathcal{F}({\tt H}_{i})$ in
both cases. In the former, these are just the identity map. In the second
case, the morphisms are induced by the deletion of some marked edge. Let now
${\tt H}$ be a graph of $(\mathbf{RG}_{g,n})^{\rm op}$ as required by property
(F) in Definition 1.6, so that $\mathcal{F}({\tt H})$ comes equipped with a
map from ${\tt G}$. Recall that the morphisms in $(\mathbf{MG}_{g,n})^{\rm
op}$ are induced from either contractions of unlabelled edges or deletions of
marked edges; hence, if there is a map ${\tt G}\to\mathcal{F}({\tt H})$, this
implies that ${\tt G}$ is a minor of $\mathcal{F}({\tt H})$, obtained from
$\mathcal{F}({\tt H})$ by iterative contractions and deletions of the marked
edges. In particular, if ${\tt G}$ contains a marked edge, then the morphism
to ${\tt H}$ can only be induced from contractions, therefore it must come
from a contraction of rigidified graphs. On the other hand, if ${\tt G}$ does
not contain a marked edge, the map to $\mathcal{F}({\tt H})$ is either only
given by contractions (as in the previous case), or by contractions followed
by a deletion of the marked edge. In this last case, there exists a ${\tt
H}_{i}$ with a contraction map in $(\mathbf{RG}_{g,n})^{\rm op}$ to ${\tt H}$.
This is enough to infer, as in the proof of [PR22, Lemma 3.11], that the
functor $\mathcal{F}$ satisfies property (F). ∎

We can now state the main result of the section.

######  Theorem 2.22.

The category $(\mathbf{MG}_{g,n})^{\rm op}$ (resp. $(\mathbf{MPG}_{g,n})^{\rm
op}$) of marked (resp. plane) graphs of combinatorial genus $\leq g$ and
number of marked edges $\leq n$, and minor morphisms, is quasi-Gröbner.

###### Proof.

The statement follows from the previous lemmas, and Proposition 1.12, along
with the observation that the functor
$\mathcal{F}\colon(\mathbf{RG}_{g,n})^{\rm op}\to(\mathbf{MG}_{g,n})^{\rm op}$
is essentially surjective, since every object of $(\mathbf{MG}_{g,n})^{\rm
op}$ is isomorphic to a rigidified marked graph via the functor $\mathcal{F}$.
In the case of plane graphs, the proof can be repeated verbatim with the same,
plane, versions of the statements. ∎

Assume now that $R$ is a left Noetherian ring. As a consequence of Theorems
1.13, 2.20, and 2.22 we have that subquotients of finitely generated
$\mathbf{RG}_{g,n}^{\rm op}$\- and $\mathbf{MG}_{g,n}^{\rm op}$-modules are
finitely generated modules as well. In [MR20], it was shown that the homology
of simplicial complexes associated to graphs with respect to suitable monotone
properties is finitely generated. This is the case, for example, of the
matching complex [Bou92, Wac03]. As the category of graphs (of bounded genus)
and minor morphisms is quasi-Gröbner, consequences of being finitely generated
for a module are, for example, the asymptotic estimates of its dimension and
boundedness of its torsion – see also [Ram22]. In this section we extended
Gröbner-like properties to other categories of graphs – namely, marked, plane
graphs. This can be used to show (almost verbatim) that suitable extensions of
monotone properties in this setting satisfy the same properties; e.g. rainbow
matching complexes. This will be the subject of future work.

In the next section, we will be concerned with magnitude homology. This is not
an homology theory associated to a monotone property of graphs. Nonetheless,
we proceed with the same spirit of this section and show that magnitude
(co)homology is finitely generated in a fixed degree.

##  3\. Magnitude (co)homology

In this section, we prove the main result of the paper, _i.e._ that magnitude
(co)homology of graphs is a finitely generated functor on the category
$\mathbf{C}\mathbf{Graph}^{\rm op}$ of connected graphs and contractions. As a
consequence, we recover structural results on its torsion and ranks. We note
here that all graphs are undirected, but the same statements can be also
inferred for the directed graphs – we will focus on the directed version in a
forthcoming work.

###  3.1. Magnitude homology and cohomology of graphs

We start with recalling the definition of magnitude homology of graphs, and we
will then focus on magnitude cohomology. We will mainly follow [HW17, SS21,
Hep22].

First, observe that a connected graph can be seen as a metric space with the
path metric – the distance between two vertices of the graph being given by
the length of the shortest path in the graph connecting them. To be more
precise, the points of the metric space associated to a graph ${\tt G}$ are
its vertices, and edges are declared to have length $1$. Concretely, the
metric $d$ on ${\tt G}$ is given by

$d(v,w)\coloneqq\min\\{d(v,v_{1})+\sum_{i=1}^{k-2}d(v_{i},v_{i+1})+d(v_{k-1},w)\mid\\{v,v_{1}\\},\\{v_{k-1},w\\},\\{v_{i},v_{i+1}\\}\in
E({\tt G}),i=1,\dots,k-2\\}$

for $v,w$ vertices of ${\tt G}$. If the graph is not connected, we set
$d(v,w)\coloneqq\infty$ for every $v,w\in{\tt G}$ not connected by any path;
hence, for non-connected graphs, $d$ is an extended metric. For a $k$-uple
$(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})\ .$

We can now recall the definition of magnitude chain groups.

######  Definition 3.1.

Let ${\tt G}$ be a graph, and $l,k\in\mathbb{N}$ natural numbers. For a ring
$R$, we let

$\operatorname{\mathrm{MC}}_{k,l}({\tt G};R)\coloneqq
R\langle(v_{0},\dots,v_{k})\mid v_{0}\neq\dots\neq
v_{k},\ell(v_{0},\dots,v_{k})=l\rangle$

be the free $R$-module on the paths of length $l$ on $k+1$ vertices of ${\tt
G}$. The differential $\delta\colon\operatorname{\mathrm{MC}}_{k,l}({\tt
G};R)\to\operatorname{\mathrm{MC}}_{k-1,l}({\tt G};R)$ is defined on $k$-uples
$(v_{0},\dots,v_{k})$ by

$\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.

For a given $l\in\mathbb{N}$, the pair $(\operatorname{\mathrm{MC}}_{*,l}({\tt
G};R),\delta)$ is a chain complex – _c.f._ [HW17, Lemma 2.11].

######  Definition 3.2 ([HW17, Definition 2.4]).

Let ${\tt G}$ be a graph. The _magnitude homology_
$\operatorname{\mathrm{MH}}_{*,*}({\tt G};R)$ of ${\tt G}$ is defined as the
bigraded $R$-module $\bigoplus_{k,l}\operatorname{\mathrm{MH}}_{k,l}({\tt
G};R)$, where

$\operatorname{\mathrm{MH}}_{k,l}({\tt
G};R)\coloneqq\mathrm{H}_{k}(\operatorname{\mathrm{MC}}_{*,l}({\tt
G};R),\delta)$

is given by the homology of the magnitude chain complex.

We can reinterpret the magnitude homology groups as follows – see also [Asa22,
Section 2] for the case of directed graphs. Given a non-negative integer $k$,
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 tuples of vertices of
${\tt G}$. 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$. Note that
these modules can be equipped with the differential $\delta$, with which they
become chain complexes. As $I_{k}({\tt G};R)\subseteq\Lambda_{k}({\tt G};R)$,
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)$. Then, confining
ourselves to the setting of undirected graphs, we get that the magnitude chain
complex $\operatorname{\mathrm{MC}}_{k,l}({\tt G};R)$ can also be defined as
the submodule of $R_{k}({\tt G};R)$ given by tuples of length precisely $l$ –
_cf._ [Asa22, Definition 2.13]; note that this is compatible with the chain
complex structure – _cf._ [Asa22, Lemma 2.14]. We get the following:

######  Remark 3.3.

The magnitude chain modules $\operatorname{\mathrm{MC}}_{k,l}({\tt G};R)$ are
sub-quotients of the free $R$-module $\Lambda_{k}({\tt G};R)$.

It is possible to modify the differential $\delta$ so to get a new
differential $\delta^{\prime}\colon\operatorname{\mathrm{MC}}_{k,l}({\tt
G};R)\to\operatorname{\mathrm{MC}}_{k-1,l-1}({\tt G};R)$, in turn inducing an
homomorphism $\delta^{\prime}\colon\operatorname{\mathrm{MH}}_{k,l}({\tt
G};R)\to\operatorname{\mathrm{MH}}_{k-1,l-1}({\tt G};R)$ between the magnitude
homology groups. Equipped with this new differential, also magnitude homology
can be seen as a chain complex $(\operatorname{\mathrm{MH}}_{k-*,l-*}({\tt
G};R),\delta^{\prime})$. The homology of the resulting chain complex was
denoted by $\mathcal{MH}_{k-*}^{l-*}({\tt G})$ in [Asa22, Definition 2.21].

######  Remark 3.4 ([Asa22, Proposition 6.11]).

In the case $k=l$, the homology theory $\mathcal{MH}_{k-*}^{l-*}({\tt G})$,
for directed graphs, recovers the (reduced) path homology of directed graphs
introduced in [GLMY20]. The same proof, in the undirected setting, produce an
isomorphism of $\mathcal{MH}_{k-*}^{l-*}({\tt G})$ for undirected graphs, with
the reduced path homology of graphs – see, e.g. [BGJW19, Section 2.2] for the
definition.

Magnitude homology is an homology theory of (directed) graphs, and is
functorial with respect to contractions. Recall that a contraction of a graph
${\tt G}$ with respect to an edge $e$ is the graph obtained from ${\tt G}$ by
contracting $e$ to a point. More specifically, if ${\tt G}$ and ${\tt H}$ are
graphs, consider maps $\phi\colon{\tt G}\to{\tt H}$ of vertices that preserve
or contract each edge of ${\tt G}$. Observe that such maps do not increase the
length of tuples of vertices of ${\tt G}$:
$\ell(\phi(v_{0}),\dots,\phi(v_{k}))\leq\ell(v_{0},\dots,v_{k})$. Every
contraction $\phi\colon{\tt G}\to{\tt H}$ of graphs induces a chain map

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

which to a 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. Recall
that we denote by $\mathbf{C}\mathbf{Graph}$ the category of graphs and
contractions.

######  Proposition 3.5 ([HW17, Proposition 3.3]).

Magnitude homology is a functor

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

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

By dualising the definition of magnitude homology, as customary, we get the
definition of magnitude cohomology – see [Hep22] – which we now recall:

######  Definition 3.6.

_Magnitude cohomology_ ${\rm MH}^{*}_{*}$ is the cohomology of the complex

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

equipped with the dual differential.

This defines a functor with respect to the dual maps inducing functoriality in
magnitude cohomology – [Hep22, Definition 2.2]. In particular, the dualisation
defines a functor

$\operatorname{\mathrm{MH}}_{*}^{*}\colon{\bf CGraph}^{{\rm
op}}\to\mathbf{BiGrMod}_{R}\ .$

We recall that in ${\bf CGraph}^{{\rm op}}$ there is a morphism ${\tt
G}\to{\tt G}^{\prime}$ if, and only if, the graph ${\tt G}$ is obtained from
the graph ${\tt G}$ by a sequence of contractions. We conclude the section
observing that magnitude homology and magnitude cohomology are related by a
universal coefficients short exact sequence by [Hep22, Remark 2.5]. Thanks to
this short exact sequence, results on magnitude homology of graphs can be
derived from results on magnitude cohomology, as customary. In the next
subsections, we will restrict ourselves to the case of magnitude cohomology.

###  3.2. Magnitude cohomology is finitely generated

In order to prove that magnitude cohomology (in a fixed $k$-degree) is
finitely generated, we exhibit a finitely generated module such that magnitude
cohomology is a subquotient of it.

Let $\mathbf{Graph}$ be the category of graphs and minor morphisms, and, in
the following, we let $R$ be a commutative ring.

######  Definition 3.7.

The _vertex module_ is the functor $\mathcal{V}\colon{\bf Graph}\to
R\text{\bf-Mod}$, which assigns to each graph ${\tt G}$ the $R$-module

$\mathcal{V}({{\tt G}})=R\left\langle x_{v}\mid v\in V({\tt G})\right\rangle$

freely generated by the vertices of ${\tt G}$. To each minor morphism
$\phi\colon{\tt G}\to{\tt G}^{\prime}$, that is if ${\tt G}^{\prime}$ is
obtained from ${\tt G}$ via a series of contractions and deletions, it assigns
the map $\mathcal{V}(\phi)\colon\mathcal{V}({{\tt
G}}){\longrightarrow}\mathcal{V}({{\tt G}}^{\prime})$ given by $x_{v}\mapsto
x_{\phi(v)}$.

Recall from Definition 1.1 the definition of a finitely generated module, and
from Lemma 1.2 the equivalent definition in terms of projectives. The
following lemma is straightforward:

######  Lemma 3.8.

Let ${\bf C}$ be a category and $\mathcal{F}$ be a finitely generated ${\bf
C}$-module. Then, $\mathcal{F}^{\oplus k}$ is finitely generated.

###### Proof.

By assumption, we have objects $x_{1},\dots,x_{n}$ of $\mathbf{C}$ and a
surjection $\bigoplus_{i=1}^{n}\mathcal{P}_{x_{i}}\to\mathcal{F}$. It follows
that, if we set $y_{ki}=\dots=y_{k(i+1)-1}=x_{i}$, we have a surjection
$\bigoplus_{j=1}^{kn}\mathcal{P}_{y_{j}}\to\mathcal{F}^{\oplus k}$, which
implies that $\mathcal{F}^{\oplus k}$ is finitely generated. ∎

Consider the restriction of the module $\mathcal{V}^{\oplus k}$ to the
category $\mathbf{C}\mathbf{Graph}$ of graphs and contractions.

######  Lemma 3.9.

For each $k$, the magnitude homology $\operatorname{\mathrm{MH}}_{k,*}(-;R)$
is a sub-quotient of $\mathcal{V}^{\oplus k}$.

###### Proof.

It is sufficient to notice that $\Lambda_{k}({\tt G})=\mathcal{V}^{\oplus
k}({\tt G})$, and that the maps which induce the functoriality are induced by
the identification of the vertices of the contracted edges – cf. [HW17,
Definition 2.2] and [Hep22, Section 2]. Taking the directed sum over all
lengths $l$, we get the result. ∎

Magnitude cohomology ${\rm MH}^{*}_{*}$ is by definition the cohomology of the
dual complex of the magnitude homology of graphs. If a module $M$ is a
subquotient of a module $N$, then it is not generally true that ${\rm
Hom}(M,R)$ is a subquotient of ${\rm Hom}(N,R)$. However, this is the case for
magnitude cohomology; in fact, we have the following:

######  Proposition 3.10.

For each $k$ non-negative integer, magnitude cohomology
$\operatorname{\mathrm{MH}}^{k}_{*}(-;R)=\bigoplus_{l}\operatorname{\mathrm{MH}}^{k}_{l}(-;R)$
is a sub-quotient of ${\rm Hom}(\mathcal{V}^{\oplus k},R)$.

###### Proof.

Fix $l$ a natural number and consider the magnitude chain group
$\operatorname{\mathrm{MC}}_{k,l}({\tt G};R)$ of a graph ${\tt G}$. This is a
sub-quotient of $\mathcal{V}^{\oplus k}({\tt G})$ by Lemma 3.9. Observe that
the modules $\Lambda_{k}({\tt G};R),I_{k}({\tt G};R)$ and $R_{k}({\tt G};R)$
are free $R$-modules. It follows immediately that ${\rm Hom}_{R}(R_{k}({\tt
G};R),R)$ is a submodule of ${\rm Hom}_{R}(\Lambda_{k}({\tt G};R),R)={\rm
Hom}_{R}(\mathcal{V}^{\oplus k}({\tt G};R),R)$. Note also that
$\operatorname{\mathrm{MC}}_{k,l}({\tt G};R)$ is spanned by some elements of a
basis of $R_{k}({\tt G};R)$ – _cf_. [Asa22, Definition 2.13]. We have a short
exact sequence

(1) $0\to\operatorname{\mathrm{MC}}_{k,l}({\tt G};R)\to R_{k}({\tt G};R)\to
Q_{k}({\tt G};R)\to 0$

where $Q_{k}({\tt G};R)$ is the associated quotient, which is also a free
$R$-module. In particular, the group
$\operatorname{\mathrm{Ext}}^{i}_{R}(Q_{k}({\tt G};R),M)$ are zero for all
$i\geq 1$ and $R$-module $M$. Hence, dualising the short exact sequence in Eq.
(1), we get the short exact sequence

(2) $0\to{\operatorname{\mathrm{Hom}}}_{R}(Q_{k}({\tt G};R),R)\to{\rm
Hom}_{R}(R_{k}({\tt G};R),R)\to\underbrace{{\rm
Hom}_{R}(\operatorname{\mathrm{MC}}_{k,l}({\tt
G};R),R)}_{=\operatorname{\mathrm{MC}}^{k}_{l}({\tt G};R))}\to 0$

from which the statement follows. ∎

Our goal is now to show that the module ${\rm Hom}(\mathcal{V}^{\oplus k},R)$
is finitely generated. As we do not know whether the full category of graphs
and minor morphisms, or simply contractions, is Noetherian, we will restrict
to the subcategory of graphs with bounded genus.

######  Theorem 3.11.

Let $R$ be a ring with identity. Then, the ${\bf CGraph}^{{\rm op}}_{\leq
g}$-module ${\rm Hom}(\mathcal{V}^{\oplus k},R)$ is finitely generated.

###### Proof.

Thanks to Lemma 3.8, it is sufficient to prove the statement for $k=1$. Denote
by ${\tt S}(m_{1},m_{2},m_{3})$ and ${\tt R}(m)$ the graphs illustrated in
Figure 2: the graph ${\tt R}(m)$ is a rose of genus $m$, whereas the graph
${\tt S}(m_{1},m_{2},m_{3})$ has $m_{1}$ self-loops at $v_{1}$, $m_{3}$ self-
loops at $v_{2}$, and $m_{2}+1$ edges connecting $v_{1}$ and $v_{2}$, where
the sum $m_{1}+m_{2}+m_{3}$ is bounded by $g$.

Let ${\tt G}$ be a graph and $v\in V({\tt G})$. Denote by $\delta_{v}\colon
V({\tt G})\to R$ the function which is $1_{R}$ at the vertex $v$, and $0$
otherwise. Firstly, assume that ${\tt G}$ has no edges. Then ${\tt G}\cong{\tt
R}(m)$, $m\leq g$, thus ${\rm Hom}(\mathcal{V}({\tt
G}),R)=R\langle\delta_{v}\rangle\cong\mathcal{P}_{{\tt R}(m)}({\tt G})$. Thus,
we can assume that ${\tt G}$ has at least one edge.

Fix a spanning tree ${\tt T}$ of ${\tt G}$. For each $e\in E({\tt T})$, the
contraction of all edges in ${\tt T}$ but $e$ gives a morphism

$\phi_{e}\colon{\tt S}(m_{1},m_{2},m_{3})\to{\tt G}\ ,$

for some $m_{1},m_{2},m_{3}$ such that $m_{1}+m_{2}+m_{3}=m\leq g$ is the
combinatorial genus of ${\tt G}$. While the contraction of the whole ${\tt T}$
gives a morphism $\psi_{T}\colon{\tt R}(m)\to{\tt G}$. Now, to each $\phi_{e}$
we associate the function

$f_{e}\colon V({\tt G})\to R$

which is $1_{R}$ when evaluated at the vertices which are contracted to
$v_{1}$, and is $0$ on the remaining vertices. While to $\psi_{T}$ we assign
the function $\imath$ whose value is $1_{R}$ on each vertex of ${\tt G}$. To
prove the theorem, it is sufficient to show that the $\delta_{v}$’s are in the
span of these functions. Fix a root $r$ on ${\tt T}$ and let $d$ be the width
of ${\tt T}$ with respect to $r$ – that is the maximum distance from $r$. If
the distance of $v\in V({\tt T})=V({\tt G})$ from $r$ is $d$ (and more
generally if $v$ is a leaf) then $v$ is the univalent vertex of an edge $e$.
Then, we obtain $\delta_{v}$ is either as $f_{e}$ or as $\imath-f_{e}$.

Assume that $\delta_{v}$ belongs to $R\langle\iota,\,f_{e};\ e\in E({\tt
T})\rangle$, for all $v$ such that $d(v,r)\geq k$, for some $k>0$. We show
that $\delta_{w}\in R\langle\iota,\,f_{e};\ e\in E({\tt T})\rangle$, for all
$w$ such that $d(w,r)=k-1$, and this concludes the proof. If $k-1>0$, then
$w\neq r$. Let $e=\\{w,w^{\prime}\\}\in E({\tt G})$ be such that
$k-1>d(w^{\prime},r)$. Then, there is $f\in\\{f_{e},\imath-f_{e}\\}$ whose
value is $1_{R}$ on $w$ and on some vertices $v_{1},...,v_{k}$ farther than
$w$ from $r$, and $0$ on the otherwise. It follows that

$\delta_{w}=f-\sum_{i}\delta_{v_{k_{i}}}\in R\langle\iota,\,f_{e};\ e\in
E({\tt T})\rangle\ ,$

as desired. To conclude, if $k-1=0$, then $w=r$. In this case
$\delta_{w}=f-\sum_{v\neq r}\delta_{v}\in R\langle f_{e},\iota\mid e\in E({\tt
T})\rangle\ ,$ and the statement follows. ∎

$v_{1}$$v_{2}$$\left.\vdots\right.\ m_{2}$$m_{1}$$m_{3}$${\tt
S}(m_{1},m_{2},m_{3})$${\tt R}(m)$ Figure 2. Generators of the ${\bf
Graph}^{{\rm op}}_{\leq g}$-module ${\rm Hom}(\mathcal{V}^{\oplus k},R)$. The
total number of blue arcs in ${\tt S}(m_{1},m_{2},m_{3})$ is lower equal than
$g$.

Let $R$ be a commutative Noetherian ring, with identity. We can now state the
main result of the section:

######  Corollary 3.12.

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

###### Proof.

By Proposition 2.8, the (opposite) category ${\bf CGraph}^{{\rm op}}_{\leq g}$
of graphs of bounded genus and contractions is quasi-Gröbner, hence sub-
quotients of finitely generated ${\bf CGraph}^{{\rm op}}_{\leq g}$-modules are
finitely generated by Theorem 1.13. By Theorem 3.11, the ${\bf CGraph}^{{\rm
op}}_{\leq g}$-module ${\rm Hom}(\mathcal{V}^{\oplus k},R)$ is finitely
generated. Therefore, the statement now follows from Proposition 3.10. ∎

###  3.3. Applications

A first consequence of the finite generation property described in Corollary
3.12 is a bound on the magnitude (co)homology ranks that depends on the number
of eges of the considered graphs. We will follow [PR22]. Our first corollary
is a general result for graphs of bounded genus, and the second is related to
subsequent subdivisions.

######  Corollary 3.13.

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 ${\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}$.

###### Proof.

The statement directly follows from [PR22, Proposition 4.3] after noticing
that magnitude cohomology, in cohomological degree $k$ and independently on
the length degree $l$, is a subquotient of a module which is finitely
generated in degree $\leq g+1$ – that is, generated by the graphs ${\tt
S}(m_{1},m_{2},m_{3})$ and ${\tt R}(m)$, for $m_{1}+m_{2}+m_{3},m\leq g$. ∎

Let ${\tt G}$ be a graph of genus $g$, $\underline{e}=(e_{1},\dots,e_{r})$ a
tuple of distinct edges of ${\tt G}$ which are not self-loops. We fix a
direction on $e_{1},\dots,e_{r}$. This extra data is auxiliary, that is the
choice of the direction is immaterial, but it is needed to explicitly write
down the functor below. For a tuple $\underline{m}=(m_{i},\dots,m_{r})$ of
non-negative integers, we let ${\tt G}(\underline{e},\underline{m})$ be the
graph obtained from ${\tt G}$ by subdividing each edge $e_{i}$ a number of
$m_{i}$ times. If $m_{i}=0$, then “subdivision” means “contraction” of the
edge $e_{i}$. Recall from Remark 1.11 that the category $\mathbf{OI}$ is the
category of linearly ordered finite sets and ordered inclusions, and is
Gröbner. Consider the product category $\mathbf{OI}^{r}$. The directions on
the edges $e_{i}$ have been chosen in order to construct a subdivision functor

$\Phi_{{\tt G},\underline{e}}\colon\mathbf{OI}^{r}\to{\bf CGraph}^{{\rm
op}}_{\leq g}$

which associates to a linearly ordered set $[\underline{m}]\in\mathbf{OI}^{r}$
the graph ${\tt G}(\underline{e},\underline{m})$, and to a morphism
$[\underline{m}]\to[\underline{n}]$ in $\mathbf{OI}^{r}$ a contraction ${\tt
G}(\underline{e},\underline{n})\to{\tt G}(\underline{e},\underline{m})$ – see
[PR22, Section 4.2] for the details. The provided construction is of interest
to us because of the following result:

######  Proposition 3.14 ([PR22, Proposition 4.4]).

The functor $\Phi_{{\tt G},\underline{e}}\colon\mathbf{OI}^{r}\to{\bf
CGraph}^{{\rm op}}_{\leq g}$ satisfies property (F).

The proposition implies that, if $\mathcal{M}$ is a ${\bf CGraph}^{{\rm
op}}_{\leq g}$-module which is a subquotient of a module ${\bf CGraph}^{{\rm
op}}_{\leq g}\to R\text{\bf-Mod}$ (with $R$ here a field) that is finitely
generated in degrees $\leq d$, _i.e._ by graphs with at most $d$ edges, then
the dimension of $\mathcal{M}({\tt G}(\underline{e},\underline{m}))$ is
bounded by a polynomial in $\underline{m}$ of degree $\leq d$ – _c.f._ [PR22,
Corollary 4.5]. As a consequence, we have the following:

######  Corollary 3.15.

Let $R$ be a field and ${\tt G}$ be a graph of genus $g$. Then, there exists a
polynomial $f_{{\tt G},\underline{e}}(x_{1},\dots,x_{r})$ of total degree at
most $g+1$ such that

$\dim_{R}\operatorname{\mathrm{MH}}_{l}^{k}({\tt
G}(\underline{e},\underline{m});R)=f_{{\tt
G},\underline{e}}(m_{1},\dots,m_{r})\ ,$

provided $\underline{m}$ is large enough in each entry.

###### Proof.

The statement directly follows from [PR22, Corollary 4.5] after noticing that
magnitude cohomology is a subquotient of a module which is finitely generated
in degree $\leq g+1$ – that is the graphs ${\tt S}(m_{1},m_{2},m_{3})$ and
${\tt R}(m)$, for $m_{1}+m_{2}+m_{3},m\leq g$. ∎

Likewise, a similar result is obtained by considering the functor
$\operatorname{\mathrm{MH}}_{*}^{k}=\bigoplus_{l}\operatorname{\mathrm{MH}}_{l}^{k}$,
as the finite generation of the magnitude cohomology functor only depends on
$k$ and not on $l$.

$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{m}$$e_{m}$$e_{0}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$\cdot$$\cdot$$\cdot$
Figure 3. The cycle graph ${\tt C}_{m}$.

######  Example 3.16.

Let ${\tt C}_{m}$ be a cycle graph with $m$ edges – see Figure 3. Subdivision
of any edge of ${\tt C}_{m}$ yields again a cycle. The magnitude homology of
cycles have been computed in [Gu18, Theorems 4.6 & 4.8], proving a conjecture
of [HW17, Appendix A.1]. For a fixed $k$, it can be shown that, in their
notation, the dimension

(3) $T^{m}_{k,l}=\dim_{\mathbb{Z}}{\rm MH}_{k,l}({\tt C}_{m})=a(k,l)m+b(k,l)\
.$

Note that $a(k,l),b(k,l)\neq 0$ for finitely many values of $l$, whose number
is dependent on $k$. Hence for each $k$ we can set $A(k)=\sum_{l}a(k,l)$ and
$B(k)=\sum_{l}b(k,l)$. It follows that $T^{m}_{k,l}\leq A(k)m+B(k)$.

Corollary 3.13 and Corollary 3.15 do not provide sharp results, see Example
3.16. However, they generalise what happens in the aforementioned example, to
graphs of fixed or bounded genus. More precisely, Corollary 3.13 is the
analogue of the inequality $T^{m}_{k,l}\leq A(k)m+B(k)$ in Example 3.16.
Corollary 3.15 is the analogue of the formula in Equation (3), for families of
graphs obtained via subdivision of edges. By applying [PR22, Corollary 4.7],
we get a similar statement when considering the operation of “gluing” trees to
${\tt G}$. We refer to [PR22] for more applications.

A second application, of main interest to us, concerns the behaviour of
torsion in magnitude (co)homology. It was shown in [SS21, Theorem 3.14] that
any finitely generated Abelian group may appear as a subgroup of the magnitude
homology of a graph, and that there are infinitely many such graphs. More
precisely, Sadzanovic and Summers proved the following:

######  Theorem 3.17 ([SS21, Theorem 3.13]).

Let $p$ be a prime and $n,m\geq 1$ integers. There exist infinitely many
distinct isomorphism classes of graphs whose magnitude homology contains
$\mathbb{Z}_{p^{m}}$ torsion in bigrading $(3,2n+3)$.

The proof of [SS21, Theorem 3.13] is based on Kaneta-Yoshinaga construction
[KY21]. Graphs whose integral magnitude homology has ${p^{r}}$-torsion are
obtained from triangulations of (generalised) lens spaces and iterated
subdivisions. However, there is no structural theorem concerning the
complexity of graphs having given torsion in integral magnitude homology. The
next result suggests that, in order to find more torsion in magnitude
(co)homology, one needs to increase the combinatorial complexity of the
graphs.

######  Theorem 3.18.

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 graph ${\tt
G}$ of genus at most $g$.

###### Proof.

First, note that magnitude homology and magnitude cohomology are related by a
universal coefficients short exact sequence by [Hep22, Remark 2.5], hence we
can restrict to magnitude cohomology (and results for magnitude homology will
be derived by application of such short exact sequence).

Fix a degree $k$, and take $R=\mathbb{Z}$ the integers. By Corollary 3.12, the
${\bf CGraph}^{{\rm op}}_{\leq g}$-module
$\operatorname{\mathrm{MH}}^{k}_{l}(-;\mathbb{Z})$ is finitely generated. Let
${\tt G}$ be a graph of bounded genus $\leq g$, and $\tau$ a torsion class in
$\operatorname{\mathrm{MH}}^{k}_{l}({\tt G};\mathbb{Z})$. For $\phi\colon{\tt
H}\to{\tt G}$ a contraction of graphs, we get by functoriality a map in
magnitude cohomology that preserves the torsion class. Therefore, we can
consider the submodule
$\mathcal{T}\subseteq\operatorname{\mathrm{MH}}^{k}_{l}(-;\mathbb{Z})$ which
sends a graph ${\tt G}$ to the $\mathbb{Z}$-module
$\operatorname{\mathrm{MH}}^{k}_{l}({\tt G};\mathbb{Z})$. Then, by Proposition
2.8, the ${\bf CGraph}^{{\rm op}}_{\leq g}$-module $\mathcal{T}$ is also
finitely generated. But, by definition, this means that there exist graphs
${\tt G}_{1},\dots,{\tt G}_{m(k)}$ of genus bounded by $g$, and a surjection
$\bigoplus_{i=1}^{m(k)}\mathcal{P}_{{\tt G}_{i}}\to\mathcal{T}$ from the
associated principal projectives. Now, choose $N$ to be the least common
multiple of the annihilators of $\mathcal{T}({\tt
G}_{1}),\dots,\mathcal{T}({\tt G}_{m(k)})$; then, for any graph ${\tt G}$ in
${\bf CGraph}^{{\rm op}}_{\leq g}$, the torsion part of
$\operatorname{\mathrm{MH}}^{k}_{l}({\tt G};\mathbb{Z})$ has exponent at most
$N$. This concludes the proof. ∎

From Remark 3.4 and [Asa22] follows that (reduced) path homology, as
introduced in [GLMY20], appears as the diagonal in the second page of a
spectral sequence whose $0$-th page features magnitude chain groups. Shifting
to later pages in the spectral sequence is obtained by subsequent
subquotients. Therefore, after restricting to undirected graphs, Theorem 3.11
yields, with the same proof of Theorem 3.18, the following:

######  Corollary 3.19.

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

## References

  * [AHK21] Y. Asao, Y. Hiraoka, and S. Kanazawa.  Girth, magnitude homology, and phase transition of diagonality, 2021.
  * [Asa22] Y. Asao.  Magnitude homology and path homology.  Bulletin of the London Mathematical Society, 2022.
  * [Bar15] D. Barter.  Noetherianity and rooted trees, 2015.
  * [BGJW19] H. Barcelo, C. Greene, A. S. Jarrah, and V. Welker.  Discrete cubical and path homologies of graphs.  Algebr. Comb., 2(3):417–437, 2019.
  * [Bou92] S. Bouc.  Homologie de certains ensembles de $2$-sous-groupes des groupes symétriques.  J. Algebra, 150(1):158–186, 1992.
  * [Bur22] S. Burkin.  Operads and categories in representation stability theory, 2022.
  * [CCDT21] L. Caputi, C. Collari, and S. Di Trani.  Multipath cohomology of directed graphs, 2021.  ArXiv:2108.02690.
  * [CCDT22] L. Caputi, C. Collari, and S. Di Trani.  Combinatorial and topological aspects of path posets, and multipath cohomology.  Journal of Algebraic Combinatorics, 2022.  https://doi.org/10.1007/s10801-022-01180-9.
  * [CEF15] T. Church, J. S. Ellenberg, and B. Farb.  FI-modules and stability for representations of symmetric groups.  Duke Mathematical Journal, 164(9):1833 – 1910, 2015.
  * [CEFN14] T. Church, J. S. Ellenberg, B. Farb, and R. Nagpal.  $\mathrm{FI}$-modules over Noetherian rings.  Geometry & Topology, 18(5):2951 – 2984, 2014.
  * [CR22] L. Caputi and H. Riihimäki.  Hochschild homology, and a persistent approach via connectivity digraphs, 2022.
  * [GG23] H. Gimperlein and M. Goffeng.  The Willmore energy and the magnitude of Euclidean domains.  Proc. Amer. Math. Soc., 151(2):897–906, 2023.
  * [GL15] W. L. Gan and L. Li.  Noetherian property of infinite EI categories.  New York J. Math., 21:369–382, 2015.
  * [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.
  * [Gu18] Y. Gu.  Graph magnitude homology via algebraic morse theory, 2018.
  * [Hep22] R. Hepworth.  Magnitude cohomology.  Math. Z., 301(4):3617–3640, 2022.
  * [HGR05] L. Helme-Guizon and Y. Rong.  A categorification for the chromatic polynomial.  Algebraic & Geometric Topology, 5(4):1365 – 1388, 2005.
  * [HW17] R. Hepworth and S. Willerton.  Categorifying the magnitude of a graph.  Homology Homotopy Appl., 19(2):31–60, 2017.
  * [JHR06] E. F. Jasso-Hernandez and Y. Rong.  A categorification for the Tutte polynomial.  Algebr. Geom. Topol., 6:2031–2049, 2006.
  * [Kho00] M. Khovanov.  A categorification of the Jones polynomial.  Duke Math. J., 101(3):359–426, 2000.
  * [KY21] R. Kaneta and M. Yoshinaga.  Magnitude homology of metric spaces and order complexes.  Bull. Lond. Math. Soc., 53(3):893–905, 2021.
  * [Lei13] T. Leinster.  The magnitude of metric spaces.  Doc. Math., 18:857–905, 2013.
  * [Lei19] T. Leinster.  The magnitude of a graph.  Math. Proc. Cambridge Philos. Soc., 166(2):247–264, 2019.
  * [Lei21] T. Leinster.  Entropy and diversity. The axiomatic approach.  Cambridge: Cambridge University Press, 2021.
  * [LM17] T. Leinster and M. W. Meckes.  The magnitude of a metric space: from category theory to geometric measure theory.  In Measure theory in non-smooth spaces, Partial Differ. Equ. Meas. Theory, pages 156–193. De Gruyter Open, Warsaw, 2017.
  * [LS21] T. Leinster and M. Shulman.  Magnitude homology of enriched categories and metric spaces.  Algebr. Geom. Topol., 21(5):2175–2221, 2021.
  * [Lüc89] W. Lück.  Transformation groups and algebraic $K$-theory, volume 1408 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin, 1989.  Mathematica Gottingensis.
  * [LW13] T. Leinster and S. Willerton.  On the asymptotic magnitude of subsets of Euclidean space.  Geom. Dedicata, 164:287–310, 2013.
  * [MR20] D. Miyata and E. Ramos.  The graph minor theorem in topological combinatorics, 2020.
  * [PR22] N. Proudfoot and E. Ramos.  The contraction category of graphs.  Represent. Theory, 26:673–697, 2022.
  * [Ram22] E. Ramos.  The graph minor theorem meets algebra.  Notices Amer. Math. Soc., 69(8):1297–1305, 2022.
  * [SP94] A. R. Solow and S. Polasky.  Measuring biological diversity.  Environ. Ecol. Stat., 1:95–103, 1994.
  * [SS17] S. V. Sam and A. Snowden.  Gröbner methods for representations of combinatorial categories.  J. Amer. Math. Soc., 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.
  * [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.
  * [Wil14] S. Willerton.  On the magnitude of spheres, surfaces and other homogeneous spaces.  Geom. Dedicata, 168:291–310, 2014.