The Depth Poset Under Transpositions in the Filter

Edelsbrunner, Herbert; Lipiński, Michał; Mrozek, Marian; Soriano-Trigueros, Manuel; Zimin, Fedor

doi:10.4230/LIPIcs.SoCG.2026.41

The Depth Poset Under Transpositions in the Filter

Herbert Edelsbrunner

Institute of Science and Technology Austria (ISTA), Klosterneuburg, Austria Michał Lipiński

Institute of Science and Technology Austria (ISTA), Klosterneuburg, Austria Marian Mrozek

Division of Computational Mathematics, Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland Manuel Soriano-Trigueros

Universidad de Sevilla, Spain
Institute of Science and Technology Austria (ISTA), Klosterneuburg, Austria Fedor Zimin

Institute of Science and Technology Austria (ISTA), Klosterneuburg, Austria

Abstract

The depth poset of a filtered Lefschetz complex reflects the dependencies between the cancellations of different shallow birth-death pairs. Using the fast algorithms for computing the depth poset in [9] and for updating the persistence diagram under transpositions in [7], we give a complete case analysis of how transpositions of cells in the filter affect the depth poset. In addition, we present statistics on the depth poset for random point data and its sensitivity to the transpositions that occur in random straight-line homotopies.

Keywords and phrases:

Algebraic topology, Lefschetz complexes, persistent homology, vines and vineyards, birth-death pairs, shallow pairs, relations, partial orders, transpositions

Funding:

Herbert Edelsbrunner: DFG Collaborative Research Center TRR 109, Austrian Science Fund (FWF), grant no. I 02979-N35

Michał Lipiński: European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 101034413

Marian Mrozek: Polish National Science Center under Opus Grant 2019/35/B/ST1/00874 and Opus Grant 2025/57/B/ST1/00550

Copyright and License:

© Herbert Edelsbrunner, Michał Lipiński, Marian Mrozek, Manuel Soriano-Trigueros,
and Fedor Zimin; licensed under Creative Commons License CC-BY 4.0

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Computational geometry

Related Version:

Previous Version: https://arxiv.org/abs/2511.21961

Acknowledgements:

The authors thank Jakub Leśkiewicz and Bartosz Furmanek for discussions that helped improve the paper.

DOI:

10.4230/LIPIcs.SoCG.2026.41

Event:

42nd International Symposium on Computational Geometry (SoCG 2026)

Editors:

Hee-Kap Ahn, Michael Hoffmann, and Amir Nayyeri

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The field of topology optimization aims at the design of shapes whose large- and small-scale connectivity is subject to modifications applied in order to satisfy constraints and optimize objective functions. The traditional approach is numerical and optimizes through repeated local improvement; see the text by Bendsøe [4] and the major revision by Bendsøe and Sigmund [5]. More recently, the methods of topological data analysis have matured and provide an alternative approach to this seasoned problem; see e.g. the “big steps” algorithm by Nigmetov and Morozov [19], which is closely related to the work presented in this paper. Specifically, we aim at exploring the space of shapes that relate to each other through the cancellation and interchange of the critical points of a function. This is naturally related to the simplification of functions and shapes, as studied in [1, 3, 11], but goes beyond this work by casting light on the space of possible simplifications.

An overarching goal for the presented work is to uncover the potential new tools from combinatorial dynamics pioneered by Forman [13, 12], offering discrete counterparts for classic concepts such as the Conley index, Morse decomposition, and connection matrix [16, 17, 18].

The primary technical prerequisites for our work are the depth poset of a filter on a complex, as introduced in [9], the well established concept of persistent homology; see the text by Edelsbrunner and Harer [10], and the vineyard algorithm for computing persistence along a parametrized family of functions, as originally described in [7]. The depth poset collects all dependencies between cancellations of shallow birth-death pairs (formerly known as apparent pairs [2] and close pairs [8]) and thus provides a global yet discrete representation of the space of shapes reachable by sequences of such cancellations. We mention that shallow pairs appeared in other seemingly unrelated contexts, for example in fast adaptive sorting [20]. Our main contribution is the complete case analysis of how transpositions in the filter affect the depth poset. Working toward establishing the depth poset as a first class object, we also present statistics on the size and shape of this poset and its variation under transpositions.

Outline.

Section 2 explains the technical background needed for our results. Section 3 gives the complete case analysis of how a transposition in the filter affects the depth poset of the same. Section 4 presents statistical results that probe the depth poset and homotopies between them for random PL height functions on Delaunay mosaics of Poisson point processes.

2 Background

This section presents the background we need to study the relations and orders in which our results are couched. Besides standard material, we need concepts from persistent homology and its matrix reduction algorithms. We refer to [10] for more comprehensive background.

Relations.

We adapt the terminology from graph theory, in which a relation consists of (directed) arcs that connect nodes. Each arc goes from its source to its target, both of which are nodes. A (directed) path is a sequence of arcs such that the target of each arc is the source of the next arc, and it goes from the source of the first arc to the target of the last arc. It is a directed cycle if the target of the last arc is also the source of the first arc. The relation is acyclic if it has no directed cycle. Note however that an acyclic relation may have undirected cycles, such as two disjoint paths that connect the same two nodes.

An acyclic relation has a unique transitive closure, which is the possibly larger (acyclic) relation that has an arc from a source to a target whenever there is such a path. A partial order is an acyclic relation that is its own transitive closure, and in situations where we wish to emphasize the nodes rather than the arcs, we refer to it as a partially ordered set, or a poset, for short. Two nodes in a poset are comparable if there is an arc that connects them, and we write $a\leq b$ if $a$ is the source and $b$ is the target of the connecting arc. A total order is a partial order in which any two nodes are comparable. It is a linear extension of a partial order on the same nodes if $a\leq b$ in the partial order implies $a\leq b$ in the total order.

In this paper we work with Lefschetz complexes with coefficients in ${{\mathbb{Z}}}/2{{\mathbb{Z}}}$ for simplicity, which can be viewed as chain complexes with a fixed bases. In particular, they avoid the complications that come with concrete geometric descriptions of the cells. This type of complex was introduced first under the more modest name of a complex in the book by Lefschetz [15]. We borrow the below definition from [9].

Definition 2.1.

A Lefschetz complex with coefficients in ${{\mathbb{Z}}}/2{{\mathbb{Z}}}$ is a triplet $({{K}},\dim,{{\kappa}})$ , in which ${{K}}$ is a finite set of elements, called cells, $\dim\colon{{K}}\to{{\mathbb{Z}}}$ maps each cell to its dimension, and ${{\kappa}}\colon{{K}}\times{{K}}\to{{\mathbb{Z}}}/2{{\mathbb{Z}}}$ is the incidence map satisfying $\sum\nolimits_{y\in{{K}}}\kappa(z,y)\cdot\kappa(y,x)=0$ for all $z,x\in{{K}}$ and ${{\kappa}}(y,x)\neq 0$ only if $\dim{y}=\dim{x}+1$ . For simplicity, we write just $K$ for a Lefschetz complex assuming that $\dim$ and ${{\kappa}}$ are implied. If ${{\kappa}}(y,x)\neq 0$ , then we say that cell $x$ is a facet of $y$ and cell $y$ is a cofacet of $x$ , we denote this relation by $x\preceq y$ . The transitive closure of the facet relation forms a partial order on $K$ called the face relation.

An injective function on a complex, $f\colon K\to{{\mathbb{R}}}$ , that satisfies $f(a)<f(b)$ whenever $a\prec b$ is called a filter of $K$ . A total order in which $a$ precedes $b$ iff $f(a)<f(b)$ is then a linear extension of the face relation; see the left panel of Figure 1.

Figure 1: Upper left: a complex with four vertices, five edges, three triangles (

\alpha,\beta,\gamma

, in which

\alpha

and

\beta

have the same boundary), and one

3

-cell (

\Sigma

, which is sandwiched between

\alpha

and

\beta

). Lower left: the ordering implied by a filter, with birth-death pairs as indicated (see definition below). Right: the death and birth relations on the birth-death pairs as computed by Algorithms 1 and 2 below.

Persistent Homology and Transpositions.

Given a filter on a complex, $f\colon K\to{{\mathbb{R}}}$ , we construct the complex by adding one cell at a time following the implied order. After adding $i$ cells, we arrive at a subcomplex $K_{i}\subseteq K$ , and we refer to the resulting sequence of subcomplexes as a filtration of $K$ . Fixing a dimension, $p$ , and a coefficient field, e.g. ${{\mathbb{Z}}}/2{{\mathbb{Z}}}$ , we apply the degree- $p$ homology functor to each subcomplex and thus get a linear sequence of vector spaces connected by linear maps:

\displaystyle{\mbox{${\sf H}_{p}{({\emptyset})}$}}={{\sf H}_{p}{({K_{0}})}}\to% {{\sf H}_{p}{({K_{1}})}}\to\ldots\to{{\sf H}_{p}{({K_{n}})}}={{\sf H}_{p}{({K}% )}};

(1)

see e.g. [14] for the needed background in algebraic topology. Whenever the added cell has dimension $p$ , it either gives birth to a degree- $p$ homology class or it gives death to a degree- $(p-1)$ homology class. This is classic Morse theory, and the novelty in persistence is that for each death-giving $(p+1)$ -cell we find a unique birth-giving $p$ -cell whose class it ends. We call these the degree- $p$ birth-death pairs of $f$ , denoted ${{{\it BD}}_{p}{({f})}}$ . It is also possible that some birth-giving $p$ -cells do not get paired, and they reflect the degree- $p$ homology of $K$ . A convenient combinatorial representation of this information is the persistence diagram, denoted ${{\rm Dgm}_{p}{({f})}}$ , which maps $(a,b)\in{{{\it BD}}_{p}{({f})}}$ to the point $(f(a),f(b))\in{{\mathbb{R}}}^{2}$ .

An important property is the stability of the persistence diagram, originally proved in [6]. In a nutshell, it says that for two monotonic functions, $f,g\colon K\to{{\mathbb{R}}}$ , there is a bijection between ${{\rm Dgm}_{p}{({f})}}$ and ${{\rm Dgm}_{p}{({g})}}$ such that the maximum coordinate difference between corresponding points is bounded from above by the absolute maximum of $f(a)-g(a)$ over all cells $a\in K$ . This will be instrumental in the following construction.

Consider two filters, $f_{0},f_{1}\colon K\to{{\mathbb{R}}}$ , and the straight-line homotopy defined by $f_{\lambda}(a)=(1-\lambda)f_{0}(a)+\lambda f_{1}(a)$ for $0\leq\lambda\leq 1$ . These functions imply a $1$ -parameter family of persistence diagrams for each dimension $p$ . Mapping every point $(f_{\lambda}(a),f_{\lambda}(b))\in{{\rm Dgm}_{p}{({f_{\lambda}})}}$ to $(f_{\lambda}(a),f_{\lambda}(b),\lambda)\in{{\mathbb{R}}}^{3}$ , we effectively stack up these diagrams, and because of stability, the points form continuous curves in ${{\mathbb{R}}}^{3}$ . Following the terminology in [7], we call these curves vines and the collection of vines a vineyard. Assuming $K$ is finite, there are only finitely many values of $\lambda$ for which $f_{\lambda}$ is not a filter (because it assigns the same value to at least two cells). These values split $[0,1]$ into finitely many open intervals with a unique ordering of the cells in each. In the generic case, the orderings in any two consecutive intervals differ by a single transposition of two adjacent cells. Such a transposition may or may not affect the birth-death pairs, and if it does, we call it a switch. As established in [7], there are only three kinds of switches: the BB-type, which swaps the birth-giving cells between two pairs, the DD-type, which swaps the death-giving cells between two pairs, and the BD-type, which swaps a birth-giving with a death-giving cell; see Figure 2. Observe that in the first two cases, the two affected points belong to the same-degree persistence diagram, while in the third case the affected points belong to persistence diagrams of consecutive degrees.

Figure 2: The three types of switches. From left to right: swapping two birth-giving cells (BB-type), swapping two death-giving cells (DD-type), and swapping a birth-giving with a death-giving cell (BD-type). In the first two cases, the intervals that correspond to the pairs are nested – before and after the switch – and in the third case, they are disjoint – again before and after the switch.

Cancellation of Shallow Pairs.

Given a filtered Lefschetz complex, we are interested in simplifying it. The natural operation to this end is the cancellation of a cell $b$ with one of its facets $a$ . The operation produces a new Lefschetz complex $(K^{\prime},\dim^{\prime},\kappa^{\prime})$ where $K^{\prime}=K\setminus\{a,b\}$ , $\dim^{\prime}$ is the restriction of $\dim$ to $K^{\prime}$ , and the new incidence map is defined for $x,y\in K^{\prime}$ by ${{\kappa}}^{\prime}(y,x)={{\kappa}}(y,x)+{{\kappa}}(y,a)\cdot{{\kappa}}(b,x)$ ; see the schematic cancellation of the pair $(a,b)$ in Figure 3.

Figure 3: To cancel

a\prec b

, we connect all facets of

b

to all cofacets of

a

. The remainder of the face relation is unchanged.

A cancellation may have side-effects, such as changing the homotopy type of the complex or making a cell a facet of another cell that precedes it in the filter. In contrast, a cancellation preserves the homology of the Lefschetz complex [9]. To avoid the need to reorganize the filter, we restrict ourselves to cancellations where this is not necessary. Even more, we restrict ourselves to canceling shallow pairs, $a\prec b$ , for which $a$ is the last facet of $b$ and $b$ is the first cofacet of $a$ in the ordering of the filter; see [9] but also [2], where they are referred to as apparent pairs. If $a\prec b$ is a shallow pair, then all other facets of $b$ precede $a$ and all other cofacets of $a$ succeed $b$ , so the new filter is obtained by removing $a$ and $b$ , and no reordering is necessary. The following basic properties are obvious or proved in [9]:

$\blacksquare$

every shallow pair is a birth-death pair of the filter;
$\blacksquare$

after a shallow pair is canceled, the remaining birth-death pairs are unchanged;
$\blacksquare$

there is at least one shallow pair, unless the face relation is empty.

Because of the third property, we can keep canceling shallow pairs until the face relation runs empty. We call the resulting sequence of canceled pairs a shallow cancellation order, which by the first two properties is a total order of the birth-death pairs of the original filter. However, there may be many orderings of the birth-death pairs such that each pair is shallow at the time it gets canceled, which motivates the next concept.

Definition 2.2.

The depth poset of a filter on a Lefschetz complex, $f\colon K\to{{\mathbb{R}}}$ , is the intersection of all shallow cancellation orders of $f$ , denoted ${{\rm Depth}{({f})}}$ .

This concept was introduced in [9], along with some of its fundamental properties, which we state without proof.

Lemma 2.3.

Let $f\colon K\to{{\mathbb{R}}}$ be a filter on a Lefschetz complex, $\varphi=(x,y)$ and $\psi=(a,b)$ two birth-death pairs of $f$ , $(\varphi,\psi)$ an arc in ${{\rm Depth}{({f})}}$ , $\sigma=(s,t)$ a shallow pair of $f$ , and $f^{\prime}\colon K\setminus\{s,t\}$ the filter after canceling $\sigma$ . Then

1.

nodes connected by an arc in ${{\rm Depth}{({f})}}$ are nested; that is: $f(a)<f(x)<f(y)<f(b)$ ;
2.

arcs of ${{\rm Depth}{({f})}}$ respect dimensions; that is: ${\rm dim\,}{a}={\rm dim\,}{x}$ and ${\rm dim\,}{b}={\rm dim\,}{y}$ ;
3.

canceling $\sigma$ has no side-effects; that is: ${{\rm Depth}{({f^{\prime}})}}={{\rm Depth}{({f})}}\cap[{{{\it BD}}{({f^{\prime% }})}}\times{{{\it BD}}{({f^{\prime}})}}]$ .

By Property 2, ${{\rm Depth}{({f})}}$ is the disjoint union of posets ${{\rm Depth}_{p}{({f})}}\subseteq{{{\it BD}}_{p}{({f})}}\times{{{\it BD}}_{p}{% ({f})}}$ .

Matrix Reduction Twice.

While the definition of the depth poset is constructive, it is in terms of possibly exponentially many total orders on the birth-death pairs. Alternatively, it can be constructed as the transitive closure of two relations, both of which can be computed efficiently by reducing the boundary matrix of the complex. We review the algorithms and refer to [9] for a proof of correctness.

Definition 2.4.

The death relation of a filter on a Lefschetz complex, $f\colon K\to{{\mathbb{R}}}$ , denoted ${{D}}(f)\subseteq{{{\it BD}}{({f})}}\times{{{\it BD}}{({f})}}$ , records the left-to-right column operations during the reduction of the boundary matrix in reverse order of the birth-giving cells; see Algorithm 1.

Algorithm 1 Bottom to Top Column Reduction.

Input: $\Delta$ (the boundary matrix)
Output: $R_{1}U_{1}$ (a decomposition of $\Delta$ )

The arcs in the death relation correspond to the off-diagonal non-zero entries in the columns of death-giving cells in $U_{1}$ :

\displaystyle{\mbox{${D}$}}(f)

\displaystyle=\{\left((x,y),(a,b)\right)\in{{{\it BD}}{({f})}}\times{{{\it BD}% }{({f})}}\mid y\neq b{\rm\nobreak\ and\nobreak\ }U_{1}[y,b]=1\}.

(2)

To make sense of $U_{1}$ , consider the matrix $V_{1}$ that stores the chains whose boundaries are the cycles in $R_{1}$ . Initially, $V_{1}$ is the identity matrix and we maintain it by applying the same column operations as performed on $R_{1}$ . If we ignore the deletions of rows and columns, we retain the matrices in their original sizes, and it is not difficult to see that they satisfy $R_{1}=\Delta V_{1}$ and $\Delta=R_{1}U_{1}$ throughout the algorithm, so $U_{1}=V_{1}^{-1}$ .

Definition 2.5.

The birth relation of a filter on a Lefschetz complex, $f\colon K\to{{\mathbb{R}}}$ , denoted ${{B}}(f)\subseteq{{{\it BD}}{({f})}}\times{{{\it BD}}{({f})}}$ , records the bottom-to-top row operations during the reduction of the boundary matrix in the order of the death-giving cells; see Algorithm 2.

Algorithm 2 Left to Right Row Reduction.

Input: $\Delta$ (the boundary matrix)
Output: $R_{2}U_{2}$ (a decomposition of $\Delta$ )

The arcs in the birth relation correspond to the off-diagonal non-zero entries in the rows of birth-giving cells in $U_{2}$ :

\displaystyle{\mbox{${B}$}}(f)

\displaystyle=\{\left((x,y),(a,b)\right)\in{{{\it BD}}{({f})}}\times{{{\it BD}% }{({f})}}\mid x\neq a{\rm\nobreak\ and\nobreak\ }U_{2}[a,x]=1\}.

(3)

To rationalize $U_{2}$ , we introduce the matrix $V_{2}$ that stores the chains whose coboundaries are the cocycles, i.e. $R_{2}=V_{2}\Delta$ assuming we ignore the deletions of rows and columns. Similarly $\Delta=U_{2}R_{2}$ , so $U_{2}=V_{2}^{-1}$ .

The right panel of Figure 1 shows examples of the death and birth relations of a filter. A noteworthy feature of this example are the pairs $({\tt d},\gamma)$ and $(\beta,\Sigma)$ . In spite of the fact that d is an edge of $\beta$ , which prevents $({\tt d},\gamma)$ from being shallow, there is no arc connecting the two pairs in the depth poset. Indeed, the two pairs are neither nested nor do their dimensions match, so an arc would contradict the first two properties in Lemma 2.3. Hence, it must be possible to cancel $({\tt d},\gamma)$ before canceling $(\beta,\Sigma)$ , and this can indeed be done if we first cancel $({\tt e},\alpha)$ , which is the sole predecessor of $({\tt d},\gamma)$ in the poset. Geometrically, the cancellation of $({\tt e},\alpha)$ attaches $\beta$ to d twice, which in modulo- $2$ arithmetic is counted as no attachment.

It is not difficult to see that the two relations are neither necessarily their own transitive closures nor necessarily their own transitive reductions, and while they express different pieces of information, they are not necessarily disjoint. Nevertheless, they determine the depth poset as the transitive closure of their union; see [9] for a proof. This is important so we state the claim more formally.

Theorem 2.6.

Let $f\colon K\to{{\mathbb{R}}}$ be a filter on a Lefschetz complex. Then ${{\rm Depth}{({f})}}$ is the transitive closure of ${{D}}(f)\cup{{B}}(f)$ .

3 Case Analysis

A transposition preserves all birth-death pairs, unless it is a switch, in which case the two transposed cells replace each other in their respective pairs. Consider for example the filter in Figure 1 and entertain what happens when we transpose the edges $\tt c$ and $\tt d$ . Comparing Figures 1 and 4, we note that $({\tt C},{\tt c})$ and $({\tt d},\gamma)$ got replaced by $({\tt C},{\tt d})$ and $({\tt c},\gamma)$ , and the death and birth relations both lost their only arc.

Figure 4: The only difference to the example in Figure 1 is the order of the edges

\tt c

and

\tt d

. To the right, we see the death and birth relations, which are both empty.

It should however be noted that a transposition may change the depth poset without affecting the birth-death pairs. To see this, we organize a complete case analysis along the classification of transpositions into three types: of two birth-giving cells, of two death-giving cells, and of a birth-giving with a death-giving cell.

Prior to the case analysis, we state two lemmas that will both be repeatedly used. The first excludes certain configurations of birth-death pairs.

Lemma 3.1.

Let $f\colon K\to{{\mathbb{R}}}$ be a filter on a Lefschetz complex, and $a\prec y$ two cells in $K$ . If $a$ is the last facet of $y$ in the ordering implied by $f$ , and $a$ is not yet paired when we encounter $y$ in the ordering of the filter, then $(a,y)$ is a birth-death pair of $f$ .

Proof.

Consider the standard matrix reduction algorithm for persistent homology, which reduces the columns of the ordered boundary matrix from left to right. Since $a$ is the last facet of $y$ , the lowest non-zero entry in column $y$ is in row $a$ . When the algorithm arrives at $y$ , $a$ is not yet paired, so there is no pivot in its row. It follows that this entry remains and becomes a pivot, which is equivalent to $(a,y)$ becoming a birth-death pair. $\hfill\blacktriangleleft$

The second lemma addresses a property of ordered boundary matrices that amounts to a reformulation of Lemma 4.6 in [9]. We state it without proof.

Lemma 3.2.

Let $f\colon K\to{{\mathbb{R}}}$ be a filter on a Lefschetz complex, $\Delta$ the corresponding ordered boundary matrix, $x$ a row of $\Delta$ , and $y$ a column of $\Delta$ . Then any two boundary matrices obtained by canceling all birth-death pairs with pivots below row $x$ or to the left of column $y$ following shallow but possibly different cancellation orders are the same.

3.1 Case I: Birth-birth Transpositions

Let $(x,y)$ and $(a,b)$ be two nested or otherwise overlapping birth-death pairs with matching dimension, so $f(a)<f(x)<f(y)<f(b)$ or $f(x)<f(a)<f(y)<f(b)$ and ${\rm dim\,}{a}={\rm dim\,}{x}={\rm dim\,}{y}-1={\rm dim\,}{b}-1$ . As illustrated in Figure 5, we assume that $a$ and $x$ are consecutive in the ordering, so either the two pairs are incomparable in the depth poset, or they are connected by an arc but not by a path of two arcs. To prepare the analysis, we cancel the birth-death pairs whose pivots are below row $x$ or to the left of column $y$ in the ordered boundary matrix. By Lemma 3.2, the sequence in which these pairs are canceled does not affect the remaining portion of the boundary matrix. After the cancellations, $(x,y)$ is shallow and $(a,b)$ is either shallow or has $(x,y)$ as its sole predecessor in the depth poset. Similarly, we cancel all birth-death pairs with pivots below row $a$ or to the left of column $y$ in the boundary matrix after transposing $a$ and $x$ . The two operations commute, so we can alternatively transpose $a$ and $x$ after the mentioned cancellations. Refer to Figure 5 for the three sub-cases as defined after the initial cancellations:

Figure 5: The configurations before and after the transposition of two birth-giving cells. From left to right: Cases I.1, I.2, I.3, with the configuration before and after the transposition at the top and the bottom, respectively, or vice versa for the inverse transposition. Within each panel, we show the relevant birth- and death-giving cells as rows and columns of the boundary matrix, respectively, the two birth-death pairs as bars with dotted face relation, and the corresponding nodes and arcs in the death and birth relations.

Case I.1:: $a\prec y$ and $x\nprec b$ , as illustrated in the upper left panel of Figure 5. Since $(a,b)$ is not shallow, it must be that $(x,y)$ precedes $(a,b)$ in the depth poset before the transposition of $a$ and $x$ . To see that the transposition is a switch note that after transposing, $a$ is the last facet of $y$ and is not yet paired before we encounter $y$ from the left, so $(a,y)$ is a birth-death pair by Lemma 3.1. By the stability of the persistence diagram [6], $(x,b)$ is another pair after the transposition, and the remaining pairs are unchanged; see the lower left panel of Figure 5. Finally, reading the two panels from bottom to top, we have the inverse switch defined by $x\prec y$ and $a\prec b$ .
Case I.2:: $a\nprec y$ and $x\prec b$ , as illustrated in the upper middle panel of Figure 5. Like in Case I.1, $(x,y)$ is a predecessor of $(a,b)$ before the transposition of $a$ and $x$ . Since $a$ is not a facet of $y$ , $(x,y)$ remains shallow, so the transposition is not a switch. But since the two pairs are no longer nested, they are also no longer comparable by Lemma 2.3; see the lower middle panel of Figure 5. Reading the two panels from bottom to top, we have the inverse transposition defined by $a\nprec y$ and $x\prec b$ , but now for two overlapping pairs.
Case I.3:: $a\nprec y$ and $x\nprec b$ , as illustrated in the upper right panel of Figure 5. Like in Case I.2, the transposition of $a$ and $x$ maintains $(x,y)$ as a shallow pair, so the transposition is not a switch. The two pairs are incomparable before the transposition because $x$ is not a facet of $b$ and $y$ is not a cofacet of $a$ , and after the transposition because the pairs are no longer nested; see the lower right panel of Figure 5. The inverse transposition is defined by $a\nprec y$ and $x\nprec b$ , but now for pairs that are neither nested nor disjoint.

When the transposition of $a$ and $x$ is not a switch, then the changes described in Cases I.2 and I.3 are exhaustive, but if it is a switch, there may be changes beyond those described in Case I.1. We need notation to describe them. Letting $\varphi=(x,y)$ and $\psi=(a,b)$ be two birth-death pairs, the former is a predecessor of the latter in the death relation if $U_{1}[y,b]=1$ and in the birth relation if $U_{2}[a,x]=1$ . We therefore write

$\displaystyle{\mbox{$\rm Pred$}}_{1}{({a,b})}$	$\displaystyle=\{\varphi\mid(\varphi,\psi)\in{{D}}\}=\{(x,y)\in{{{\it BD}}{({f}% )}}\mid y\neq b{\rm\nobreak\ and\nobreak\ }U_{1}[y,b]=1\};$	(4)
$\displaystyle{\mbox{$\rm Pred$}}_{2}{({a,b})}$	$\displaystyle=\{\varphi\mid(\varphi,\psi)\in{{B}}\}=\{(x,y)\in{{{\it BD}}{({f}% )}}\mid a\neq x{\rm\nobreak\ and\nobreak\ }U_{2}[a,x]=1\};$	(5)
$\displaystyle{\mbox{$\rm Succ$}}_{1}{({a,b})}$	$\displaystyle=\{\varphi\mid(\psi,\varphi)\in{{D}}\}=\{(x,y)\in{{{\it BD}}{({f}% )}}\mid b\neq y{\rm\nobreak\ and\nobreak\ }U_{1}[b,y]=1\};$	(6)
$\displaystyle{\mbox{$\rm Succ$}}_{2}{({a,b})}$	$\displaystyle=\{\varphi\mid(\psi,\varphi)\in{{B}}\}=\{(x,y)\in{{{\it BD}}{({f}% )}}\mid x\neq a{\rm\nobreak\ and\nobreak\ }U_{2}[x,a]=1\},$	(7)

and ${\rm Pred}_{1}^{{\rm bef}}{({a,b})}$ , ${\rm Pred}_{1}^{{\rm aft}}{({a,b})}$ for the sets before and after a transposition, etc. We begin with the changes of the successors in the death relation and write $\oplus$ for the symmetric difference operation between sets.

Lemma 3.3.

Let $f\colon K\to{{\mathbb{R}}}$ be a filter on a Lefschetz complex, $(x,y)$ and $(a,b)$ birth-death pairs of matching dimension, $a$ precedes $x$ , $y$ precedes $b$ , and $a, x$ are consecutive in the ordering implied by the filter. Then $a\prec y$ iff $(x,y)\in{\rm Pred}_{2}{({a,b})}$ iff the transposition of $x$ and $a$ is a BB-type switch (see the left panels in Figure 5), and in this case

$\displaystyle{\mbox{$\rm Succ$}}_{1}^{{\rm aft}}{({a,y})}$	$\displaystyle={\rm Succ}_{1}^{{\rm bef}}{({x,y})}\oplus(x,b)\oplus{\rm Succ}_{% 1}^{{\rm bef}}{({a,b})};\nobreak\ \nobreak\ {\rm Succ}_{1}^{{\rm aft}}{({x,b})% }={\rm Succ}_{1}^{{\rm bef}}{({a,b})};$	(8)
$\displaystyle{\mbox{$\rm Succ$}}_{2}^{{\rm aft}}{({a,y})}$	$\displaystyle={\rm Succ}_{2}^{{\rm bef}}{({x,y})}\oplus\{(x,b),(a,b)\};% \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak% \ \nobreak\ \nobreak\ {\rm Succ}_{2}^{{\rm aft}}{({x,b})}={\rm Succ}_{2}^{{\rm bef% }}{({a,b})};$	(9)
$\displaystyle{\mbox{$\rm Pred$}}_{1}^{{\rm aft}}{({a,y})}$	$\displaystyle={\rm Pred}_{1}^{{\rm bef}}{({x,y})};\nobreak\ \nobreak\ \nobreak% \ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ % \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak% \ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ % \nobreak\ \nobreak\ \nobreak\ \nobreak\ \,{\rm Pred}_{1}^{{\rm aft}}{({x,b})}=% {\rm Pred}_{1}^{{\rm bef}}{({a,b})};$	(10)
$\displaystyle{\mbox{$\rm Pred$}}_{2}^{{\rm aft}}{({a,y})}$	$\displaystyle={\rm Pred}_{2}^{{\rm bef}}{({x,y})};\nobreak\ \nobreak\ \nobreak% \ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ % \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak% \ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ % \nobreak\ \nobreak\ \nobreak\ \nobreak\ \,{\rm Pred}_{2}^{{\rm aft}}{({x,b})}=% {\rm Pred}_{2}^{{\rm bef}}{({a,b})}.$	(11)

Otherwise, the depth relation remains as is, except if $x\prec b$ (see the middle panels in Figure 5), in which case ${\rm Succ}_{1}^{{\rm aft}}{({x,y})}={\rm Succ}_{1}^{{\rm bef}}{({x,y})}\oplus(% a,b)\oplus{\rm Succ}_{1}^{{\rm bef}}{({a,b})}$ , while all other sets of successors and predecessors of $(x,y)$ and $(a,b)$ remain unchanged.

Proof.

The two equivalences follow from the completeness of the case analysis displayed in Figure 5. To see (8), consider rows $a$ and $x$ in the boundary matrix before and after the switch. With reference to the upper left panel of Figure 5 – which shows the matrix before the switch – we give names to the portions of these rows delimited by columns $y$ and $b$ :

	$\displaystyle M_{a}$	$\displaystyle=\{R_{1}[a,t]\mid f(y)\leq f(t)<f(b)\};\nobreak\ \nobreak\ N_{a}=% \{R_{1}[a,t]\mid f(b)\leq f(t)\};$		(12)
	$\displaystyle M_{x}$	$\displaystyle=\{R_{1}[x,t]\mid f(y)\leq f(t)<f(b)\};\nobreak\ \nobreak\ N_{x}=% \{R_{1}[x,t]\mid f(b)\leq f(t)\}.$		(13)

Canceling $(x,y)$ changes row $a$ to $(M_{a}+M_{x})|(N_{a}+N_{x})$ , in which the bar means catenation. At this time, $(a,b)$ is a shallow pair, so $M_{a}+M_{x}=0$ , which implies $M_{a}=M_{x}$ . Columns $y$ and $b$ in $U_{1}$ are transposed copies of rows $x$ and $a$ at the moment before $(x,y)$ and then $(a,b)$ are canceled. Hence, column $y$ in $U_{1}$ is $(M_{x}|N_{x})^{T}$ , and column $b$ is $(N_{a}+N_{x})^{T}$ . This is before the transposition of $a$ and $x$ . After the transposition, column $y$ in $U_{1}$ is $(M_{a}|N_{a})^{T}$ , and column $b$ is $(N_{x}+N_{a})^{T}$ . Using $M_{a}=M_{x}$ and $N_{a}=N_{x}+(N_{a}+N_{x})$ , we rewrite these relations in different notation:

	$\displaystyle U_{1}^{{\rm aft}}[y,t]$	$\displaystyle=\left\{\begin{array}[]{ll}U_{1}^{{\rm bef}}[y,t]&{\rm for% \nobreak\ \nobreak\ }f(y)\leq f(t)<f(b),\\ U_{1}^{{\rm bef}}[y,t]+U_{1}^{{\rm bef}}[b,t]&{\rm for\nobreak\ \nobreak\ }f(b% )\leq f(t);\end{array}\right.$		(16)
	$\displaystyle U_{1}^{{\rm aft}}[b,t]$	$\displaystyle=U_{1}^{{\rm bef}}[b,t].$		(17)

Finally, we translate the relations into the notation of the lemma using (6), and get (8) from (16) and (17). We omit the arguments for the remaining relations in Lemma 3.3. $\hfill\blacktriangleleft$ The symmetric cases – when $x$ precedes $a$ so the birth-birth transpositions go from the lower to the upper panes in Figure 5 – are similar and the same relations between the successors and predecessors before and after the transposition apply.

3.2 Case II: Death-death Transpositions

The setting is similar to Case I: $(x,y)$ and $(a,b)$ are nested or otherwise overlapping birth-death pairs of matching dimension, but now we assume that $y$ and $b$ are consecutive in the ordering implied by the filter. As before, we prepare the analysis by canceling all birth-death pairs whose pivots are below row $x$ or to the left of column $y$ . After these cancellations, $(x,y)$ is shallow, and $(a,b)$ is shallow or it has $(x,y)$ as its sole predecessor in the depth poset. Refer to Figure 6 for the three sub-cases as defined after the initial cancellations:

Figure 6: The configurations before and after the transposition of two death-giving cells in the filter. From left to right: Cases II.1, II.2, II.3, with the configuration before the transposition at the top and after the transposition at the bottom, or vice versa for the inverse transposition. Within each panel, we show the relevant birth-giving cells as rows and death-giving cells as columns of the matrix, the two birth-death pairs as bars, and the corresponding nodes and relations in the death and birth relations.

Case II.1:: $a\nprec y$ and $x\prec b$ for a nested pair, as illustrated in the upper left panel of Figure 6. The transposition is a switch, and reading the two left panels from bottom to top, we have the inverse switch defined by $x\prec y$ and $a\prec b$ .
Case II.2:: $a\prec y$ and $x\nprec b$ for a nested pair, as illustrated in the upper middle panel of Figure 6. The transposition is not a switch, and reading the two middle panels from bottom to top, we have the inverse transposition defined by the same two conditions for overlapping pairs.
Case II.3:: $a\nprec y$ and $x\nprec b$ for a nested pair, as illustrated in the upper right panel of Figure 6. Again this transposition is not a switch, and reading the two right panels from bottom to top, we have the inverse transposition defined by the same two conditions for overlapping pairs.

The sub-cases are strictly symmetric to Cases I.1, I.2, I.3, with identical arguments for the symmetric actions. While omitting other details, we state the result symmetric to Lemma 3.3, which describes the changes to the death and birth relations beyond the pairs that contain the transposed cells.

Lemma 3.4.

Let $f\colon K\to{{\mathbb{R}}}$ be a filter on a Lefschetz complex, $(x,y)$ , $(a,b)$ birth-death pairs of matching dimension, $a$ precedes $x$ , $y$ precedes $b$ , and $y, b$ are consecutive in the ordering implied by the filter. Then $x\prec b$ iff $(x,y)\in{\rm Pred}_{1}{({a,b})}$ iff the transposition of $y$ and $b$ is a DD-type switch (see the left panels in Figure 6). and in this case

$\displaystyle{\mbox{$\rm Succ$}}_{1}^{{\rm aft}}{({x,b})}$	$\displaystyle={\rm Succ}_{1}^{{\rm bef}}{({x,y})}\oplus\{((a,y),(a,b)\};% \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak% \ \nobreak\ {\rm Succ}_{1}^{{\rm aft}}{({a,y})}={\rm Succ}_{1}^{{\rm bef}}{({a% ,b})};$	(18)
$\displaystyle{\mbox{$\rm Succ$}}_{2}^{{\rm aft}}{({x,b})}$	$\displaystyle={\rm Succ}_{2}^{{\rm bef}}{({x,y})}\oplus(a,y)\oplus{\rm Succ}_{% 2}^{{\rm bef}}{({a,b})};\nobreak\ \nobreak\ {\rm Succ}_{2}^{{\rm aft}}{({a,y})% }={\rm Succ}_{2}^{{\rm bef}}{({a,b})};$	(19)
$\displaystyle{\mbox{$\rm Pred$}}_{1}^{{\rm aft}}{({x,b})}$	$\displaystyle={\rm Pred}_{1}^{{\rm bef}}{({x,y})};\nobreak\ \nobreak\ \nobreak% \ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ % \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak% \ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ % \nobreak\ \nobreak\ \nobreak\ \nobreak\ \,{\rm Pred}_{1}^{{\rm aft}}{({a,y})}=% {\rm Pred}_{1}^{{\rm bef}}{({a,b})};$	(20)
$\displaystyle{\mbox{$\rm Pred$}}_{2}^{{\rm aft}}{({x,b})}$	$\displaystyle={\rm Pred}_{2}^{{\rm bef}}{({x,y})};\nobreak\ \nobreak\ \nobreak% \ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ % \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak% \ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ % \nobreak\ \nobreak\ \nobreak\ \nobreak\ \,{\rm Pred}_{2}^{{\rm aft}}{({a,y})}=% {\rm Pred}_{2}^{{\rm bef}}{({a,b})}.$	(21)

Otherwise, the depth relation remains as is, except if $a\prec y$ (see the middle panels in Figure 6), in which case ${\rm Succ}_{2}^{{\rm aft}}{({x,y})}={\rm Succ}_{2}^{{\rm bef}}{({x,y})}\oplus(% a,b)\oplus{\rm Succ}_{2}^{{\rm bef}}{({a,b})}$ , while all other sets of sets of successors and predecessors of $(s,y)$ and $(a,b)$ remain unchanged.

3.3 Case III: Birth-death Transpositions

Case III is characterized by the transposition of cells $b$ and $x$ , in which $(a,b)$ and $(x,y)$ are disjoint or overlapping birth-death pairs with consecutive dimensions, so $f(a)<f(b)<f(x)<f(y)$ or $f(a)<f(x)<f(b)<f(y)$ and ${\rm dim\,}{a}+1={\rm dim\,}{b}={\rm dim\,}{x}={\rm dim\,}{y}-1$ . Similar to Cases I and II, we prepare the analysis by canceling all pairs whose pivots lie below the rows or to the left of columns $b$ and $x$ . This includes all predecessors of $(a,b)$ and $(x,y)$ , so after these cancellations, both are shallow. Refer to Figure 7 for the two sub-cases, with the conditions referring to the complex after the initial cancellations:

Figure 7: The configurations in Cases III.1 and III.2 on the left and right, before and after the transposition of a birth-giving cell with a death-giving cell. Within each panel, we show the relevant rows and columns of the matrix, and the corresponding birth-death pairs as bars.

Case III.1:: $a\prec x$ and $b\prec y$ for nested pairs, as illustrated in the upper left panel of Figure 7. After transposing $b$ and $x$ , $(a,x)$ and $(b,y)$ are both shallow, so the transposition is a switch and the two new pairs are birth-death pairs of the new filter. By the first two properties in Lemma 2.3, there is no arc connecting the two pairs in the depth poset. The inverse transposition is symmetric and follows the same rules.
Case III.2:: $a\nprec x$ and $b\nprec y$ for nested pairs, as illustrated in the upper right panel of Figure 7. After transposing $b$ and $x$ , $(a,b)$ and $(x,y)$ are still shallow, so the transposition is not a switch. The inverse transposition is defined by the same conditions but now for two overlapping pairs, as illustrated in the bottom right panel of Figure 7.

There are no additional cases, because the relevant birth-death pairs are shallow both before and after the transposition, which excludes configurations different from the ones illustrated in Figure 7. Observe that Case III.1 is quite different from all others, because the transposition changes the types of two cells: $b$ from death- to birth-giving, and $x$ from birth- to death-giving. Hence, their corresponding rows and columns in the boundary matrix assume different roles, which may have a profound impact on the depth poset. We prove that this is in fact not the case for the successors, but it can be for the predecessors.

Recall that Algorithm 1 records the column reductions for all cells alike, but only the ones for death-giving cells turn into arcs of the death relation. Symmetrically, Algorithm 2 records the row reductions for all cells, but only the ones for birth-giving cells that also belong to birth-death pairs turn into arcs of the birth relation. We will now make use of the so far neglected information. Letting $a$ and $x$ be the birth-giving cells of the two pairs in a BD-type switch, we collect the reductions of column $x$ prior to reaching row $a$ as arcs in the death relation, and letting $y$ and $b$ be death-giving cells of these pairs, we collect the reductions of row $b$ prior to reaching column $y$ as arcs in the birth relation.

Lemma 3.5.

Let $f\colon K\to{{\mathbb{R}}}$ be a filter on a Lefschetz complex, $(a,b)$ and $(x,y)$ birth-death pairs of consecutive dimensions, and $b, x$ consecutive in the ordering implied by the filter. Then $a\prec x$ and $b\prec y$ iff the transposition of $b$ and $x$ is a BD-type switch (see the left panels in Figure 7), and in this case

$\displaystyle{\mbox{$\rm Succ$}}_{1}^{{\rm aft}}{({a,x})}$	$\displaystyle={\rm Succ}_{1}^{{\rm bef}}{({a,b})};\nobreak\ \nobreak\ \nobreak% \ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ % \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak% \ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ % \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ {\rm Succ}_{1}^{{\rm aft}}{(% {b,y})}={\rm Succ}_{1}^{{\rm bef}}{({x,y})};$	(22)
$\displaystyle{\mbox{$\rm Succ$}}_{2}^{{\rm aft}}{({a,x})}$	$\displaystyle={\rm Succ}_{2}^{{\rm bef}}{({a,b})};\nobreak\ \nobreak\ \nobreak% \ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ % \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak% \ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ % \nobreak\ \nobreak\ \nobreak\ \nobreak\ \nobreak\ {\rm Succ}_{2}^{{\rm aft}}{(% {b,y})}={\rm Succ}_{2}^{{\rm bef}}{({x,y})};$	(23)
$\displaystyle{\mbox{$\rm Pred$}}_{1}^{{\rm aft}}{({a,x})}$	$\displaystyle=\{(t,x)\mid U_{1}^{{\rm bef}}[t,x]=1,f(t)>f(a)\};\nobreak\ % \nobreak\ \nobreak\ {\rm Pred}_{1}^{{\rm aft}}{({b,y})}={\rm Pred}_{1}^{{\rm bef% }}{({x,y})};$	(24)
$\displaystyle{\mbox{$\rm Pred$}}_{2}^{{\rm aft}}{({a,x})}$	$\displaystyle={\rm Pred}_{2}^{{\rm bef}}{({a,b})};\nobreak\ \nobreak\ \nobreak% \ {\rm Pred}_{2}^{{\rm aft}}{({b,y})}=\{(b,s)\mid U_{2}^{{\rm bef}}[b,s]=1,f(s% )<f(y)\}.$	(25)

Otherwise, the depth relation remains as is (see the right panels in Figure 7).

Proof.

To prove (22) and (23), we first consider rows $b$ and $x$ in the boundary matrix (after canceling all birth-death pairs whose pivots are below row $x$ or to the left of column $b$ ). Before the transposition, $b$ gives death, so there is no pivot in its row. We claim that this implies that the two rows are equal. Indeed, if there is a column in which the entries in rows $b$ and $x$ are different, then the leftmost such entry would be a pivot, which is a contradiction to the assumptions. Since the two rows are the same, transposing them makes no difference, other than exchanging their names. This implies ${\rm Succ}_{1}^{{\rm aft}}{({a,x})}={\rm Succ}_{1}^{{\rm bef}}{({a,b})}$ as well as ${\rm Succ}_{1}^{{\rm aft}}{({b,y})}={\rm Succ}_{1}^{{\rm bef}}{({x,y})}$ . The symmetric argument implies the corresponding relations for the successors in the birth relation.

To prove (24) and (25), we recall that rows $b$ and $x$ are equal, so in the death relation the predecessors of $(x,y)$ before the transposition are the predecessors of $(b,y)$ after the transposition and, symmetrically, in the birth relation the predecessors of $(a,b)$ before the transposition are the predecessors of $(a,x)$ after the transposition. The remaining predecessors of $(a,x)$ and $(b,y)$ are determined while canceling the birth-death pairs with pivots below and to the left of the rows and columns of these pairs. We can get this information from column $x$ in $U_{1}$ and row $b$ in $U_{2}$ as computed before the transposition. $\hfill\blacktriangleleft$ The symmetric cases – in which we read the panels in Figure 7 from bottom to top – are similar. This completes the case analysis of changes to the depth poset caused by the transposition of two cells that are consecutive in the filter.

4 Computational Experiments

In this section, we present measurements of the depth poset collected while running the algorithms on $1$ -, $2$ -, and $3$ -dimensional random functions and straight-line homotopies between them. For each set of parameters, the results are averaged over ten repeats.

4.1 Random Piecewise Linear Functions

To minimize complications and avoid boundary effects as well as any essential homology, we construct the random functions on a regular cubical subdivision of the $d$ -dimensional torus. Choosing a positive integer, $n$ , we use $({{\mathbb{R}}}/n{{\mathbb{Z}}})^{d}$ as a model of the $d$ -torus, and subdivide it with the unit $d$ -cubes of $({{\mathbb{Z}}}/n{{\mathbb{Z}}})^{d}+[0,1]^{d}$ . We furthermore kill its essential homology classes by adding $2^{d}$ extra cells, namely the empty set as the sole $(-1)$ -cell and $\binom{d}{p}$ $(p+1)$ -cells, each with boundary equal to a subdivided $p$ -torus, for $1\leq p\leq d$ . Write $K=K(n,d)$ for the resulting complex, which consists of $\binom{d}{p}n^{d}$ $p$ -cubes, for $0\leq p\leq d$ , plus the $2^{d}$ extra cells.

As an example, let $d=2$ in which case the torus is the $n$ -by- $n$ square grid, which is subdivided into $n^{2}$ unit square cells. The $(-1)$ -cell facilitates reduced homology, which pairs the empty set with the component. In addition, there are two $2$ -cells killing the essential degree- $1$ homology classes, each a polygon whose boundary consists of $n$ edges, a horizontal integer line for one and a vertical integer line in the square grid for the other polygon. Finally, there is the $3$ -cell whose boundary is the entire $n$ -by- $n$ square grid.

Refer to caption — Figure 8: *From left to right:* the average number of nodes (*upper row*) and arcs (*lower row*) in the transitive reduction of the depth poset of a random function on the $d$ -torus, for $d=1,2,3$ , respectively. Because of the symmetries in the construction, the curves for $p=0$ and $p=d-1$ are nearly identical.

To turn this complex into a random function, $f\colon K\to{{\mathbb{R}}}$ , we choose $f(\gamma)$ in $[p,p+1]$ , whenever $p={\rm dim\,}{\gamma}$ . In particular, we choose $f(\gamma)$ uniformly at random in $[p,p+1]$ whenever $\gamma$ is a $p$ -cube, and we set $f(\gamma)=p+1$ whenever it is an extra $p$ -cell. In spite of the extra cells that kill the essential homology of the $d$ -torus, we will refer to $f$ as a random function on the $d$ -torus.

By construction, the filter that orders the cells by value is also ordered by dimension. We may think of $f$ as a piecewise constant function, but there is an alternative interpretation as a piecewise linear function. Letting $\hat{K}=\hat{K}(n,d)$ be the barycentric subdivision of $K$ , each vertex $\hat{\gamma}\in\hat{K}$ is the center of a cell $\gamma\in K$ , and we map $\hat{\gamma}$ to $\hat{f}(\hat{\gamma})=f(\gamma)$ . We then get $\hat{f}$ on the underlying space of $K$ by piecewise linear interpolation of its values at the vertices. By construction, each center of a $p$ -cell in $K$ is a critical point of index $p$ of $\hat{f}$ . All critical points are paired up as nodes of the depth poset, which implies that $n$ and $d$ determine the number of nodes for each $-1\leq p\leq d$ ; see the upper row in Figure 8. In contrast, the number of arcs in the depth poset has a small but non-zero variance; see the lower row of Figure 8.

As proved in [9], the depth poset splits by the dimensions of the nodes, but depending on the data it may split further. The upper row in Figure 9 shows that it indeed does so for random functions on the $2$ -torus. Each component has at least one minimal and one maximal node, but there may be more, and the middle and lower rows of the same figure support this possibility. Recall that the minimal nodes of the depth poset are exactly the shallow pairs, which explains why their number has barely any variance. In $d=2$ dimensions, there are $4n^{2}$ incident vertex-edge pairs, and such a pair is shallow iff the edge precedes the other three incident edges of the vertex, and the vertex succeeds the other incident vertex of the edge. Indeed, if an incident vertex-edge pair satisfies these conditions, then it is a pair in persistence as well as shallow, and if it does not satisfy these conditions, it may or may not be a pair in persistence but it is certainly not shallow. Since the vertices and edges are ordered randomly and independently, the edge is first among four with probability $\frac{1}{4}$ and the vertex is second among two with probability $\frac{1}{2}$ . Ignoring the extra $(-1)$ -cell, the chance of such a pair to be shallow is therefore $\frac{1}{8}$ . Symmetrically, there are $4n^{2}$ incident edge-square pairs, and ignoring the extra $3$ -cell, the chance of an incident edge-square pair to be shallow is again $\frac{1}{8}$ . This implies that the expected number of shallow pairs is $n^{2}+O(1)$ ; see the first panel in the middle row of Figure 9. Each shallow pair is also a minimal node in the death and birth relations, but both have additional minimal nodes; see the symmetry of the curves in the second and third panels in the middle row of Figure 9, which is a consequence of the symmetry of cubically subdividing the torus. We observe that there are many more minimal nodes than there are maximal nodes. Curiously, the depth poset has many fewer maximal nodes than the death and birth relations, while the difference seems less dramatic for the minimal nodes.

By definition, a poset has no directed cycle, but it may have undirected cycles (pairs of paths that connect the same two nodes). For a $1$ -dimensional function, the death and birth relations have no undirected cycles either but, perhaps surprisingly, the union of these two relations can have such cycles. Figure 10 shows the average number of (undirected) cycles (which we compute as $\#{\rm components}+\#{\rm arcs}-\#{\rm nodes}$ ), together with the average height (defined as the number of arcs in the longest directed path in the relation).

4.2 Straight-line Homotopies

Letting $f_{0},f_{1}\colon K\to{{\mathbb{R}}}$ be two random functions on the $d$ -torus, the straight-line homotopy between them is the $1$ -parameter family of functions $f_{\lambda}(\gamma)=(1-\lambda)f_{0}(\gamma)+\lambda f_{1}(\gamma)$ , for all $\gamma\in K$ and $0\leq\lambda\leq 1$ . To collect the statistics, we perform the transpositions of cells in sequence and one at a time. Given two cells of not necessarily the same dimension, $\gamma,\eta\in K$ , the parameter at which their values match is

\displaystyle\lambda(\gamma,\eta)

\displaystyle=\frac{f_{0}(\eta)-f_{0}(\gamma)}{[f_{0}(\eta)-f_{0}(\gamma)]-[f_% {1}(\eta)-f_{1}(\gamma)]}.

(26)

The relevant such parameter values are the ones in $[0,1]$ . Instead of sorting them, it is more efficient to maintain the filter, and at each step transpose the two cells whose values match next. If this pair is not unique, we break ties and transpose the cells in sequence.

As shown in the upper row of Figure 11, the transpositions that are not switches outnumber those that are switches, so it is useful to draw the curves of the latter on a more appropriate scale, which we do in the lower row of the same figure. As shown in the lower row of Figure 11, there are barely any BD-type switches of two vertices or two $2$ -cells, and even for edges, there are fewer BD-type switches than switches of BB-type and switches of DD-type.

An interesting aspect of the transpositions is how much they change the depth poset. Every switch affects exactly two nodes, while a transposition that is not a switch leaves all nodes unchanged. The effect on the arcs is less predictable, so we measure the change by counting the arcs that are different before and after the transposition. Not surprisingly, there are barely any arcs that change when the transposition is not a switch. Also not surprisingly, there are significantly more arcs that change in the depth poset as compared to the transitive reduction of the poset. Because of the limited size of the random functions in our experiment, it is difficult to gauge how the size of the symmetric difference of the arcs before and after the transposition grows with the size of the function. In any case, it seems to grow much slower than the total number of arcs, which we observe to grow quadratically in $n$ ; see the middle panel in the lower row of Figure 8.

5 Discussion

The main contribution of this paper is the complete analysis of how transpositions of cells in the filter affect the depth poset of a filtered Lefschetz complex. This analysis provides further evidence for the relative significance of birth-death switches, as they mark a more extensive re-organization of the persistent homology than all other types of transpositions. Our initial computational experiments suggest that the birth-death switches are more rare than all other types, and that the number of arcs that change grows much slower than the total number of arcs in the depth poset. This work calls for further research in at least the following three directions:

$\blacksquare$

investigate the links between the transposition induced changes in the depth poset and the bifurcations in the associated gradient dynamics;
$\blacksquare$

extend the notion of a depth poset from discrete Morse functions to discrete vector fields as introduced in Forman [12], or even to multi-vector fields as studied in [16, 17];
$\blacksquare$

study the depth poset stochastically for various models of random functions and for homotopies between them.

We finally mention that the algorithms in this paper and its precursor [9] are closely related to the algorithms for topology optimization described by Nigmetov and Morozov [19]. Can the more global topological information provided by the depth poset be harvested to get faster or better methods for topology optimization?

References

[1] Dominique Attali, Marc Glisse, Samuel Hornus, Francis Lazarus, and Dmitriy Morozov. Persistence-sensitive simplification of functions on surfaces in linear time. Manuscript, presented at TOPOINVIS, 9:23–24, 2009. URL: https://members.loria.fr/SHornus/simplif/attali-pssfslt.pdf.
[2] Ulrich Bauer. Ripser: efficient computation of Vietoris–Rips persistence barcodes. Journal of Applied and Computational Topology, 5(3):391–423, 2021. doi:10.1007/s41468-021-00071-5.
[3] Ulrich Bauer, Carsten Lange, and Max Wardetzky. Optimal topological simplification of discrete functions on surfaces. Discrete & Computational Geometry, 47(2):347–377, 2012. doi:10.1007/s00454-011-9350-z.
[4] Martin P. Bendsøe. Optimization of Structural Topology, Shape, and Material. Springer, Berlin, Germany, 1995. doi:10.1007/978-3-662-03115-5.
[5] Martin P. Bendsøe and Ole Sigmund. Topology Optimization. Springer, Berlin, Germany, 2nd edition, 2004. doi:10.1007/978-3-662-05086-6.
[6] David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. Discrete & Computational Geometry, 37(1):103–120, 2007. doi:10.1007/s00454-006-1276-5.
[7] David Cohen-Steiner, Herbert Edelsbrunner, and Dmitriy Morozov. Vines and vineyards by updating persistence in linear time. In Proceedings of the 26th Annual Symposium on Computational Geometry, SCG ’06, pages 119–126, New York, NY, USA, 2006. Association for Computing Machinery. doi:10.1145/1137856.1137877.
[8] Olaf Delgado-Friedrichs, Vanessa Robins, and Adrian Sheppard. Skeletonization and partitioning of digital images using discrete Morse theory. IEEE Trans Pattern Anal Mach Intell, 37(3):654–666, March 2015. doi:10.1109/TPAMI.2014.2346172.
[9] Hebert Edelsbrunner, Michał Lipiński, Marian Mrozek, and Manuel Soriano-Trigueros. The poset of cancellations induced by gradient dynamics in a filtered Lefschetz complex. arXiv:2311.14364, 2026. doi:10.48550/arXiv.2311.14364.
[10] Herbert Edelsbrunner and John L Harer. Computational topology: an introduction. American Mathematical Society, Providence, Rhode Island, 2010. doi:10.1090/mbk/069.
[11] Herbert Edelsbrunner, Dmitriy Morozov, and Valerio Pascucci. Persistence-sensitive simplification functions on 2-manifolds. In Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, SCG ’06, pages 127–134, New York, NY, USA, 2006. Association for Computing Machinery. doi:10.1145/1137856.1137878.
[12] Robin Forman. Combinatorial vector fields and dynamical systems. Mathematische Zeitschrift, 228(4):629–681, 1998. doi:10.1007/PL00004638.
[13] Robin Forman. Morse theory for cell complexes. Advances in Mathematics, 134(1):90–145, 1998. doi:10.1006/aima.1997.1650.
[14] Allen Hatcher. Algebraic Topology. Cambridge University Press, 2002.
[15] Solomon Lefschetz. Algebraic Topology, volume 27 of Colloquium Publications. American Mathematical Society, Providence, Rhode Island, 1942.
[16] Michał Lipiński, Jacek Kubica, Marian Mrozek, and Thomas Wanner. Conley-Morse-Forman theory for generalized combinatorial multivector fields on finite topological spaces. Journal of Applied and Computational Topology, 7:139–184, 2022. doi:10.1007/s41468-022-00102-9.
[17] Marian Mrozek. Conley–Morse–Forman theory for combinatorial multivector fields on Lefschetz complexes. Foundations of Computational Mathematics, 17(6):1585–1633, 2017. doi:10.1007/s10208-016-9330-z.
[18] Marian Mrozek and Thomas Wanner. Connection Matrices in Combinatorial Topological Dynamics. SpringerBriefs in Mathematics. Springer Cham, 2025. doi:10.1007/978-3-031-87600-4.
[19] Arnur Nigmetov and Dmitriy Morozov. Topological optimization with big steps. Discrete & Computational Geometry, 72(1):310–344, 2024. doi:10.1007/s00454-023-00613-x.
[20] Jens Kristian Refsgaard Schou and Bei Wang. Persisort: A new perspective on adaptive sorting based on persistence. In Proc. 36th Canadian Conference on Computational Geometry, pages 287–302, July 2024.

[bib.bib1] [1] Dominique Attali, Marc Glisse, Samuel Hornus, Francis Lazarus, and Dmitriy Morozov. Persistence-sensitive simplification of functions on surfaces in linear time. Manuscript, presented at TOPOINVIS, 9:23–24, 2009. URL: https://members.loria.fr/SHornus/simplif/attali-pssfslt.pdf.

[bib.bib2] [2] Ulrich Bauer. Ripser: efficient computation of Vietoris–Rips persistence barcodes. Journal of Applied and Computational Topology, 5(3):391–423, 2021. doi:10.1007/s41468-021-00071-5.

[bib.bib3] [3] Ulrich Bauer, Carsten Lange, and Max Wardetzky. Optimal topological simplification of discrete functions on surfaces. Discrete & Computational Geometry, 47(2):347–377, 2012. doi:10.1007/s00454-011-9350-z.

[bib.bib4] [4] Martin P. Bendsøe. Optimization of Structural Topology, Shape, and Material. Springer, Berlin, Germany, 1995. doi:10.1007/978-3-662-03115-5.

[bib.bib5] [5] Martin P. Bendsøe and Ole Sigmund. Topology Optimization. Springer, Berlin, Germany, 2nd edition, 2004. doi:10.1007/978-3-662-05086-6.

[bib.bib6] [6] David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. Discrete & Computational Geometry, 37(1):103–120, 2007. doi:10.1007/s00454-006-1276-5.

[bib.bib7] [7] David Cohen-Steiner, Herbert Edelsbrunner, and Dmitriy Morozov. Vines and vineyards by updating persistence in linear time. In Proceedings of the 26th Annual Symposium on Computational Geometry, SCG ’06, pages 119–126, New York, NY, USA, 2006. Association for Computing Machinery. doi:10.1145/1137856.1137877.

[bib.bib8] [8] Olaf Delgado-Friedrichs, Vanessa Robins, and Adrian Sheppard. Skeletonization and partitioning of digital images using discrete Morse theory. IEEE Trans Pattern Anal Mach Intell, 37(3):654–666, March 2015. doi:10.1109/TPAMI.2014.2346172.

[bib.bib9] [9] Hebert Edelsbrunner, Michał Lipiński, Marian Mrozek, and Manuel Soriano-Trigueros. The poset of cancellations induced by gradient dynamics in a filtered Lefschetz complex. arXiv:2311.14364, 2026. doi:10.48550/arXiv.2311.14364.

[bib.bib10] [10] Herbert Edelsbrunner and John L Harer. Computational topology: an introduction. American Mathematical Society, Providence, Rhode Island, 2010. doi:10.1090/mbk/069.

[bib.bib11] [11] Herbert Edelsbrunner, Dmitriy Morozov, and Valerio Pascucci. Persistence-sensitive simplification functions on 2-manifolds. In Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, SCG ’06, pages 127–134, New York, NY, USA, 2006. Association for Computing Machinery. doi:10.1145/1137856.1137878.

[bib.bib12] [12] Robin Forman. Combinatorial vector fields and dynamical systems. Mathematische Zeitschrift, 228(4):629–681, 1998. doi:10.1007/PL00004638.

[bib.bib13] [13] Robin Forman. Morse theory for cell complexes. Advances in Mathematics, 134(1):90–145, 1998. doi:10.1006/aima.1997.1650.

[bib.bib14] [14] Allen Hatcher. Algebraic Topology. Cambridge University Press, 2002.

[bib.bib15] [15] Solomon Lefschetz. Algebraic Topology, volume 27 of Colloquium Publications. American Mathematical Society, Providence, Rhode Island, 1942.

[bib.bib16] [16] Michał Lipiński, Jacek Kubica, Marian Mrozek, and Thomas Wanner. Conley-Morse-Forman theory for generalized combinatorial multivector fields on finite topological spaces. Journal of Applied and Computational Topology, 7:139–184, 2022. doi:10.1007/s41468-022-00102-9.

[bib.bib17] [17] Marian Mrozek. Conley–Morse–Forman theory for combinatorial multivector fields on Lefschetz complexes. Foundations of Computational Mathematics, 17(6):1585–1633, 2017. doi:10.1007/s10208-016-9330-z.

[bib.bib18] [18] Marian Mrozek and Thomas Wanner. Connection Matrices in Combinatorial Topological Dynamics. SpringerBriefs in Mathematics. Springer Cham, 2025. doi:10.1007/978-3-031-87600-4.

[bib.bib19] [19] Arnur Nigmetov and Dmitriy Morozov. Topological optimization with big steps. Discrete & Computational Geometry, 72(1):310–344, 2024. doi:10.1007/s00454-023-00613-x.

[bib.bib20] [20] Jens Kristian Refsgaard Schou and Bei Wang. Persisort: A new perspective on adaptive sorting based on persistence. In Proc. 36th Canadian Conference on Computational Geometry, pages 287–302, July 2024.