# Cofiltrations of spanning trees in multiparameter persistent homology

Fritz Grimpen<EMAIL_ADDRESS>Institute for Algebra, Geometry, Topology
and its Applications (ALTA), Department of Mathematics, University of Bremen,
Germany  and  Anastasios Stefanou<EMAIL_ADDRESS>Institute for
Algebra, Geometry, Topology and its Applications (ALTA), Department of
Mathematics and Computer Science, University of Bremen, Germany

###### Abstract.

Given a multiparameter filtration of simplicial complexes, we consider the
problem of explicitly constructing generators for the multipersistent homology
groups with arbitrary PID coefficients. We propose the use of spanning trees
as a tool to identify such generators by introducing a condition for
persistent spanning trees, which is accompanied by an existence result for
cofiltrations consisting of spanning trees. We also introduce a generalization
of spanning trees, called spanning complexes, for dimensions higher than one,
and we establish their existence as a first step towards this direction.

###### Key words and phrases:

Cofiltrations, Spanning Trees, Multiparameter Persistent Homology

###### 2020 Mathematics Subject Classification:

Primary 55N31; secondary 05C50, 05C90

###### Contents

  1. 1 Introduction
    1. 1.1 Multiparameter persistence
    2. 1.2 Minimal presentations
    3. 1.3 Related work
    4. 1.4 Motivation
    5. 1.5 Our contributions
    6. 1.6 Organization
  2. 2 Preliminaries
    1. 2.1 Simplicial homology
    2. 2.2 Persistence modules and persistent homology
  3. 3 Spanning trees of simplicial complexes
  4. 4 Filtrations and cofiltrations of spanning trees
  5. 5 $R$-spans of persistence modules
  6. 6 Generating persistent first homology
  7. 7 Higher-dimensional spanning complexes

##  1\. Introduction

Persistent homology studies the evolution of topological features of a dataset
(finite metric space) across a given filtration on the dataset [ELZ02]. It is
arguably the most heavily used tool in Topological Data Analysis (TDA) [Car09,
EH10]. Persistent homology has the algebraic structure of an
$\mathbb{N}$-graded module [CZCG05].

###  1.1. Multiparameter persistence

Persistent homology extends naturally from one-parameter filtrations [ZC05] to
multiparameter filtrations of datasets [CZ09]. The corresponding algebraic
structure of multiparameter homology is that of an $\mathbb{N}^{d}$-graded
module, as shown in [CZ09]. In fact persistent homology can be defined for
filtrations parameterized over any poset $Q$ [BS14]. The extension from graded
modules to multigraded modules is of particular importance to TDA, since there
are situations where important information from data cannot be captured from
persistent homology by merely considering one-parameter filtration, e.g.
persistent homology is shown to be unstable to the presence of outliers [CZ09,
LW15]. By introducing a density parameter as a second filtration parameter on
datasets, outliers in datasets can then be regarded as noise, making two-
parameter persistent homology robust to the presence of outliers in the data.
Thus, additional information from datasets can be extracted from datasets by
studying multiparameter persistent homology. In multiparameter persistence, in
general, there is no way to visualize the indecomposable modules as interval
modules [CZ09, DX22], as in the case of one-parameter persistence [BC20,
Cra15]. Therefore, recent research works in multipersistence theory have been
focusing on the study of multipersistent invariants [KM21, Pat18].

###  1.2. Minimal presentations

The key techniques to better understand the structure of multiparameter
persistence modules as well as to help towards an efficient computation of
multipersistent invariants of modules, are the minimal free presentations,
minimal free resolutions [CLO05], and the recently introduced minimal flat-
injective presentations [Mil20] of multigraded modules. However, in practice,
all of these techniques often pre-assume that the module is equipped with a
set of generators to begin with, and that the multigraded module is a
submodule of some given free module. Gröbner basis methods can then be
utilized to compute a minimal presentation and a minimal free resolution of
the module [CLO05, LS98, MS05]. As of now, the problem of finding an efficient
way to compute a minimal presentation of multiparameter persistence modules
remains open. Some works in TDA towards this direction include [CSZ10, CSV17,
LW22].

###  1.3. Related work

In [CSZ10] the authors show that if a multifiltration
$X=(X_{a})_{a\in\mathbb{N}^{d}}$ is one-critical, i.e. every simplex enters
the multifiltration in at most one multidegree (thereby making each $C_{n}(X)$
a free module), then Schreyer’s algorithm [CLO05] can be directly applied for
computing a Gröbner basis for the $n$-cycle module
$Z_{n}(X)=\operatorname{Ker}\partial_{n}$ of the homology module
$H_{n}(X)=\operatorname{Ker}\partial_{n}/\operatorname{Im}\partial_{n+1}$ of a
multifiltration $X$, and thus for computing a minimal free presentation for
the homology module. In [CSV17], the authors attempted to describe in an
explicit and combinatorial way the multigraded module structure of the
homology of any multifiltration of simplicial complexes. They developed a
construction that realizes the $n$-th homology module $H_{n}(X)$ of a
multifiltration $X$, as the homology $\operatorname{Ker}f/\operatorname{Im}g$
of a certain chain complex $F_{1}\xrightarrow{f}F_{2}\xrightarrow{g}F_{3}$ of
free multigraded modules. They also proved that the multigraded modules that
can occur as $R$-spans of multifiltrations of sets are the direct sums of
monomial ideals.

In the case of a $2$-parameter filtration $X$, they construct a free
presentation

$F_{1}\to F_{0}\to H_{n}(X)\to 0$

for the homology module $H_{n}(X)$, where $F_{1}$ is explicitly defined and
$F_{0}$ is the kernel of a morphism between certain free modules. However,
that kernel module $F_{0}$, although free, was not defined explicitly, as
mentioned by the authors, and therefore there was not an explicit method given
for computing a (minimal) free presentation for $H_{n}(X)$. The issue was
later resolved in [LW22], where the authors devised a general algorithm for
computing minimal presentation for $2$-parameter persistence modules (also
called bigraded modules), whenever they are represented as
$M\cong\operatorname{Ker}g/\operatorname{Im}g$ (for instance via the
combinatorial presentation of [CSV17]), for some chain complex of free
$2$-parameter persistence modules
$F_{1}\xrightarrow{f}F_{2}\xrightarrow{g}F_{3}$. In both works, for $d=2$, the
authors are invoking the algebraic-geometric fact that over two variables
($2$-parameters), kernels of free bigraded modules are also free. This is no
longer true when we work on multigraded modules over $d\geq 3$ parameters.

###  1.4. Motivation

Our goal is to develop a method for computing (minimal) generators for the
homology of a multifiltration. Our work is motivated by the problem of
computing generators of kernels of morphisms of _upper-set decomposable_
modules (direct sums of monomial ideals) as in [CSV17]. However, in this work
our approach is to investigate a way to find (minimal) free generators for the
$n$-cycle module $Z_{n}(X)$ of a multifiltration $X$, since this would be
enough for our goal. Indeed, if we know the generators of $Z_{n}(X)$, because
of the canonical epimorphism from $Z_{n}(X)$ onto $H_{n}(X)$, we will also
obtain free generators for $H_{n}(X)$. This will then enable us, at least
implicitly, to be able to apply the machinery of commutative algebra to
compute a minimal free presentation and a minimal free resolution of the
homology of a multifiltration. In the static case of simplicial complexes, we
can compute the generators of the first homology group $H_{1}(X)$ of a given
complex $X$ by using spanning tree subcomplexes $T$ of $X$. We have the
following theorem which is known from many sources in the literature.

######  Theorem 1 ([Koz20, Spa82]).

If $X$ is a 1-dimensional simplicial complex and $T$ a spanning tree of $X$,
then $H_{1}(X)\cong C_{1}(X,T)$.

###  1.5. Our contributions

The main contribution of this work is a method to construct generators of the
$1$-dimensional cycle module $Z_{1}(X;R)=\operatorname{Ker}\partial_{1}$ for a
given multifiltration $X=(X^{q})_{q\in Q}$ of finite simplicial complexes over
a finite poset $Q$ and an arbitrary principal ideal domain $R$. To the
multifiltration $X$ we associate a _cofiltration of spanning trees_
$T=(T^{q})_{q\in Q}$ by endowing the simplicial complex $\bigcup_{q\in
Q}X^{q}$ with a simplicial order. We show that these multifiltrations satisfy
the following crucial property.

######  Theorem 2.

For any poset $Q$ and any $Q$-indexed filtration $X=(X^{q})_{q}$ of simplicial
complexes, there exists a $Q$-indexed filtration $T=(T^{q})_{q}$ of spanning
trees of $X$ satisfying $X^{q}\setminus T^{q}\subseteq X^{q^{\prime}}\setminus
T^{q^{\prime}}$ for any pair $q\leq q^{\prime}$ in $Q$.

This existence result for a cofiltration of spanning trees $T$ associated to
$X$ allows us to associate to every edge $\sigma$ contained in $X$ but not in
$T$ an upper-set decomposable module $M_{\sigma}$. We show that the direct sum
$\bigoplus_{\sigma}M_{\sigma}$, where $\sigma$ ranges over any edge $\sigma$
in $X$ but not in $T$, admits a canonical epimorphism of persistence modules
onto $Z_{1}(X)$, and subsequently onto $H_{1}(X)$.

######  Theorem 3.

Let $Q$ be any finite poset and $X=(X^{q})_{q\in Q}$ a $Q$-indexed filtration
of finite simplicial complexes. Then, given a choice of simplicial order on
$X$ there exists an epimorphism $\varphi_{1}\colon M\to Z_{1}(X)$, where $M$
is an upper set decomposable module, constructed explicitly from the
cofiltration of order-minimal spanning trees.

As a last step and in order to generalize that technique to higher homology
groups $H_{n}(X)$, $n\in\mathbb{N}$, we introduce a direct generalization of
spanning trees to higher dimensions. We call this generalized structure an
_$n$ -spanning complex_ and show the existence by an application of Zorn’s
lemma.

######  Theorem 4.

For any simplicial complex $X$ and any $n\in\mathbb{N}$ there exists a
subcomplex $A$ such that $Z_{n}(A)=0$ and $B_{n-1}(A)=B_{n-1}(X)$, i.e. $X$
admits an $n$-spanning complex.

###  1.6. Organization

In Section 2, we recall the basic definitions of partially ordered sets,
simplicial complexes, simplicial homology, persistence modules, and persistent
simplicial homology. In Section 3, we define our notion of spanning trees in
terms of the boundaries and chains of subcomplexes. Subsequently, we state an
edge-exchange lemma (Lemma 6) and the existence of a classical isomorphism
associated to spanning trees (Theorem 7).

In Section 4, we investigate the previously introduced notion of spanning
trees on their behavior under persistence. In order to describe this behavior,
we introduce the notion of a cofiltration of spanning trees (Definition 24)
and prove that they always exist for finite posets and (globally) finite
filtrations (Theorem 26).

The Section 5 is used to collect a variety of algebraic statements concerning
so-called $R$-spans of set-valued diagrams over any small category. These
results are meant to be used in Section 6, where we construct from a
cofiltration of spanning trees an upper set decomposable persistence module
that enjoys an epimorphism onto the first persistent homology group (Theorem
38).

The last section, Section 7, is meant as an outlook to analogue results for
higher-dimensions. We introduce the generalized notion of $n$-spanning
complexes and show that their existence follows from Zorn’s lemma (Theorem
42).

##  2\. Preliminaries

Throughout this paper, let $R$ be a principal ideal domain.

Let $Q$ be a non-empty set. Recall that a _partial order_ on $Q$ is a relation
$\mathord{\leq}\subseteq Q\times Q$, where $(q,q^{\prime})\in\mathord{\leq}$
is denoted by $q\leq q^{\prime}$, satisfying the following three properties
for all $q,q^{\prime},q^{\prime\prime}\in Q$:

  1. (i)

$q\leq q$ (_Reflexivity_).

  2. (ii)

$q\leq q^{\prime}$ and $q^{\prime}\leq q^{\prime\prime}$ imply $q\leq
q^{\prime\prime}$ (_Transitivity_).

  3. (iii)

$q\leq q^{\prime}$ and $q^{\prime}\leq q$ imply $q=q^{\prime}$
(_Antisymmetry_).

If $\mathord{\leq}$ satisfies also $q\leq q^{\prime}$ or $q^{\prime}\leq q$
for $q,q^{\prime}\in Q$, then $\mathord{\leq}$ is called a _total order_. We
call the pair $(Q,\mathord{\leq})$ a _poset_ whenever $\mathord{\leq}$ is a
partial order. Moreover, if $\mathord{\leq}$ is a total order, then we call
$(Q,\mathord{\leq})$ a _totally ordered set_. A set $X$ is said to be _well-
ordered_ by a partial order $\leq$ if every non-empty subset of $X$ admits a
unique minimal element. Then, $\leq$ is called a _well-ordering_ of $X$, and
we denote by $\min(A)$ the unique minimal element of $A$ for $A\subseteq X$.
In particular, every well-ordering of $X$ is a total order on $X$.

###  2.1. Simplicial homology

Let $V$ be a non-empty set, which we call the _vertex set_ and whose elements
are called _vertices_. An _(abstract) simplicial complex_ (over $V$) is a
subset $X$ of the power set of $V$ such that

  1. (i)

every element $\sigma\in X$ is a finite subset of $V$ and

  2. (ii)

for every element $\sigma\in X$ every subset $\tau$ of $\sigma$ is also an
element of $X$, i.e. $\sigma\in X$ and $\tau\subseteq\sigma$ imply $\tau\in
X$.

The elements of $X$ are called _simplices_. For $n\in\mathbb{N}$ we denote by
$X_{n}$ the simplices in $X$ of cardinality equal to $n+1$, and we define the
_$n$ -skeleton of $X$_ by $\operatorname{skel}_{n}X=\bigcup_{k\leq n}X_{k}$.
Although the vertex set $V$ is part of the simplicial complex $X$, we omit it
unless it is necessary, and then we denote it by $V(X)$. Given simplicial
complexes $X$ over $V$ and $Y$ over $W$, a map $f\colon V\to W$ is a
_simplicial map_ if for $\sigma=\\{v_{0},\dotsc,v_{n}\\}\in X$ it holds
$f(\sigma)=\\{f(v_{0}),\dotsc,f(v_{n})\\}\in Y$. We also write $f\colon X\to
Y$ for a simplicial map. Simplicial complexes with simplicial maps constitute
the category $\operatorname{Simp}$ of simplicial complexes.

For the purposes of (simplicial) homology, the vertex set $V(X)$ of a
simplicial complex $X$ is endowed with a fixed total order $\preceq$. We shall
extend this idea to the whole simplicial complex by endowing a simplicial
complex $X$, viewed as its set of simplices, with a fixed well-ordering
$\preceq$: The pair $(X,\mathord{\preceq})$ is an _ordered simplicial complex_
and $\preceq$ is a _simplicial order_ in this context. Note that an ordered
simplicial complex $(X,\mathord{\preceq})$ induces a total order on the vertex
set $V(X)$ by the correspondence $V\leftrightarrow\\{\\{v\\}\mid v\in V\\}$.
We write $[v_{0},\dotsc,v_{n}]$ to denote the simplex
$\\{v_{0},\dotsc,v_{n}\\}$ if $v_{0}\leq\dotsb\leq v_{n}$.

Let $(X,\mathord{\preceq}_{X})$ and $(Y,\mathord{\preceq}_{Y})$ be ordered
simplicial complexes and let $f\colon X\to Y$ a simplicial map. Then, we say
that $f$ is a _morphism of ordered simplicial complexes_ or a _order-
preserving simplicial map_ if, for all $\sigma,\tau\in X$ satisfying
$\sigma\preceq_{X}\tau$, it follows $f(\sigma)\preceq_{Y}f(\tau)$. We denote
the category with ordered simplicial complexes as objects and order-preserving
simplicial maps by $\operatorname{Simp}_{\mathrm{ord}}$ and call it the
_category of ordered simplicial complexes_.

The category of simplicial complexes admits a (topological) homology theory,
namely _simplicial homology_ , see [Hat15, Spa82]. Let $X$ be a simplicial
complex and let $V(X)$ be endowed with a total order $\leq$. For a simplex
$[v_{0},\dotsc,v_{n}]$ we write $[v_{0},\dotsc,\widehat{v_{i}},\dotsc,v_{n}]$
to denote the simplex $\\{v_{0},\dotsc,v_{n}\\}\setminus\\{v_{i}\\}$.

For $n\in\mathbb{N}$, let $C_{n}(X)$ be the free $R$-module generated by the
$n$-simplices $X_{n}$ and let

$\displaystyle\partial_{n}\colon C_{n}(X)$ $\displaystyle\longrightarrow
C_{n-1}(X)\text{,}$ $\displaystyle[v_{0},\dotsc,v_{n}]$
$\displaystyle\longmapsto\sum_{i=0}^{n}(-1)^{n}[v_{0},\dotsc,\widehat{v_{i}},\dotsc,v_{n}]\text{,}$

be the _boundary homomorphism_ defined on generators of $C_{n}(X)$. The
boundary homomorphisms satisfy $\partial_{n}\circ\partial_{n+1}=0$, and the
quotient $\operatorname{Ker}\partial_{n}/\operatorname{Im}\partial_{n+1}$ is
the _$n$ -th (simplicial) homology module_, which is denoted by $H_{n}(X)$.
Additionally, we define $Z_{n}(X)=\operatorname{Ker}\partial_{n}$ and
$B_{n}(X)=\operatorname{Im}\partial_{n+1}$. We note that $Z_{n}(X)$ and
$B_{n}(X)$ are free since $R$ is a PID by assumption.

###  2.2. Persistence modules and persistent homology

Let $(Q,\mathord{\leq})$ be a poset. A family $(X^{q})_{q\in Q}$ of simplicial
complexes is called a _filtration_ if for all $q,q^{\prime}\in Q$ with $q\leq
q^{\prime}$ it holds $X^{q}\subseteq X^{q^{\prime}}$. Note that
$X^{q^{\prime}}\subseteq\bigcup_{q\in Q}X^{q}$ for every $q^{\prime}\in Q$.
For each $n\in\mathbb{N}$, every pair $q,q^{\prime}\in Q$ with $q\leq
q^{\prime}$ induces a homomorphism of $R$-modules

$H_{n}(X^{q}\subseteq X^{q^{\prime}})\colon H_{n}(X^{q})\longrightarrow
H_{n}(X^{q^{\prime}})\text{.}$

The collection $(H_{n}(X^{q}))_{q\in Q}$ together with these homomorphisms
$H_{n}(X^{q}\subseteq X^{q^{\prime}})$ for all pairs $q,q^{\prime}\in Q$
satisfying $q\leq q^{\prime}$ is called the _$n$ -th persistent homology
module of $(X^{q})_{q\in Q}$_. The underlying algebraic structure is a
_persistence module_.

Given a poset $(Q,\mathord{\leq})$, we can consider its associated _poset
category_ $\mathcal{Q}$ that is given by

$\operatorname{Ob}(\mathcal{Q})=Q\text{,}\qquad\operatorname{Hom}_{\mathcal{Q}}(q,q^{\prime})=\\{(q,q^{\prime})\\}\cap\mathord{\leq}\text{.}$

We denote the associated poset category of $Q$ also by $Q$.

Further, denote by $\operatorname{Mod}_{R}$ the category of $R$-modules. Then,
a _persistence module_ with coefficients in $R$ and indexed over
$Q=(Q,\mathord{\leq})$ is a functor $M\colon Q\to\operatorname{Mod}_{R}$. The
images of morphisms in $Q$ under a persistence module are called the
_structure homomorphisms_ of $M$. The morphisms of persistence modules
$M,N\colon Q\to\operatorname{Mod}_{R}$ are precisely the natural
transformations $M\to N$ . More generally, a persistence module can be indexed
by an arbitrary small category $I$, e.g. $I=\mathcal{Q}$ the posetal category
associated to $(Q,\mathord{\leq})$. We write $\operatorname{Mod}_{R}^{I}$ to
denote the _category of persistence modules_ indexed by the small category
$I$. By abusing notation, we shall write $\operatorname{Mod}_{R}^{Q}$ to
denote the category of persistence modules indexed by the posetal category
associated to $(Q,\mathord{\leq})$.

Furthermore, we call a set-valued functor on $Q$ a _persistent set_ and a
corresponding natural transformation a _persistent map_. The category of
persistent sets is denoted by $\operatorname{Set}^{Q}$.

##  3\. Spanning trees of simplicial complexes

Traditionally, spanning trees of graphs are subgraphs that reflect the
connectivity properties of the original graph while preserving acyclicity and
means to identify cyclic paths in a graph [BM08, Koz20, Lov77]. As such, they
are classically characterized in terms of combinatorial properties on them. We
modify the standard definition of a spanning tree to facilitate the need of
having an algebraic characterization in the following way:

  * •

We characterize spanning trees in terms of their cycle and boundary modules of
simplicial homology, see Definition 5 below.

  * •

The zeroth homology module of a spanning tree does not need to trivialize,
i.e. a spanning tree is not necessarily connected.

Throughout this section, let $X$ be a simplicial complex with vertex set $V$.

######  Definition 5 (Spanning tree).

A _spanning tree_ of $X$ is a simplicial subcomplex $T$ of $X$ such that

  1. (i)

$X_{0}=T_{0}$,

  2. (ii)

the boundary homomorphism $\partial_{1}\colon C_{1}(T)\to C_{0}(T)$ is
injective, and

  3. (iii)

$B_{0}(X)=B_{0}(T)$.

The first condition states the natural assumption that any spanning tree of
$X$ needs to have the same vertices (in the sense of 0-simplices) as $X$.
Further, the second condition requires that any spanning tree of $X$ is indeed
a tree, i.e. the 1-dimensional cycle module of any spanning tree is trivial.

The most useful condition is the third, which roughly states that a spanning
tree indeed spans the space $X$ in the following sense: Suppose that $T$ is a
spanning tree of $X$ and let $u,v$ be vertices of $X$. Further, suppose that
there exists a path in $X$ from $u$ to $v$, i.e. $u$ and $v$ lie in the same
path component of $X$, or equivalent there is a 1-chain $c\in C_{1}(X)$ such
that $\partial_{1}c=u-v$. Then, the third condition implies that there exists
a 1-chain $c^{\prime}\in C_{1}(T)$ such that
$\partial_{1}c=\partial_{1}c^{\prime}\in B_{0}(T)$. Thus, both vertices $u$
and $v$ also lie in the same path component of $T$.

More generally, if $c$ is a 1-chain in $X$, then there always exists a 1-chain
$c^{\prime}$ in $T$ such that $c-c^{\prime}$ is a cycle. Particularly, it
follows from Definition 5 (ii) that the chain $c^{\prime}\in C_{1}(T)$ is
uniquely determined by $c\in C_{1}(X)$.

We are now developing the basic theory of (homological) spanning trees as
above. To that end, we fix the following notation: For sets $X$, $Y$, and $Z$
we write $X\cup Y\setminus Z$ to denote $(X\cup Y)\setminus Z$. That is, the
set difference and union operators have the same precedence and are left-
associative.

Let $T$ be a spanning tree of $X$. We pick some edge (1-simplex) $e$ in $X$
that is not in $T$ and we ask whether there exists another spanning tree of
$X$ that actually contains $e$. It is clear that $A=T\cup\\{e\\}$ still
satisfies $B_{0}(X)=B_{0}(A)$ and $V(X)=V(A)$, and thus the subcomplex $A$
still satisfies two out of three conditions for a spanning tree, see
Definition 5 (i) and (iii). However, it is also easy to see that $Z_{1}(A)\neq
0$. Thus, $A$ does not satisfy the acyclicity condition of spanning trees.

Therefore, the actual question is whether we can find some edge $e^{\prime}$
in $T$ such that $T\cup\\{e\\}\setminus\\{e^{\prime}\\}$ is again a spanning
tree. We call the following the lemma the _edge-exchange lemma_. A similar
statement about spanning trees is known as the _tree exchange property_ , see
[BM08, p. 113, Exercise 4.3.2].

######  Lemma 6.

Let $T$ be a spanning tree of the simplicial complex $X$. Then, for every edge
$\sigma\in X$ that is not contained in $T$, there exists an edge $\tau\in T$
such that $T\cup\\{\sigma\\}\setminus\\{\tau\\}$ is a spanning tree of $X$.

Moreover, if $c$ is a 1-chain in $T$ such that
$\partial_{1}c=\partial_{1}\sigma$, then every simplex in $c$ is admissible as
$\tau$.

###### Proof.

Let $\sigma$ be an edge contained in $X$ but not in $T$. Since $T$ is a
spanning tree, we find a 1-chain $c$ in $T$ such that
$\partial_{1}c=\partial_{1}\sigma$. Moreover, we can choose
$\lambda_{0},\dotsc,\lambda_{k}\in\\{1,-1\\}$ and distinct edges
$\tau_{0},\dotsc,\tau_{k}\in T$ such that
$c=\sum_{i=0}^{k}\lambda_{i}\tau_{i}$. We set $\tau=\tau_{0}$, i.e.
$c=\lambda_{0}\tau+\sum_{i=1}^{k}\lambda_{i}\tau_{i}$.

Let $b\in B_{0}(X)$. Then, we can choosse a 1-chain
$c^{\prime}=\mu_{0}\tau+\sum_{i=1}^{l}\mu_{i}\sigma_{i}$ in $T$ such that
$\partial_{1}c^{\prime}=b$, where the simplices
$\tau,\sigma_{1},\dotsc,\sigma_{k}$ are distinct. By replacing $\tau$ in
$c^{\prime}$ with the 1-chain $\sum_{i=1}^{k}\lambda_{i}\tau_{i}-\sigma$,
which is contained in $X\setminus T$, we obtain the chain

$c^{\prime\prime}=\sum_{i=1}^{k}\mu_{0}\lambda_{i}\tau_{i}-\mu_{0}\sigma+\sum_{i=1}^{k}\mu_{i}\sigma_{i}\text{.}$

Since the chains $\sum_{i=1}^{k}\lambda_{i}\tau_{i}$ and $\sigma$ have the
same boundary, the boundary of $c^{\prime\prime}$ coincides with the boundary
of $c^{\prime}$. Further, the chain $c^{\prime\prime}$ is, by construction,
contained in $T^{\prime}$. Hence,
$\partial_{1}c^{\prime\prime}=\partial_{1}c^{\prime}=b\in B_{0}(T^{\prime})$.
Since $T^{\prime}\subseteq X$, this proves in particular
$B_{0}(X)=B_{0}(T^{\prime})$ and $B_{0}(T)=B_{0}(T^{\prime})$.

Let $z\in Z_{1}(T+\sigma-\tau)$ and choose $\mu_{0},\mu_{1},\dotsc,\mu_{l}\in
R$ and edges $\tau_{1},\dotsc,\tau_{l}$ distinct from $\tau$ in $T$ such that
$z=\mu_{0}\sigma+\sum_{j=1}^{l}\mu_{j}\tau_{j}$. Then, we have $\mu_{0}\neq 0$
unless $z=0$. Therefore, we assume that $z\neq 0$.

Then, we have

$\mu_{0}(u-v)=\mu_{0}\partial_{1}\sigma=-\partial_{1}\sum_{j=1}^{l}\mu_{j}\tau_{j}$

for vertices distinct $u$ and $v$ in $X$. Furthermore, $\mu_{0}\neq 0$ is
invertible since there exists some chain $c\in C_{1}(T)$ satisfying
$\partial_{1}c=u-v$ and $\sum_{j=1}^{l}\mu_{j}\tau_{j}=\mu_{0}c$ by the
injectivity of $\partial_{1}$ on $C_{1}(T)$. Thus,
$u-v=-\partial_{1}\sum_{j=1}^{l}\mu_{j}\mu_{0}^{-1}\tau_{j}$.

However, this means that some of the $\tau_{1},\dotsc,\tau_{j}$ must coincide
with $\tau$ by construction. This is a contradiction to the assumption that
$\tau_{1},\dotsc,\tau_{j}$ are distinct from $\tau$. Hence,
$Z_{1}(T+\sigma-\tau)=0$. ∎

We call a pair $(\sigma,\tau)$ of an edge $\sigma\in X\setminus T$ and an edge
$\tau\in T$ an _edge exchange pair_ if $T\cup\\{\sigma\\}\setminus\\{\tau\\}$
is a spanning tree. For notational convenience, we write $T+\sigma-\tau$ for
the set $T\cup\\{\sigma\\}\setminus\\{\tau\\}$.

We have seen that every edge that is not contained in a spanning tree induces
a cycle, where exactly one edge in this cycle is not contained in the spanning
tree. The following theorem, which is known for a long time, states that the
cycles induced by edges not contained in a spanning tree are precisely the
generators of the $1$-dimensional cycle group of the spanned simplicial
complex. Proofs of this and equivalent results can be found in [Die17, Theorem
1.9.4], [Koz20, Theorem 2.33], and [Spa82, Theorem 3, p. 140].

######  Theorem 7.

Let $T$ be a spanning tree of $X$. Then, the homomorphism

$j\colon Z_{1}(X)\longrightarrow C_{1}(X,T)\text{,}\quad z\longmapsto
z+C_{1}(T)\text{,}$

is an isomorphism of $R$-modules.

###### Proof.

Let $z\in Z_{1}(X)$ such that $z\in C_{1}(T)$. Then, $z=0$ by $Z_{1}(T)=0$.
Hence, $j$ is a monomorphism.

In order to prove the surjectivity of $j$, let $c\in C_{1}(T)$. By
$B_{0}(T)=B_{0}(X)$, we find $c^{\prime}\in C_{1}(T)$ such that
$\partial_{1}c=\partial_{1}c^{\prime}$, that is $c-c^{\prime}\in Z_{1}(X)$.
Then, we have

$j(c-c^{\prime})=c-c^{\prime}+C_{1}(T)=c+C_{1}(T)$

since $c^{\prime}\in C_{1}(T)$. Thus, the homomorphism $j$ is surjective, and
it follows $Z_{1}(X)\cong C_{1}(X,T)$. ∎

Next, we are considering the notion of spanning trees of ordered simplicial
complexes. We assume that any ordered simplicial complex
$(X,\mathord{\preceq})$ satisfies the following properties:

  1. (i)

The total order $\mathord{\preceq}$ is a well-order, i.e. every subset $A$ of
$X$ admits a minimal element.

  2. (ii)

If $\sigma$ is a simplex of $X$ and $\tau$ a face of $\sigma$, then
$\tau\preceq\sigma$.

It turns out that every finite, ordered simplicial complex admits a special,
distinguished spanning tree that is minimal in a certain sense w.r.t. the
well-ordering $\preceq$. We characterize these spanning trees using
lexicographic orders.

######  Definition 8 (Lexicographic orders).

Let $(X,\mathord{\preceq})$ be a well-ordered set, e.g.
$(X,\mathord{\preceq})$ is an ordered simplicial complex. The _lexicographic
order_ $\mathord{\preceq}_{\mathrm{lex}}$ on $2^{X}$ is given by

$A\preceq_{\mathrm{lex}}B\iff A=B\text{ or }\min((A\setminus B)\cup(B\setminus
A))\in A$

for subsets $A,B\subseteq X$.

######  Remark 9.

Let $A,B\subseteq X$, where $X$ is an arbitrary well-ordered set $X$. Then,
$A\preceq_{\mathrm{lex}}B$ if and only if there exists $x\in A\setminus B$
such that for every $y\in(A\setminus B)\cup(B\setminus A)$ it holds $x\preceq
y$.

######  Lemma 10.

The lexicographic order $\preceq_{\mathrm{lex}}$ is a total order.

######  Remark 11.

If $X$ is a finite set, its power set $2^{X}$ is also finite, and then the
lexicographic order $\preceq_{\mathrm{lex}}$ is a well-ordering of $2^{X}$.

######  Example 12.

Consider the totally ordered set $X=\\{1<2<3\\}$ and endow its powerset

$2^{X}=\\{\emptyset,1,2,3,12,13,23,123\\}$

with the lexicographic order $<_{\mathrm{lex}}$, where we denote the subsets
of $X$ as words, e.g. $12=\\{1,2\\}$. Then it holds
$12<_{\mathrm{lex}}13<_{\mathrm{lex}}23$. This motivates the term
“lexicographic order” for the order defined above.

See Figure 1 for a table of all relations in $2^{X}$. We note that $A\subseteq
B$ implies $B<_{\mathrm{lex}}A$ and therefore the element $\emptyset$ is
maximal. Analogously, $X\in 2^{X}$ is minimal w.r.t. the lexicographic order.

When we compare this to the graded lexicographic order $<_{\mathrm{grlex}}$,
see Figure 2, we note that $\emptyset$ is minimal and $X$ is maximal w.r.t.
the graded lexicographic order.

| $\emptyset$ | $1$ | $2$ | $3$ | $12$ | $13$ | $23$ | $123$
---|---|---|---|---|---|---|---|---
$\emptyset$ | $=$ | $\geq$ | $\geq$ | $\geq$ | $\geq$ | $\geq$ | $\geq$ | $\geq$
$1$ |  | $=$ | $\leq$ | $\leq$ | $\geq$ | $\geq$ | $\leq$ | $\geq$
$2$ |  |  | $=$ | $\leq$ | $\geq$ | $\geq$ | $\geq$ | $\geq$
$3$ |  |  |  | $=$ | $\geq$ | $\geq$ | $\geq$ | $\geq$
$12$ |  |  |  |  | $=$ | $\leq$ | $\leq$ | $\geq$
$13$ |  |  |  |  |  | $=$ | $\leq$ | $\geq$
$23$ |  |  |  |  |  |  | $=$ | $\geq$
$123$ |  |  |  |  |  |  |  | $=$
Figure 1. The relations of the lexicographic order on $2^{X}$ for $X=\\{1<2<3\\}$, where the entry “$\geq$” denotes “$\text{row label}\geq\text{column label}$” and the entry “$\leq$” denotes “$\text{row label}\leq\text{column label}$”. | $\emptyset$ | $1$ | $2$ | $3$ | $12$ | $13$ | $23$ | $123$
---|---|---|---|---|---|---|---|---
$\emptyset$ | $=$ | $\leq$ | $\leq$ | $\leq$ | $\leq$ | $\leq$ | $\leq$ | $\leq$
$1$ |  | $=$ | $\leq$ | $\leq$ | $\leq$ | $\leq$ | $\leq$ | $\leq$
$2$ |  |  | $=$ | $\leq$ | $\leq$ | $\leq$ | $\leq$ | $\leq$
$3$ |  |  |  | $=$ | $\leq$ | $\leq$ | $\leq$ | $\leq$
$12$ |  |  |  |  | $=$ | $\leq$ | $\leq$ | $\leq$
$13$ |  |  |  |  |  | $=$ | $\leq$ | $\leq$
$23$ |  |  |  |  |  |  | $=$ | $\leq$
$123$ |  |  |  |  |  |  |  | $=$
Figure 2. The relations of the graded lexicographic order on $2^{X}$ for
$X=\\{1<2<3\\}$, where the entry “$\leq$” means “$\text{row
label}\leq\text{column label}$”.

Let $(X,\mathord{\preceq})$ be an finite, ordered simplicial complex. We
define the set $\mathcal{T}(X)=\\{T\mid\text{$T$ is a spanning tree of
$X$}\\}$. As a subset of the power set of $2^{X}$, we endow it with the
lexicographic ordering $\preceq_{\mathrm{lex}}$. Since $X$ is a finite
simplicial complex, the set $\mathcal{T}(X)$ is also a finite, total ordered
set. Therefore, $\mathcal{T}(X)$ admits a unique, minimal element.

######  Definition 13 (Order-minimal spanning tree).

The minimal element of $\mathcal{T}(X)$ is the _order-minimal spanning tree_
of $(X,\mathord{\preceq})$.

######  Example 14.

Consider the triangle complex $X=\\{\emptyset,1,2,3,12,13,23\\}$. This complex
admits three spanning trees $T_{1}$, $T_{2}$, and $T_{3}$, which are depicted
in Figure 3. When we endow the triangle complex with the lexicographic order
induced by $1\preceq 2\preceq 3$, we see that $T_{1}$ is the order-minimal
spanning tree of $X$.

$T_{1}$$T_{2}$$T_{3}$ Figure 3. The spanning trees $T_{1}$, $T_{2}$, and
$T_{3}$ of the triangle complex. The edges not contained in the spanning trees
are indicated as dashed lines.

######  Lemma 15.

Let $T$ be the order-minimal spanning tree of $(X,\mathord{\preceq})$. Then,
for every edge exchange pair $(\sigma,\tau)$ of $T$ it holds
$\tau\preceq\sigma$.

###### Proof.

We suppose that there exists an edge exchange pair $(\sigma,\tau)$, $\sigma\in
X\setminus T$ and $\tau\in T$, such that $\sigma\prec\tau$. Then, for the
spanning tree $T^{\prime}=T+\sigma-\tau$ we have

$(T^{\prime}\setminus T)\cup(T\setminus T^{\prime})=\\{\sigma,\tau\\}\text{.}$

Then, the minimal element of this symmetric difference is $\sigma$. Thus, it
is contained in $T^{\prime}$, and it follows
$T^{\prime}\prec_{\mathrm{lex}}T$. Hence, $T$ is not order-minimal. ∎

######  Proposition 16.

A spanning tree $T$ of $X$ is order-minimal w.r.t. $\preceq$ if and only if
there is no edge-exchange pair $(\sigma,\tau)\in X\setminus T\times T$ such
that $\sigma\preceq\tau$.

###### Proof.

The assertion follows from Lemma 15 together with Lemma 6: If $T$ is order-
minimal, every edge exchange pair $(\sigma,\tau)$ must satisfy
$\sigma\preceq\tau$. Vice-versa, if $T$ is not order-minimal, let $T^{\prime}$
be an order-minimal spanning tree of $X$ and pick an edge-exchange pair
$(\sigma,\tau)$ where $\sigma$ is an edge in $T^{\prime}$ but not in $T$. ∎

######  Remark 17.

The characterization of order-minimal spanning trees in terms of their edge-
exchange pairs in conjunction with the edge-exchange lemma (Lemma 6) provides
a tactic to reduce a given spanning tree to the order-minimal one.

Let $T$ be any spanning tree of $X$. Then, if $T$ is not order-minimal, we can
iteratively pick an edge exchange pair $(\sigma,\tau)$ such that
$\sigma\preceq\tau$, and replace $T$ by $T+\sigma-\tau$.

This method iteratively reduces the spanning tree $T$ until $T$ is order-
minimal by the characterization above.

######  Definition 18 (Leading simplex).

Let $n\in\mathbb{N}$ and let
$c=\lambda_{1}\sigma_{1}+\dotsb+\lambda_{k}\sigma_{k}$ be a non-zero $n$-chain
of $X$. Suppose that $\sigma_{1},\dotsc,\sigma_{k}$ are distinct,
$\lambda_{1},\dotsc,\lambda_{k}$ are non-zero, and
$\sigma_{1}\preceq\dotsb\preceq\sigma_{k}$. The _leading simplex_
$\operatorname{LS}(c)=\operatorname{LS}_{\mathord{\preceq}}(c)$ of $c$ is
$\sigma_{k}$.

######  Proposition 19.

Let $T$ be an order-minimal spanning tree of $(X,\mathord{\preceq})$. For
every non-zero $z\in Z_{1}(X)$, it holds $\operatorname{LS}(z)\in X\setminus
T$.

###### Proof.

Let $z\in Z_{1}(X)$. Then, there exist simplices
$\sigma_{1},\dotsc,\sigma_{k}$ in $X$ but not in $T$ and non-zero
$\lambda_{1},\dotsc,\lambda_{k}\in R$ such that

$z=\sigma_{1}\lambda_{1}+\dotsc+\lambda_{k}\sigma_{k}+c$

for some 1-chain $c$ in $T$. We choose for every $i\in\\{1,\dotsc,k\\}$ a
1-chain $c_{i}$ in $T$ such that $\partial_{1}c_{i}=\partial_{1}\sigma_{i}$.
Then, we have

$z=\lambda_{1}(\sigma_{1}-c_{1})+\dotsc+\lambda_{k}(\sigma_{k}-c_{k})\in
Z_{1}(X)\text{.}$

Since we can construct an edge-exchange pair $(\sigma_{i},\tau_{i})$ of $T$
for any $i\in\\{1,\dotsc,k\\}$, it follows $\sigma_{i}\preceq\tau_{i}$. In
particular, every $1$-simplex in $c_{i}$ is admissible as $\tau_{i}$, cf.
Lemma 6. Therefore, $\operatorname{LS}(\sigma_{i}-c_{i})=\sigma_{i}$. Hence,
we obviously have

$\displaystyle\operatorname{LS}(z)=\operatorname{LS}(\lambda_{1}(\sigma_{1}-c_{1})+\dotsc+\lambda_{k}(\sigma_{k}-c_{k}))$
$\displaystyle\in\operatorname{LS}\\{\sigma_{i}-c_{i}\mid
i\in\\{1,\dotsc,k\\}\\}$
$\displaystyle=\\{\sigma_{1},\dotsc,\sigma_{k}\\}\subseteq X\setminus
T\text{.}\qed$

##  4\. Filtrations and cofiltrations of spanning trees

Let $Q=(Q,\mathord{\leq})$ be a finite poset and $X=(X^{q})_{q\in Q}$ a
$Q$-indexed filtration of finite simplicial complexes. In this section, we
investigate the question of whether there exists a multipersistent analogue of
spanning trees for filtrations of simplicial complexes. The following result
answers this question in the affirmative under a fairly strong assumption on
$X$, which cannot be satisfied for arbitrary $X$.

Let $T=(T^{q})_{q\in Q}$ be a filtration of simplicial complexes such that
$T^{q}$ is a spanning tree of $X^{q}$ for each $q\in Q$. Then, we can consider
the persistence module $C_{1}(X,T)\colon Q\to\operatorname{Mod}_{R}$ with
$C_{1}(X,T)(q)=C_{1}(X^{q},T^{q})$ for $q\in Q$ and structure maps

$C_{1}(X^{q},T^{q})\to C_{1}(X^{q^{\prime}},T^{q^{\prime}})\text{,}\quad
c+C_{1}(T^{q})\mapsto c+C_{1}(T^{q^{\prime}})\text{.}$

######  Lemma 20.

The structure maps of $C_{1}(X,T)$ are well-defined module homomorphisms.

###### Proof.

Let $q\leq q^{\prime}\in Q$ be a pair. The well-definedness of the structure
map from $C_{1}(X^{q},T^{q})$ to $C_{1}(X^{q^{\prime}},T^{q^{\prime}})$
follows immediately from $T^{q}\subseteq T^{q^{\prime}}$.

Let $c\in C_{1}(X^{q})$ such that $c$ is also a chain in $T^{q^{\prime}}$.
Then, we choose non-zero $\lambda_{1},\dotsc,\lambda_{k}\in R$ and distinct
simplices $\sigma_{1},\dotsc,\sigma_{k}$ in $T^{q^{\prime}}\cap X^{q}$ such
that $c=\sum_{i=1}^{k}\lambda_{i}\sigma_{i}$. We suppose without loss of
generality and to the contrary that $\sigma_{1}\notin T^{q}$. Then,
$T^{q}\cup\\{\sigma_{1}\\}$ is a subcomplex of $X^{q}$ with non-trivial cycle
module. However, $T^{q}\cup\\{\sigma_{1}\\}$ is also a subcomplex of
$T^{q^{\prime}}$ since $\sigma_{1}\in T^{q^{\prime}}$. Thus, we have a
contradiction since $T^{q^{\prime}}$ has trivial cycle module. It follows that
$\sigma_{1},\dotsc,\sigma_{k}$ are contained in $T^{q}$. Therefore, $c$ is a
1-chain in $T^{q}$, and the kernel of the structure map from
$C_{1}(X^{q},T^{q})$ to $C_{1}(X^{q^{\prime}},T^{q^{\prime}})$ is trivial. ∎

Now we have for any $q\in Q$ an $R$-module isomorphism $j^{q}\colon
Z_{1}(X^{q})\to C_{1}(X^{q},T^{q})$. The next proposition states that the
family $j=(j^{q})_{q\in Q}$ of these isomorphisms is actually a persistent
homomorphism from $Z_{1}(X)$ to $C_{1}(X,T)$.

######  Proposition 21.

Suppose there exists a filtration $T=(T^{q})_{q\in Q}$ of simplicial complexes
such that $T^{q}$ is a spanning tree of $X^{q}$ for each $q\in Q$. The
persistent homomorphism $j\colon Z_{1}(X)\to C_{1}(X,T)$ that is for every
$q\in Q$ defined by

$j^{q}\colon Z_{1}(X^{q})\to C_{1}(X^{q},T^{q})\text{,}\qquad z\mapsto
z+C_{1}(T^{q})\text{,}$

is an isomorphism of persistence modules.

###### Proof.

The assertion is equivalent to the commutativity of the diagram

${Z_{1}(X^{q})}$${C_{1}(X^{q},T^{q})}$${Z_{1}(X^{q^{\prime}})}$${C_{1}(X^{q^{\prime}},T^{q^{\prime}})}$$\scriptstyle{j^{q}}$$\scriptstyle{j^{q^{\prime}}}$

where the structure map of $Z_{1}(X)$ from $Z_{1}(X^{q})$ to
$Z_{1}(X^{q^{\prime}})$ is the canonical inclusion map. However, the
commutativity of the diagram follows immediately. ∎

######  Remark 22.

If $Q$ is totally ordered, we can always choose a subfiltration of spanning
trees.

Figure 4. A $3\times 3$-filtration of simplicial complexes without a
corresponding subfiltration of spanning trees in the sense of Proposition 21.

######  Example 23.

If the poset $Q$ is not total, the existence of a subfiltration of spanning
trees for any filtration over $Q$ is not guaranteed. A counterexample of such
filtration over $\mathbb{N}^{2}$ is depicted in Figure 4. This failure of
existence is also reflected in the fact that the decomposition structure of
persistence modules over non-totally ordered sets is not trivial [CZ09].

######  Definition 24 (Cofiltrations of spanning trees).

Let $(T^{q})_{q\in Q}$ be a family of simplicial complexes such that $T^{q}$
is a spanning tree of $X^{q}$ for any $q\in Q$. The family $(T^{q})_{q\in Q}$
is a _cofiltration of spanning trees_ of $X$ if $X^{q}\setminus T^{q}\subseteq
X^{q^{\prime}}\setminus T^{q^{\prime}}$ set-theoretically for any pair $q\leq
q^{\prime}$ in $Q$.

A similar but more general notion of cofiltrations was introduced in [PR22].

######  Lemma 25.

Let $(X,\mathord{\preceq})$ be an ordered simplicial complex and $A$ a
subcomplex of $X$. Interpret $A$ as an ordered simplicial complex, with
ordering given by the restriction of $\mathord{\preceq}$. For order-minimal
spanning trees $T_{A}$ and $T_{X}$ of $A$ and $Y$, respectively, it holds
$A\setminus T_{A}\subseteq X\setminus T_{X}$ set-theoretically.

###### Proof.

Let $e\in A\setminus T_{A}$. Then, we find
$c=\sum_{i=1}^{k}\lambda_{i}e_{i}\in C_{1}(T_{A})$ such that the chain $z=c-e$
is a cycle in $A$. By Lemma 19, the leading simplex of $z$ must be contained
in $A\setminus T_{A}$, and the only possibility is $\operatorname{LS}(z)=e$.
Since $T_{X}$ is an order-minimal spanning tree of $X$, it further follows
that $\operatorname{LS}(z)\in X\setminus T_{X}$. Hence, we have $e\in
X\setminus T_{X}$. ∎

Our main result in this section is that we can use the above lemma to obtain,
for every filtration of finite simplicial complexes over a finite poset, a
corresponding cofiltration of spanning trees, cf. Theorem 2.

######  Theorem 26.

Let $X=(X^{q})_{q\in Q}$ be a filtration of finite simplicial complexes. Then,
there exists a cofiltration of spanning trees $T$ of $X$, i.e. a family
$T=(T^{q})_{q\in Q}$ of simplicial complexes with $X^{q}\setminus
T^{q}\subseteq X^{q^{\prime}}\setminus T^{q^{\prime}}$ for any pair $q\leq
q^{\prime}\in Q$.

###### Proof.

We choose for any $q\in Q$ an order-minimal spanning tree $T^{q}$ of $X^{q}$,
which exists since $X^{q}$ is finite. Let $q\leq q^{\prime}\in Q$. We know by
assumption that $X^{q}$ is a subcomplex of $X^{q^{\prime}}$. Thus, by Lemma
25, we have $X^{q}\setminus T^{q}\subseteq X^{q^{\prime}}\setminus
T^{q^{\prime}}$. Hence, $(T^{q})_{q\in Q}$ is a cofiltration of spanning trees
of $(X^{q})_{q\in Q}$. ∎

Lastly, we show that we can extend the above result in a functorial fashion
for order- and dimension-preserving simplicial maps. A morphism of simplicial
complexes $f\colon X\to Y$ is called _dimension-preserving_ if
$\dim\sigma=\dim f(\sigma)$. Let $\operatorname{Simp}_{\mathrm{ord},\dim}$
denote the subcategory of ordered simplicial complexes with dimension- and
order-preserving simplicial maps as morphisms.

######  Definition 27.

Let $A\subseteq X$ be a pair of simplicial complexes and $n\in\mathbb{N}$. The
_$n$ -difference of $X$ and $A$_ is the set

$X\boxminus_{n}A=X_{0}\cup\dotsc\cup X_{n-1}\cup(X_{n}\setminus
A_{n})\text{.}$

It is immediately clear that $X\boxminus_{n}A$ is again a simplicial complex
contained in $X$. Further, we note that the $(n-1)$-skeleton of
$X\boxminus_{n}A$ coincides with the $(n-1)$-skeleton of $X$.

######  Theorem 28.

Let $f\colon(X,\mathord{\leq}_{X})\to(Y,\mathord{\leq}_{Y})$ be an order- and
dimension-preserving simplicial map. Suppose that $T_{X}$ is an order-minimal
spanning tree of $X$ and $T_{Y}$ is an order-minimal spanning tree of $Y$.
Then, $f(X\boxminus_{1}T_{X})\subseteq Y\boxminus_{1}T_{Y}$.

Hence, $f$ restricts to a simplicial map $X\boxminus_{1}T_{X}\to
Y\boxminus_{1}T_{Y}$.

###### Proof.

Let $\lambda_{1},\dotsc,\lambda_{k}\neq 0$ and $\sigma_{1},\dotsc,\sigma_{k}$
be distinct $1$-simplices in $X$ satisfying
$\sigma_{1}\preceq_{X}\dotsb\preceq_{X}\sigma_{k}$. That is, for the chain
$c=\lambda_{1}\sigma_{1}+\dotsb+\lambda_{k}\sigma_{k}$ we have
$\operatorname{LS}(c)=\sigma_{k}$.

Since $f$ is order-preserving, it follows
$f(\sigma_{1})\preceq_{Y}\dotsb\preceq_{Y}f(\sigma_{k})$. Moreover, since $f$
is dimension-preserving, every simplex $f(\sigma_{i})$ is an $1$-simplex for
$i\in\\{1,\dotsc,k\\}$.

Let $f_{\sharp}\colon C_{1}(X)\to C_{1}(Y)$ be the associated homomorphism of
chain modules of $f$. Therefore, we have
$f_{\sharp}(c)=\lambda_{1}f(\sigma_{1})+\dotsb+\lambda_{k}f(\sigma_{k})$.
Hence,
$\operatorname{LS}(f_{\sharp}(c))=f(\sigma_{k})=f(\operatorname{LS}(c))$.

Now, let $\sigma$ be an $1$-simplex in $X$ but not in $T_{X}$. Then, we choose
a chain $c$ in $T_{X}$ such that $c-\sigma\in Z_{1}(X)$. Since the spanning
tree $T_{X}$ is order-minimal, we have $\operatorname{LS}(c-\sigma)\in
X\setminus T_{X}$. Thus, it holds $\operatorname{LS}(c-\sigma)=\sigma$.

By the considerations above, we have
$\operatorname{LS}(f_{\sharp}(c-\sigma))=f(\operatorname{LS}(c-\sigma))=f(\sigma)$.
Since $T_{Y}$ is also order-minimal and $f_{\sharp}(c-\sigma)$ is by
definition a non-zero $1$-cycle in $Y$, it follows
$\operatorname{LS}(f_{\sharp}(c-\sigma))\in Y\setminus T_{Y}$. Hence,
$f(\sigma)\in Y\boxminus_{1}T_{Y}$, which proves the assertion. ∎

######  Remark 29.

Every monomorphism of simplicial complexes is necessarily dimension-
preserving. Hence, if $f\colon(X,\mathord{\leq}_{X})\to(Y,\mathord{\leq}_{Y})$
is a monomorphism, it follows $f(X\setminus T_{X})\subseteq Y\setminus T_{Y}$.

######  Example 30.

Let $X$ be a wedge of two triangles and $Y$ a single triangle. A simplicial
map from $X$ into $Y$ that sends each triangle in $X$ onto the triangle $Y$ is
dimension-preserving but not injective.

######  Corollary 31.

There is an endofunctor
$\tau_{1}\colon\operatorname{Simp}_{\mathrm{ord},\dim}\to\operatorname{Simp}_{\mathrm{ord},\dim}$
defined as follows: For $(X,\mathord{\preceq}_{X})$ an ordered simplicial
complex, let $T_{X}$ be the unique order-minimal spanning tree of $X$. Then,
define
$\tau_{1}(X,\mathord{\preceq}_{X})=(X\boxminus_{1}T_{X},\mathord{\preceq}_{X})$.

For a morphism $f\colon(X,\mathord{\preceq}_{X})\to(Y,\mathord{\preceq}_{Y})$
in $\operatorname{Simp}_{\mathrm{ord},\dim}$, let $T_{Y}$ be the order-minimal
spanning tree of $Y$. Define the morphism $\tau_{1}(f)\colon
X\boxminus_{1}T_{X}\to Y\boxminus_{1}T_{Y}$ to be the underlying simplicial
map of $f$ formally restricted to $X\boxminus_{1}T_{X}$, interpreted as a
morphism in $\operatorname{Simp}_{\mathrm{ord},\dim}$.

In particular, this functor is faithful but not full in general.

######  Remark 32.

Let $A\subseteq X$ be a simplicial pair and let $i\colon A\to X$ denote the
canonical inclusion map. Further, we assume that $X$ is endowed with a
simplicial order $\preceq_{X}$ and we endow $A$ with the restriction of
$\preceq_{X}$ as simplicial order. Under this assumption, we see that $i$ is
an order-preserving simplicial map $(A,\preceq_{X})\to(X,\preceq_{X})$.

Moreover, it follows from Remark 29 that $i$ is also dimension-preserving.
Thus, Corollary 31 implies that there is an order- and dimension-preserving
simplicial map
$\tau_{1}(i)\colon(A\boxminus_{1}T_{A},\mathord{\preceq}_{X})\to(X\boxminus_{1}T_{X},\mathord{\preceq}_{X})$,
where $T_{A}$ is the order-minimal spanning tree of $A$ and $T_{X}$ is the
order-minimal spanning tree of $X$.

From this result, it directly follows that $A_{1}\setminus T_{A}$ is a subset
of $X_{1}\setminus T_{X}$. Hence, Corollary 31 is a vast generalization of
Lemma 25 and Theorem 26.

##  5\. $R$-spans of persistence modules

Let $R$ be a principal ideal domain and $Q=(Q,\mathord{\leq})$ a poset. Denote
by $U_{0}$ the forgetful functor $\operatorname{Mod}_{R}\to\operatorname{Set}$
sending an $R$-module to its underlying set. We consider the forgetful functor

$\displaystyle U_{Q}\colon\operatorname{Mod}_{R}^{Q}$
$\displaystyle\longrightarrow\operatorname{Set}^{Q}\text{,}$ $\displaystyle M$
$\displaystyle\longmapsto U_{0}\circ M\text{.}$

The functor $U$ sending an $R$-module to its underlying set is right-adjoint
to the $R$-span functor $R\colon\operatorname{Set}\to\operatorname{Mod}_{R}$,
which for any set $B$ assigns the free $R$-module $R(B)$ with basis $B$ to the
set $B$. We now show that the adjunction $U\dashv R$ extends to an adjunction
of $U_{Q}$.

Let
$\eta_{X,M}\colon\operatorname{Hom}_{\operatorname{Mod}_{R}}(R(X),M)\to\operatorname{Hom}_{\operatorname{Set}}(X,U(M))$
be the natural transformation in $X\in\operatorname{Set}^{Q}$ and
$M\in\operatorname{Mod}_{R}^{Q}$ associated to the adjunction. We consider the
functor $R_{Q}\colon\operatorname{Set}^{Q}\to\operatorname{Mod}_{R}^{Q}$
defined on a persistent set $X$ by $R_{Q}(X)=R\circ X$, and we claim that
$R_{Q}$ is the left adjoint of $U_{Q}$.

For any persistent set $X$ and persistence module $M$ we define the map

$\displaystyle\theta_{X,M}\colon\operatorname{Hom}_{\operatorname{Mod}_{R}^{Q}}(R_{Q}(X),M)$
$\displaystyle\longrightarrow\operatorname{Hom}_{\operatorname{Set}^{Q}}(X,U_{Q}(M))\text{,}$
$\displaystyle(\alpha_{q})_{q\in Q}$
$\displaystyle\longmapsto(\eta_{X(q),M(q)}(\alpha_{q}))_{q\in Q}\text{.}$

It is easy to see that this is natural in $X\in\operatorname{Set}^{Q}$ and
$M\in\operatorname{Mod}_{R}^{Q}$. Moreover, $\theta_{X,M}$ is an isomorphism
with inverse given by the map

$\displaystyle\theta_{X,M}^{-1}\colon\operatorname{Hom}_{\operatorname{Set}^{Q}}(X,U_{Q}(M))$
$\displaystyle\longrightarrow\operatorname{Hom}_{\operatorname{Mod}_{R}^{Q}}(R_{Q}(X),M)\text{,}$
$\displaystyle(\beta_{q})_{q\in Q}$
$\displaystyle\longmapsto(\eta_{X(q),M(q)}^{-1}(\beta_{q}))_{q\in Q}\text{.}$

The functor $R_{Q}\colon\operatorname{Set}^{Q}\to\operatorname{Mod}_{R}^{Q}$
defined in this context is called the _persistent $R$-span functor_. These
considerations prove the following lemma.

######  Lemma 33.

The forgetful functor
$U_{Q}\colon\operatorname{Mod}_{R}^{Q}\to\operatorname{Set}^{Q}$ admits a
left-adjoint functor, namely $R_{Q}$. In particular, $U_{Q}$ preserves limits,
products, and finite coproducts and, dually, $R_{Q}$ preserves colimits,
coproducts, and finite products [Mac78].

######  Definition 34.

Let $\mathcal{B}$ be a set consisting of persistent sets. A persistence module
$M\colon Q\to\operatorname{Mod}_{R}$ is _$\mathcal{B}$ -decomposable_ if there
exists a family $(B_{i})_{i\in I}$ of elements of $\mathcal{B}$ such that

$M\cong\bigoplus_{i\in I}\mathop{R_{Q}}(B_{i})\text{.}$

Specifically, we consider the family $\mathcal{U}$ of principal persistent
sets, defined as follows. A subset $U$ of the poset $Q$ is an _upper set_
(also called an _order coideal_ in order theory) if for all $q\in U$ and
$q^{\prime}\in Q$ with $q\leq q^{\prime}$ it follows $q^{\prime}\in U$. Given
such upper set $U\subseteq Q$, the associated _principal persistent set_ is
the persistent set $\mathrm{pt}[U]\colon Q\to\operatorname{Set}$ with
$\mathrm{pt}[U](q)=\\{\ast\\}$ if $q\in U$ and $\mathrm{pt}[U](q)=\emptyset$
otherwise, and $\mathrm{pt}[U](q\leq q^{\prime})$ the identity map unless
$q\notin U$.

With these notions, we define

$\mathcal{U}=\mathcal{U}_{Q}=\\{\mathrm{pt}[U]\mid\text{$U$ an upper subset of
$Q$}\\}\text{.}$

If a persistence module $M\colon Q\to\operatorname{Mod}_{R}$ is
$\mathcal{U}$-decomposable, we say that $M$ is _upper set decomposable_ (USD).
That is, $M$ is upper set decomposable if and only if there exists a family
$(U_{i})_{i\in I}$ of upper subsets of $Q$ such that $M=\bigoplus_{i\in
I}R[U_{i}]$. Moreover, if $U$ is an upper set, the module
$R[U]=R_{Q}(\mathrm{pt}[U])$ is the _upper set module_ of $U$.

######  Proposition 35.

Let $B\colon Q\to\operatorname{Set}$ a functor. For $q\in Q$, denote by
$\iota_{q}\colon B(q)\to\operatorname{colim}B$ the colimit injection. Then the
following assertions are equivalent:

  1. (i)

For every $q\in Q$, the map $\iota_{q}$ is injective.

  2. (ii)

The persistence module $\mathop{R_{Q}}B$ is upper set decomposable.

  3. (iii)

For every $q\in Q$, the colimit injection
$\iota^{\prime}_{q}\colon\mathop{R_{Q}}B(q)\to\operatorname{colim}\mathop{R_{Q}}B$
is a monomorphism.

###### Proof.

(i) $\implies$ (ii): We define the persistent set $B^{\prime}\colon
Q\to\operatorname{Set}$ as follows: For $q\in Q$, let
$B^{\prime}(q)=\iota_{q}(B(q))$.

Then, for an ordered pair $q\leq q^{\prime}$ in $Q$ and every $x\in
B^{\prime}(q)$ we have $x\in B^{\prime}(q^{\prime})$ since
$\iota_{q}=\iota_{q^{\prime}}\circ B(q\leq q^{\prime})$ holds. Therefore, the
map $B^{\prime}(q\leq
q^{\prime})\colon\iota_{q}(B(q))\to\iota_{q^{\prime}}(B(q^{\prime}))$ can be
chosen as the inclusion.

Moreover, $B^{\prime}$ is isomorphic to $B$ by construction. For every $q\in
Q$, the map

$B(q)\to B^{\prime}(q)\text{,}\qquad b\mapsto\iota_{q}(b)\text{,}$

is bijective by the injectivity of $\iota_{q}$. Thus, $B^{\prime}\cong B$.

Further, $B^{\prime}$ is upper set decomposable since we can decompose
$B^{\prime}$ into the coproduct of $\mathrm{pt}[U_{x}]$ over any
$x\in\operatorname{colim}B$, where $U_{x}=\\{q\in Q\mid x\in B^{\prime}(q)\\}$
is an upper set of $Q$ by construction.

(ii) $\implies$ (iii): Let $(U_{i})_{i\in I}$ be a family of upper sets of $Q$
such that $\mathop{R_{Q}}B=\bigoplus_{i\in I}R[U_{i}]$. Since every upper set
module $R[U_{i}]$ admits monic colimit injections
$R[U_{i}](q)\to\operatorname{colim}R[U_{i}]$ for any $q\in Q$, it follows that
$\mathop{R_{Q}}B$ also admits monic colimit injections as claimed.

(iii) $\implies$ (ii): Suppose that there exists some $q\in Q$ such that
$\iota_{q}$ is not injective. Then, there are $b,b^{\prime}\in B(q)$ such that
$b\neq b^{\prime}$ and $\iota_{q}(b)=\iota_{q}(b^{\prime})$. Thus,
$b-b^{\prime}\in R_{Q}B(q)$ is a non-zero element of the kernel of
$\iota^{\prime}_{q}$ since $R_{Q}$ preserves colimits. Hence,
$\iota^{\prime}_{q}$ is not injective and thus not a monomorphism. ∎

######  Remark 36.

Results similar to Proposition 35 were established in [CSV17]. A functor
$B\colon Q\to\operatorname{Mod}_{R}$ is a _multifiltration_ if the structure
maps of $B$ are monomorphisms. For the poset $Q=\mathbb{N}^{d}$ (or more
generally for $Q$ a lattice), the conditions of Proposition 35 are equivalent
to the condition that the functor $B$ is a multifiltration, cf. [CSV17,
Proposition 3.3]. Moreover, any non-trivial multifiltration $B$ is uniquely
decomposable into indecomposables and the indecomposable multifiltrations over
$\mathbb{N}^{d}$ are precisely the upper set modules [CSV17, Proposition 3.1,
Corollary 3.2]. In this sense, Proposition 35 is a generalization of [CSV17,
Proposition 3.1].

######  Example 37.

Let $U=\\{(a,b)\in\mathbb{Z}^{2}\mid a+b\geq 0\\}$. This is clearly an upper
set of $\mathbb{Z}^{2}$. However, the upper set module $R[U]$ is not finitely
generated, since we need a generator in each $(a,-a)$ for $a\in\mathbb{Z}$ to
cover $U$ by principal upper sets of $\mathbb{Z}^{2}$.

##  6\. Generating persistent first homology

Let $X=(X^{q})_{q\in Q}$ be a $Q$-filtration of simplicial complexes and
$(T^{q})_{q\in Q}$ a filtration of spanning trees of $X$. Then, we have seen
in Proposition 21 that we can describe $Z_{1}(X)$ as the quotient persistence
module $C_{1}(X,T)=C_{1}(X)/C_{1}(T)$.

Since $C_{1}(X,T)$ has monomorphic colimit injections, it follows that
$Z_{1}(X)$ is, in this case, upper set decomposable. This results in a
decomposition $Z_{1}(X)\cong\bigoplus_{i\in I}R[U_{i}]$ for a family
$(U_{i})_{i\in I}$ of upper sets of $Q$.

All of this depends on the requirement that there exists a filtration of
spanning trees for $(X^{q})_{q\in Q}$. We have seen in Example 23 that this is
not always the case. The existence of such filtration of spanning trees fails
even for a $3\times 3$ sublattice of $\mathbb{N}^{2}$.

As an alternative for the general case, we propose in this section a technique
to determine upper sets $(U_{i})_{i\in I}$ together with an epimorphism
$\bigoplus_{i\in I}R[U_{i}]\to Z_{1}(X)$ by exploiting the properties of
order-minimal spanning trees, namely Theorem 26.

We assume that the poset $Q$ and the simplicial complex $\bigcup_{q\in
Q}X^{q}$ are finite and endowed with a simplicial order $\preceq$. Then, for
every $q\in Q$ we interpret the subcomplex $X^{q}$ as the ordered simplicial
complex $(X^{q},\mathord{\preceq})$, which naturally admits an injective
order-preserving simplicial map into $(X,\mathord{\preceq})$. Using the
simplicial order on $X^{q}$, we choose the uniquely determined order-minimal
spanning tree $T^{q}$ of $(X^{q},\mathord{\preceq})$. Since $X^{q}$ is a
finite simplicial complex, the existence of $T^{q}$ is guaranteed.

Then, it follows from Theorem 26 that $X^{q}\boxminus_{1}T^{q}$ is a
subcomplex of $X^{q^{\prime}}\boxminus_{1}T^{q^{\prime}}$. Moreover, when
$T^{\infty}$ is the order-minimal spanning tree of $X^{\infty}=\bigcup_{q\in
Q}X^{q}$ endowed with $\preceq$, we also have
$X^{q}\boxminus_{1}T^{q}\subseteq X^{\infty}\boxminus_{1}T^{\infty}$ for any
$q\in Q$.

Let $\sigma\in X^{\infty}\boxminus_{1}T^{\infty}$ be a 1-simplex. We shall
write $\operatorname{Supp}_{X\boxminus_{1}T}(\sigma)=\\{q\in Q\mid\sigma\in
X^{q}\boxminus_{1}T^{q}\\}$. For every $q\in Q$ such that
$\sigma\in\operatorname{Supp}_{X\boxminus_{1}T}(\sigma)$ we consider the
$R$-module isomorphism $j^{q}\colon Z_{1}(X^{q})\to C_{1}(X^{q},T^{q})$. We
define the persistent set $B_{\sigma}=(B_{\sigma}^{q})_{q\in Q}$ by
$B_{\sigma}^{q}=\\{j^{-1}_{q^{\prime}}(\sigma)\mid
q^{\prime}\in(-\infty,\sigma]\cap\operatorname{Supp}_{X\boxminus_{1}T}(\sigma)\\}$
and structure maps given by inclusions.

Finally, let $M$ be the $R$-span of the persistent set
$\coprod_{\sigma}B_{\sigma}$, i.e.
$M=R_{Q}(\coprod_{\sigma}B_{\sigma})\cong\bigoplus_{\sigma}R_{Q}B_{\sigma}$
where $\sigma$ ranges over each $1$-simplex in
$X^{\infty}\boxminus_{1}T^{\infty}$.

######  Theorem 38.

The module $M$ as constructed above is upper set decomposable and admits an
epimorphism onto $Z_{1}(X)$.

###### Proof.

The persistent set $B=(B^{q})_{q\in Q}=\coprod_{\sigma}B_{\sigma}$ is given by

$B^{q}=\\{(\sigma,j^{-1}_{q^{\prime}}(\sigma))\mid\sigma\in
X^{q}\boxminus_{1}T^{q},\
q^{\prime}\in(-\infty,\sigma]\cap\operatorname{Supp}_{X\boxminus_{1}T}(\sigma)\\}\text{.}$

We define the persistent map $\varphi=(\varphi^{q})_{q\in Q}\colon
B\to\mathop{U_{Q}}Z_{1}(X)$ as follows: For $(\sigma,z)\in B^{q}$, $z$ is a
cycle of $X^{q^{\prime}}$ for some $q^{\prime}\in Q$ satisfying
$q^{\prime}\leq q$. Thus, $z$ is a cycle in $X^{q}$, and we define
$\varphi^{q}(\sigma,z)=z\in Z_{1}(X^{q})$.

We have a basis
$\mathcal{B}_{q}=\\{j_{q}^{-1}(\sigma+C_{1}(T^{q}))\mid\sigma\in
X^{q}\boxminus_{1}T^{q}\mid|\sigma|=2\\}$ of $Z_{1}(X^{q})$. By construction,
the image of $\varphi^{q}$ contains $\mathcal{B}_{q}$. Thus, the uniquely
determined homomorphism $\tilde{\varphi}^{q}\colon RB\to Z_{1}(X^{q})$ is an
epimorphism.

It follows that the uniquely determined persistent homomorphism $\varphi\colon
R_{Q}\to Z_{1}(X)$ is an epimorphism in each component. Hence, $\varphi$ is an
epimorphism in the category of persistence modules. ∎

##  7\. Higher-dimensional spanning complexes

In the previous sections, we discussed spanning trees of simplicial complexes,
which allow us to determine the $1$-dimensional cycle modules of simplicial
complexes by inspecting $1$-dimensional relative chain modules. An open
question is whether there is a similar, easily computable type of subcomplex
such that for a dimension $n\in\mathbb{N}$ we can determine $n$-dimensional
cycle modules in a similar manner by inspecting $n$-dimensional relative chain
modules.

As a first step towards an answer of this question, we consider in this
section a generalization of spanning trees to higher dimensions by merely
generalizing Definition 5.

######  Definition 39.

Let $X$ be a simplicial complex and $n>0$. A subcomplex $A$ of $X$ is an _$n$
-spanning complex_ of $X$ if the following conditions hold:

  1. (i)

$\operatorname{skel}_{n-1}(A)=\operatorname{skel}_{n-1}(X)$.

  2. (ii)

The boundary homomorphism $\partial_{n}\colon C_{n}(A)\to C_{n-1}(A)$ is
injective.

  3. (iii)

$B_{n-1}(A)=B_{n-1}(X)$.

This definition directly generalizes the notion of a spanning tree defined in
Definition 5 by replacing the dimensions by an fixed but arbitrary
$n\in\mathbb{N}$.

######  Remark 40.

For $n=1$, every spanning tree is an $n$-spanning complex.

######  Proposition 41.

Let $A$ be an $n$-spanning complex of $X$. Then the homomorphism

$\displaystyle j\colon Z_{n}(A)$ $\displaystyle\longrightarrow
C_{n}(X,A)\text{,}$ $\displaystyle z$ $\displaystyle\longmapsto
z+C_{n}(A)\text{,}$

is an isomorphism of $R$-modules.

###### Proof.

The proof is analogous to Theorem 7. The injectivity of $j$ follows from
$Z_{n}(A)=0$ and the surjectivity of $j$ follows from $B_{n-1}(X)=B_{n-1}(A)$
together with $Z_{n}(A)=0$. ∎

######  Theorem 42 (Existence of $n$-spanning complexes).

For any simplicial complex $X$ and any $n\in\mathbb{N}$ there exists a
subcomplex $A$ such that $Z_{n}(A)=0$ and $B_{n-1}(A)=B_{n-1}(X)$, i.e. $X$
admits an $n$-spanning complex.

###### Proof.

Let $\mathcal{A}_{X}=\\{A\subseteq X\mid\text{$A$ is a subcomplex s.t.\
$Z_{n}(A)=0$}\\}$. For every subset
$\mathcal{A}^{\prime}\subseteq\mathcal{A}_{X}$ that is totally ordered by set
inclusion, we consider the subcomplex
$\bigcup\mathcal{A}=\bigcup_{A\in\mathcal{A}^{\prime}}A$ of $X$. We have
$Z_{n}(\bigcup\mathcal{A}^{\prime})=0$: Let $z$ be an $n$-chain in
$\bigcup\mathcal{A}^{\prime}$ such that $\partial_{n}z=0$. Then, there are
non-zero $\lambda_{1},\dotsc,\lambda_{k}\in R$ and distinct $n$-simplices
$\sigma_{1},\dotsc,\sigma_{k}$ in $\bigcup\mathcal{A}^{\prime}$ such that
$z=\lambda_{1}\sigma_{1}+\dotsb+\lambda_{k}\sigma_{k}$. Then, we can choose
$A_{1},\dotsc,A_{k}\in\mathcal{A}^{\prime}$ such that $\sigma_{i}\in A_{i}$
for $i\in\\{1,\dotsc,k\\}$. Since $\mathcal{A}^{\prime}$ is totally ordered by
set inclusion there exists an $i_{0}\in\\{1,\dotsc,k\\}$ such that
$A_{i}\subseteq A_{i_{0}}$ for all $i\in\\{1,\dotsc,k\\}$. Thus, $z$ is
actually an $n$-chain in $B_{i_{0}}\in\mathcal{A}^{\prime}$. Since $B_{i_{0}}$
satisfies $Z_{1}(B_{i_{0}})=0$ by assumption, $z=0$.

Therefore, every totally ordered subset of $\mathcal{A}_{X}$ admits an upper
bound in $\mathcal{A}_{X}$. It follows from Zorn’s lemma that there exists
$A\in\mathcal{A}_{X}$ that is maximal w.r.t. set inclusion.

It remains to prove that such maximal $A$ in $\mathcal{A}_{X}$ satisfies
$B_{n-1}(A)=B_{n-1}(X)$, i.e. $B_{n-1}(X)\subseteq B_{n-1}(A)$. In particular,
it suffices to prove that for every $n$-simplex $\sigma$ in $X$ there exists
an $n$-chain $c$ in $A$ such that $\partial_{n}c=\partial_{n}\sigma$. Let
$\sigma$ be an $n$-simplex in $X$. If $\sigma\in A$, then trivially
$\partial_{n}\sigma\in B_{n-1}(A)$. Thus, we consider only the case that
$\sigma$ is not in $A$. Then, we can consider the subcomplex
$A^{\prime}=A\cup\\{\sigma\\}$ of $X$. Since $A$ is maximal by construction in
$\mathcal{A}_{X}$ and $A\subsetneq A^{\prime}$, it follows that $A^{\prime}$
cannot be contained in $\mathcal{A}_{X}$. That is, $Z_{n}(A^{\prime})$ cannot
be trivial.

Therefore, there exists an $n$-cycle $z=\mu\sigma+c$ in $A^{\prime}$ with
$\mu\in\\{1,-1\\}$ and $c$ an $n$-chain in $A$. We can assume without loss of
generality that $\mu=1$. But then we have $\partial_{n}\sigma=\partial_{n}c\in
B_{n-1}(A)$. Hence, $B_{n-1}(X)\subseteq B_{n-1}(A)$. ∎

## References

  * [BC20] Magnus Bakke Botnan and William Crawley-Boevey  “Decomposition of persistence modules”  In _Proceedings of the American Mathematical Society_ 148.11, 2020, pp. 4581–4596  DOI: 10.1090/proc/14790
  * [BM08] J. Bondy and U… Murty  “Graph theory” 244, Graduate Texts in Mathematics  Springer Berlin, 2008
  * [BS14] Peter Bubenik and Jonathan A. Scott  “Categorification of persistent homology”  In _Discrete & Computational Geometry_ 51.3, 2014, pp. 600–627  DOI: 10.1007/s00454-014-9573-x
  * [Car09] Gunnar Carlsson  “Topology and data”  In _Bulletin of the American Mathematical Society. New Series_ 46.2, 2009, pp. 255–308  DOI: 10.1090/S0273-0979-09-01249-X
  * [CLO05] David A. Cox, John Little and Donal O’Shea  “Using algebraic geometry” 185, Graduate Texts in Mathematics  Springer New York, 2005  DOI: 10.1007/b138611
  * [Cra15] William Crawley-Boevey  “Decomposition of pointwise finite-dimensional persistence modules.”  In _Journal of Algebra and its Applications_ 14.5, 2015, pp. 8  DOI: 10.1142/S0219498815500668
  * [CSV17] Wojciech Chachólski, Martina Scolamiero and Francesco Vaccarino  “Combinatorial presentation of multidimensional persistent homology”  In _Journal of Pure and Applied Algebra_ 221.5, 2017, pp. 1055–1075  DOI: 10.1016/j.jpaa.2016.09.001
  * [CSZ10] Gunnar Carlsson, Gurjeet Singh and Afra J. Zomorodian  “Computing multidimensional persistence”  In _Journal of Computational Geometry_ 1.1, 2010, pp. 72–100  DOI: 10.20382/jocg.v1i1a6
  * [CZ09] Gunnar Carlsson and Afra Zomorodian  “The theory of multidimensional persistence”  In _Discrete & Computational Geometry_ 42.1, 2009, pp. 71–93  DOI: 10.1007/s00454-009-9176-0
  * [CZCG05] Gunnar Carlsson, Afra Zomorodian, Anne Collins and Leonidas J. Guibas  “Persistence barcodes for shapes”  In _International Journal of Shape Modeling_ 11.2, 2005, pp. 149–187  DOI: 10.1142/S0218654305000761
  * [Die17] Reinhard Diestel  “Graph theory” 173, Grad. Texts Math.  Springer Berlin, 2017  DOI: 10.1007/978-3-662-53622-3
  * [DX22] Tamal K. Dey and Cheng Xin  “Generalized persistence algorithm for decomposing multiparameter persistence modules”  In _J. Appl. Comput. Topol._ 6.3, 2022, pp. 271–322  DOI: 10.1007/s41468-022-00087-5
  * [EH10] Herbert Edelsbrunner and John L. Harer  “Computational topology. An introduction”  American Mathematical Society, 2010
  * [ELZ02] Herbert Edelsbrunner, David Letscher and Afra Zomorodian  “Topological persistence and simplification”  In _Discrete & Computational Geometry_ 28.4, 2002, pp. 511–533  DOI: 10.1007/s00454-002-2885-2
  * [Hat15] Allen Hatcher  “Algebraic topology”  Cambridge University Press, 2015
  * [KM21] Woojin Kim and Facundo Mémoli  “Generalized persistence diagrams for persistence modules over posets”  In _Journal of Applied and Computational Topology_ 5.4, 2021, pp. 533–581  DOI: 10.1007/s41468-021-00075-1
  * [Koz20] Dmitry N. Kozlov  “Organized collapse. An introduction to discrete Morse theory” 207, Graduate Studies in Mathematics  American Mathematical Society (AMS), 2020  DOI: 10.1090/gsm/207
  * [Lov77] László Lovász  “A homology theory for spanning trees of a graph”  In _Acta Mathematica Academiae Scientiarum Hungaricae_ 30, 1977, pp. 241–251  DOI: 10.1007/BF01896190
  * [LS98] Roberto La Scala and Michael Stillman  “Strategies for computing minimal free resolutions”  In _Journal of Symbolic Computation_ 26.4, 1998, pp. 409–431  DOI: 10.1006/jsco.1998.0221
  * [LW15] Michael Lesnick and Matthew Wright  “Interactive Visualization of 2-D Persistence Modules”, 2015  arXiv:1512.00180 [math.AT]
  * [LW22] Michael Lesnick and Matthew Wright  “Computing minimal presentations and bigraded Betti numbers of 2-parameter persistent homology”  In _SIAM Journal on Applied Algebra and Geometry_ 6.2, 2022, pp. 267–298  DOI: 10.1137/20M1388425
  * [Mac78] Saunders Mac Lane  “Categories for the working mathematician” 5, Graduate Texts in Mathematics  Springer New York, 1978
  * [Mil20] Ezra Miller  “Homological algebra of modules over posets”, 2020  arXiv:2008.00063v2 [math.AT]
  * [MS05] Ezra Miller and Bernd Sturmfels  “Combinatorial commutative algebra” 227, Graduate Texts in Mathematics  Springer New York, 2005
  * [Pat18] Amit Patel  “Generalized persistence diagrams”  In _Journal of Applied and Computational Topology_ 1.3-4, 2018, pp. 397–419  DOI: 10.1007/s41468-018-0012-6
  * [PR22] Amit Patel and Tatum Rask  “Poincaré Duality for Generalized Persistence Diagrams of (co)Filtrations”, 2022  arXiv:2212.14610 [math.AT]
  * [Spa82] Edwin H. Spanier  “Algebraic topology”  Springer, 1982
  * [ZC05] Afra Zomorodian and Gunnar Carlsson  “Computing persistent homology”  In _Discrete & Computational Geometry_ 33.2, 2005, pp. 249–274  DOI: 10.1007/s00454-004-1146-y