Access the full text.
Sign up today, get DeepDyve free for 14 days.
In this work we answer an open question asked by Johnson–Scoville. We show that each merge tree is represented by a discrete Morse function on a path. Furthermore, we present explicit constructions for two different but related kinds of discrete Morse functions on paths that induce any given merge tree. A reﬁnement of the used methods allows us to deﬁne notions of equivalence of discrete Morse functions on trees which give rise to a bijection between equivalence classes of discrete Morse functions and isomorphism classes of certain labeled merge trees. We also compare our results to similar ones from the literature, in particular to work by Curry. Keywords Discrete Morse theory · Combinatorial algebraic topology · Merge trees Mathematics Subject Classiﬁcation 57Q70 (Primary) · 05C05 (Secondary) · 05C90 Contents 1 Introduction ............................................... 2 Preliminaries ............................................... 2.1 Merge trees ............................................. 2.2 Generic properties and equivalences of DMFs ........................... 3 Construction of the induced index-ordered DMF ............................ 3.1 The index Morse order ....................................... 3.2 The simplex order .......................................... 3.3 The induced index-ordered DMF .................................. 4 The sublevel-connected DMF ...................................... 5 Relationships between merge trees and DMFs on paths ......................... 6 Further directions and possible applications ............................... References .................................................. B Julian Brüggemann brueggemann@mpim-bonn.mpg.de Max Planck Institute for Mathematics, Bonn, Germany 123 J. Brüggemann 1 Introduction Discrete Morse theory is a combinatorial version of the classical smooth Morse theory. It was originally developed by Forman (1998). In discrete Morse theory, topological properties of simplicial complexes X are analyzed by considering discrete Morse functions f : X → R. These topological properties can in turn be used to obtain cell decompositions of X with fewer cells. A good introduction to the topic is found in Forman (2001). Merge trees are used in Morse theory in order to keep track of the development of −1 connected components of sublevel sets X := f (−∞, a] of a given Morse function f : X → R. Since the sublevel sets form a ﬁltration of X, merge trees can be seen as a combinatorial description of the persistent connectivity of X. In particular, every branching in the induced merge tree M (X , f ) corresponds to a pair of connected components of a sublevel set X that merge to one connected component in a a−ε sublevel complex X of higher level. Initially, merge trees were introduced to topological data analysis as an approxi- mation to the Reeb graph, respectively contour tree, in Carr et al. (2003). The Reeb graph is a graph that keeps track of the connected components of level sets of any given ﬁltered manifold. In applications, the data set is often interpreted as a sampling of the graph of a function rather than a more general manifold, which is why the Reeb graph is often actually a tree, the so-called contour tree. Among other implementations of techniques of smooth Morse theory, computa- tional methods for the Reeb graph have originally been introduced in Shinagawa et al. (1991) in order to handle surfaces embedded in 3D with the help of computers. Later on, several ways to compute and apply contour trees of data sets have been discussed in many articles, e.g. Kweon and Kanade (1994), van Kreveld et al. (1997), Tarasov and Vyalyi (1998), and Carr et al. (2003). Among other applications, merge trees have been used in visualization, e.g. in Oesterling et al. (2013), Weber et al. (2007), Oesterling et al. (2017), and Yan et al. (2019). Surveys about applications of merge trees and other concepts in visualization can be found in Heine et al. (2016) and Liu et al. (2016). Furthermore, a certain version of chiral merge trees has been used in Baryshnikov (2019) to analyze asymmetries of time series. We focus on the more structural and theoretical side of merge trees, in particular the connection to discrete Morse theory. We consider a speciﬁc construction for merge trees induced by discrete Morse functions on trees which was introduced in Johnson and Scoville (2022). We use this construction to gain a better understanding of the set of discrete Morse functions, the set of merge trees, and the relationship between the two. Similar work has been done in Curry (2019) for the relationship between Morse- like functions on the interval and a related version of merge trees. Furthermore, our work is in some sense similar to parts of Curry et al. (2021), with the difference being that the authors of Curry et al. (2021) consider the relationship between merge trees and their induced barcodes instead. It seems reasonable to adapt the following terms from both of these articles and say that we consider a different instance of the “ﬁber of the persistence map”, respectively a different instance of the “inverse problem” of the “persistence map”. These names refer to the fact that merge trees and barcodes 123 On merge trees and discrete Morse functions on paths and... are invariants of ﬁltered spaces rather than just spaces. In this context, the name “persistent” became popular due to persistent homology as it appears in topological data analysis. Similar to the authors of Curry (2019) and Curry et al. (2021), we are interested in ﬁnding out what information is lost by considering our invariant at hand, the induced merge tree, instead of the given data, in our case a discrete Morse function, and how this information might be re-obtained. Such knowledge might be helpful to investigate the space of merge trees and the space of discrete Morse functions in future work. Furthermore, a good understanding of the ﬁber of the persistence map is useful for topological data analysis because it hints at features which might be lost due to the chosen invariant. Moreover, insights about the inverse problem might be helpful to enhance the chosen invariant in a way such that it preserves certain desired features of the data set. We respond to an open question asked in Johnson and Scoville (2022) by showing that every merge tree is represented by a discrete Morse function (dMf). In particular, for any given merge tree we construct a dMf on a path as a representative of the isomorphism class deﬁned by said merge tree: ∼ ∼ Theorem 5.5 Let T be a merge tree. Then there is a path P such that T = M (P, f ) = io M (P, f ) holds as merge trees where f denotes the induced index-ordered dMf sc io (Deﬁnition 3.20) and f denotes the sublevel-connected dMf (Deﬁnition 4.5) on P. sc In particular, the discrete Morse function from Theorem 5.5 can be chosen to be index-ordered (Deﬁnition 2.1) or sublevel-connected (Deﬁnition 2.31). The main tool for the construction is the corresponding Morse order (Deﬁnition 3.3), that is, the index Morse order (Deﬁnition 3.3) or the sublevel-connected Morse order (Deﬁnition 2.31) on the nodes of a given merge tree T . The index Morse order deﬁnes leaf nodes to be strictly less than inner nodes. Among leaf nodes and among inner nodes, the index Morse order is deﬁned by using a twisted version of length- lexicographical order on the set of path words (Lemma 3.16) that correspond to the respective nodes. The path words are deﬁned by the chirality of the nodes of the shortest path from the root to the corresponding node. For the sublevel-connected Morse order (Deﬁnition 4.1) we do not artiﬁcially distinguish between leaf nodes and inner nodes. We use the index Morse order (Deﬁnition 3.3) to deﬁne the index Morse labeling (Deﬁnition 3.7) on the nodes of T . Together with the simplex order (Deﬁnition 3.11), which establishes a correspondence (Remark 3.18) between the nodes of T and the simplices of a path P, the index Morse labeling deﬁnes the induced index-ordered discrete Morse function on said path P. In Sect. 2.2 we introduce several kinds of equivalence relations on the sets of discrete Morse functions with only critical cells on paths and trees. These equivalence relations allow us to identify equivalence classes of discrete Morse functions with isomorphism classes of Morse labeled merge trees: Theorem 5.4 The induced labeled merge tree M (_ , _) and the induced dMf deﬁne crit maps M (_ , _) : DM F ← → MlT : that are inverse to each other in the sense that: (1) For a dMf (P, f ) with only critical cells, the dMf (M (P, f ), λ ) is symmetry- equivalent to (P, f ), and 123 J. Brüggemann (2) For an Ml tree (T ,λ), the Ml tree M (T , f ) is isomorphic to (T ,λ). Theorem 5.6 The induced labeled merge tree M (_ , _) and the induced dMf deﬁne crit maps M (_ , _) : DM F ← → MlT : that are inverse to each other in the sense that: (1) For any dMf (X , f ) with only critical cells, the dMf (M (X , f ), λ ) is cm- equivalent to (X , f ), and (2) For any Ml tree (T ,λ), the Ml tree M (T , f ) is isomorphic to (T ,λ). The construction of the discrete Morse function induced by a Morse labeling is similar to the construction of functions on the interval in Curry (2019). In particular, Theorem 5.4 is very similar to the result (Curry 2019, Prop 6.11). The use of Morse labelings in this work basically plays the role of the function π : T → R from Curry (2019). Moreover, the simplex order is almost the same as the use of chirality in Curry (2019, Lem 6.4). But in this work, Morse orders, and in turn Morse labelings, have to satisfy a certain compatibility with the chirality, that is, property (2) of Deﬁnition 2.17. The notion of merge trees we use originates from Johnson and Scoville (2022, Def 5) and differs from the one used in Curry (2019): A priori, merge trees T in the sense of Johnson and Scoville (2022) do not carry a height function T → R as part of their data. Instead, the two children of each node have a chirality assigned to them as part of the tree’s data. This means that for any two child nodes of the same parent node, it is speciﬁed as part of data which is the right and which is the left child. This version of chirality is also canonically assigned to merge trees induced by discrete Morse functions. In contrast, the chirality of chiral merge trees in the sense of Curry (2019) arises from a chosen orientation on the interval. We obtain a similar correspondence between the chirality of merge trees and orientations on paths using the simplex order, Deﬁnition 3.11. Apart from these differences, the notion of merge trees in the sense of Johnson and Scoville (2022) is closely related to the one from Curry (2019). Chirality in the sense of Johnson and Scoville (2022) is a speciﬁc version of the notion of chirality used in Curry (2019). In order to see this, we show that the construction of the merge tree M (X , f ) induced by a discrete Morse function f in the sense of Johnson and Scoville (2022) can be modiﬁed, see Proposition 2.20, to obtain a function T → R from f , similarly to Curry (2019). This gives rise to the notion of Morse labelings, Deﬁnition 2.19, and Morse orders, Deﬁnition 3.3. It turns out that the use of chirality in Johnson and Scoville (2022) assumes a certain compatibility between Morse orders and the simplex order, whereas the use of chirality in Curry (2019) does not. As a result, the induced merge tree in the sense of Curry (2019) distinguishes between symmetry equivalences, Deﬁnition 2.42, whereas the induced merge tree in the sense of Johnson and Scoville (2022) identiﬁes symmetry-equivalent discrete Morse functions with each other, see Proposition 2.48. We discuss this in a bit more detail at the end of Sect. 5. In said discussion, we mention the notion of CMl trees, see Deﬁnition 5.9, which is as objects basically the same as the notion of merge trees from Curry et al. (2021,Def 2.2). However, the notion of combinatorial equivalence of labeled merge trees from Curry et al. (2021, Def 2.6) corresponds to a non-chiral version of shufﬂe equivalence 123 On merge trees and discrete Morse functions on paths and... Deﬁnition 2.24 rather than an equivalence of the induced persistent set as in Curry (2019, 5.1), which is more similar to an isomorphism of Ml trees Deﬁnition 2.23.The chiral merge trees from Baryshnikov (2019, Def 2.1) are as objects also very similar to the chiral merge trees from Curry (2019) and, thus, differ similarly from our notion of labeled merge trees. The aforementioned versions of labeled merge trees all have in common that their labelings need to be compatible with some other data inherent to the merge tree. In contrast to that, the labelings from Yan et al. (2019) can be quite arbitrary and might even assign multiple labels to a single node. Hence, our Ml trees a priori seem to be unrelated to the notion of labeled merge trees from Yan et al. (2019). 2 Preliminaries We consider discrete Morse functions (dMf) on trees. Recall that trees are ﬁnite acyclic simple graphs. Furthermore, simple graphs are 1-dimensional simplicial complexes. Where feasible, we introduce the preliminaries in the broader generality they are usually deﬁned in, rather than in the lesser generality we actually need for this work. We adapt most notations and conventions from Johnson and Scoville (2022). For simplicity, we assume all trees in this article to be non-empty. Similar to Johnson and Scoville (2022), we assume the dMfs to fulﬁll certain generic properties. In detail this means the following: Deﬁnition 2.1 Let X be a simplicial complex. A map f : X → R is called a discrete Morse function (dMf) if it fulﬁlls the following properties for any pair of simplices σ, τ ∈ X: (i) σ ⊆ τ ⇒ f (σ ) ≤ f (τ ) (weakly increasing) (ii) f is at most 2 − 1 (iii) f (σ ) = f (τ ) ⇒ (σ ⊂ τ ∨ τ ⊂ σ) (matching) Simplices on which f is 1 − 1 are called critical. Simplices which belong to the preimage of the same value are called matched. The set of critical simplices is denoted by Cr( f ). Values of critical simplices under f are called critical values of f .AdMf is called index-ordered if for arbitrary critical simplices σ, τ the following holds: If dim(σ ) is smaller than dim(τ ), then f (σ ) < f (τ ) holds. Remark 2.2 The deﬁnition given above is not the most general deﬁnition of dMfs but rather assumes several generic properties. This means that any dMf in the sense of Forman (1998) can be modiﬁed by a Forman equivalence (see Johnson and Scoville, 2022, Def 4.1) to fulﬁll these properties, that is, without changing the induced Morse matching. As usual in the context of dMfs, we write f : X → R although the map f is actually deﬁned on the face poset of X. In Nanda et al. (2018), a similar generic property is used to analyze ﬂow paths induced by dMfs. The notion of faithful dMfs as deﬁned in Nanda et al. (2018,Def 2.9) is almost the same as index-ordered dMfs in this article. The only difference is that for index-ordered dMfs matched cells have the same value, whereas for faithful 123 J. Brüggemann dMfs the values of the matched boundary simplices are higher than the values on the corresponding matched co-boundary simplices. Furthermore, since simple graphs and in particular trees are examples of simplicial complexes, the deﬁnition of dMfs can be applied to them as well. Remark 2.3 Because f maps Cr( f ) injectively into a totally ordered set, it induces a total order on Cr( f ). We refer to this induced order whenever we speak of simplices being ordered by f . Notation 2.4 We use the following conventions regarding notation: • We depict dMfs on graphs by labeling the graph with the values of the dMf. • Let G be a graph and let v be a node of G.By G[v] we denote the connected component of G which contains v. Deﬁnition 2.5 • Let X be a simplicial complex, f : X → R a dMf and a ∈ R.The f f sublevel complex of level a, denoted by X , is deﬁned by X := {σ ∈ X | f (σ ) ≤ a a a}. If the referred dMf f is clear from the context, we drop the superscript f from the notation. • The ordered critical values c < c < ··· < c induce a chain of sublevel 0 1 m f f f f complexes X X ··· X . Within this chain, we refer by X to the c c c 0 1 m c −ε complex that immediately precedes X . Remark 2.6 The given deﬁnition of sublevel complexes differs from the standard one used in the literature. We make use of the fact that a dMf f being weakly increasing implies that X as deﬁned above is already a subcomplex of X. If we wanted to consider the general deﬁnition of dMfs as introduced in Forman (1998), we would have to work with the smallest supercomplex of X in X instead. Taking the smallest supercomplex corresponds to additionally including all faces of simplices of X to make X a simplicial complex. Lemma 2.7 Let X be a ﬁnite simplicial complex and let f : X → R be a dMf. Then f attains its minimum on a critical 0-simplex. Furthermore, the statement also holds for the restriction to any connected component of sublevel complexes. Sketch of Proof The statement follows by a proof by contradiction and properties (i) and (ii) of Deﬁnition 2.1. Remark 2.8 The analogous statement for the maximum of a dMf f on arbitrary 1- simplices is false, as the following example shows: 3 3 0 2 1 • • • Here, the maximum is attained on a pair of matched simplices. 2.1 Merge trees We brieﬂy recapture preliminaries about merge trees as they are explained in Johnson and Scoville (2022). The basic idea is that merge trees keep track of the chronological 123 On merge trees and discrete Morse functions on paths and... development of the connected components of sublevel sets. We adapt the point of view of Johnson and Scoville (2022), that is, we consider them ‘upside down’. Thus, the children will appear above their parent node. Afterwards we introduce additional structure that dMfs induce on their corresponding merge trees and consider notions of equivalence which arise from that structure. Deﬁnition 2.9 (Merge Tree) A merge tree is a full rooted chiral binary tree T . In detail this means that T is a rooted tree fulﬁlling the properties of being binary and full, and that T has the extra datum of being chiral: Full binary Each node of T has either zero or two children. Chiral Each child node in T carries the extra datum, the so-called chirality,of being a left or a right child. Morphisms of merge trees are morphisms of rooted binary trees which are compatible with the chirality. For rooted trees T we use the notions of subtrees, ancestors and descendants as they are commonly used in computer science. Deﬁnition 2.10 For any node p of T,the descendants of p are deﬁned inductively: A node c is a descendant of p if the parent node of c is a descendant of p or p itself. A subtree of T is a subgraph of T that consists of exactly all of the descendants of some node p of T . For a node p of T we call all nodes which lie on the shortest path between p and the root, including the root, the ancestors of p. Notation 2.11 For an inner node c of T , we denote the left child of c with c and the right child of c with c . We illustrate this notation in the following example: c c l r • • • • c = p Remark 2.12 For full binary trees T with i (T ) inner nodes and l(T ) leaves it is a well-known result that l(T ) = i (T ) + 1 holds. It can be proved inductively. Remark 2.13 The chirality of nodes will either be denoted by labels or indicated implic- itly by embedding the merge tree on the page. Throughout the literature there are different notions of merge trees that are not always distinguished by name or notation. In this work, merge trees do not have explicit weights on edges. Moreover, merge trees in this work a priori do not carry a function to the real numbers. In that way, we dis- tinguish between merge trees and Morse labeled merge trees which will be introduced in Deﬁnition 2.19. We use the chirality to obtain Morse labelings on unlabeled merge trees. This leads to Deﬁnition 3.3. 123 J. Brüggemann Construction 2.14 (Johnson and Scoville 2022, Thm 9) Let X beatreeandlet f : X → R be a dMf. The merge tree induced by f , denoted by M (X , f ) is constructed as follows: Let c < c < ··· < c be the critical values of f that are assigned to 1-simplices. 0 1 m The associated merge tree M (X , f ) is constructed by induction over these critical values in descending order. Furthermore, we label the nodes of M (X , f ) in order to refer to them later. The label of a node n will be denoted by λ(n). For the base case we begin by creating a node M (c ) which corresponds to the critical 1-simplex in X labeled c and setting its label λ(M (c )) to (c , L). m m m For the inductive step, let M (c ) be a node of M (X , f ) that corresponds to a critical 1-simplex between two 0-simplices v and w. Deﬁne λ := max{ f (σ )|σ ∈ X [v],σ critical} and λ := max{ f (σ )|σ ∈ X [w],σ critical}. Two child c −ε w c −ε i i nodes of M (c ) are created, named n and n . Then label the new nodes λ(n ) := λ i λ λ λ v v w v and λ(n ) := λ .Ifmin{ f (σ )|σ ∈ X [v]} < min{ f (σ )|σ ∈ X [w]},we λ w c −ε c −ε w i i assign n the same chirality (L or R) as M (c ) and give n the opposite chirality. λ i λ v w Continue the induction over the rest of the critical 1-simplices. Remark 2.15 By construction, one of the following two cases holds for the labels λ and λ . They might be either critical values lower than c that are assigned to edges or w i critical values that are assigned to nodes. The two labels λ and λ do not necessarily v w belong to the same case. Therefore, the nodes n and n will possibly be denoted as M (c ) and M (c ) for λ λ j k v w some j , k < i in later steps of the induction. In particular, this means that the node which is considered in the ﬁrst instance of the inductive step is c . Remark 2.16 Although the induced merge tree as introduced above comes with a labeling, the labeling is not part of the data of the induced merge tree. This is one of the main differences between merge trees in Johnson and Scoville (2022) and the merge trees in Curry (2019). We consider one way to keep some information provided by the induced labeling on M (X , f ). Deﬁnition 2.17 Let T be a merge tree. We call a total order ≤ on the nodes of T a Morse order if it fulﬁlls the following two properties for any subtree T of T : (1) The restriction ≤ attains its maximum on the root of T . |T (2) The restriction ≤ attains its minimum on the subtree with root p /p if L/R is l r |T the chirality of the root p of T . Moreover, we call a merge tree (T , ≤) together with a Morse order ≤ a Morse-ordered merge tree (Mo tree). Remark 2.18 Assuming property (2) of Deﬁnition 2.17 for every subtree T with root p of T is equivalent to either of the following: • For any subtree T with root p of T , the minimum of ≤ has the same chirality |T as p. • For any subtree T with root p of T , all nodes on the shortest path between p and the minimum of ≤ have the same chirality as p. |T 123 On merge trees and discrete Morse functions on paths and... The equivalence can be proved by an inductive argument over all nodes of the shortest path between p and the minimum. Because Morse orders ≤ deﬁne in particular ﬁnite totally ordered sets, there are unique order-preserving isomorphisms λ : (V (T ), ≤) − →{0, 1,..., i (T )+l(T )−1}⊆ N ⊂ R for each Morse order. Conversely, each injective labeling λ : T → R induces an order ≤ on the nodes of T by usage of the total order on R. Deﬁnition 2.19 For Morse orders ≤ we call the map λ : (V (T ), ≤) →{0, 1,..., i (T ) + l(T ) − 1} the Morse labeling induced by ≤. We call an arbitrary labeling λ : T → R a Morse labeling if it induces a Morse order on T . We call a merge tree (T ,λ) with a Morse labeling λ : T → R a Morse labeled merge tree (Ml tree). For a Mo tree (T , ≤) we call the Ml tree (T ,λ ) the Ml tree induced by (T , ≤). Proposition 2.20 Let f : X → R be a dMf. The labeling which appears in Construc- tion 2.14 induces a Morse order on M (X , f ). Hence, M (X , f ) canonically carries the structure of a Mo tree as well as an Ml tree. Proof It is proved in Johnson and Scoville (2022, Thm 9) that M (X , f ) is a merge tree. We only have to prove that the labeling induces a Morse order. By Remark 2.3 the set Cr( f ) of critical values carries a total order induced by f . Since the critical values of f precisely deﬁne the labeling in Construction 2.14, the labeling induces a total order on the nodes of M (X , f ). It is only left to prove that this order is a Morse order. In the construction, each inner node of M (X , f ) corresponds to a critical 1-simplex and is labeled with the critical value of said critical 1-simplex. Since parent nodes are created before their child nodes are, and since the critical values are considered from highest to lowest, property (1) of Deﬁnition 2.17 is fulﬁlled. The rule in the construction which decides the chirality of the child nodes is exactly the same as property (2) of Deﬁnition 2.17. Hence, it is fulﬁlled by construction. We denote the canonical labeling of M (X , f ) by λ . Remark 2.21 In the aforementioned proof, it becomes clear that both conditions of Deﬁnition 2.17 are necessary for a total order on M (X , f ) to be induced by a dMf f . Morse orders are useful for the construction of dMfs that induce given merge trees T . We will see in Proposition 3.23 that for a total order on an arbitrary merge tree T condition (1) is sufﬁcient for inducing a dMf in the sense of Deﬁnition 3.20 later on. Nonetheless, condition (2) is necessary to ensure that the induced dMf induces the given merge tree T . Example 2.22 We consider the following example of a dMf f : X → R: 123 J. Brüggemann 13 14 10 12 12 2 2 0 1 1 • • • • • • 11 6 • • • • 8 9 7 7 3 5 4 The critical values on edges are: 5 < 6 < 9 < 11 < 14 We now show the construction algorithm of M (X , f ) visually by depicting X on c −ε the left and the part of M (X , f ) that is created up to the step corresponding to c on the right. Start: c = 14: 13 14 10 12 12 2 2 0 1 1 13 10 12 12 2 2 0 1 1 • • • • • • • • • • • • 11 13 • • 11 6 11 6 • • • • • • • • • • 8 9 7 7 3 4 14 8 9 7 7 3 4 14 5 5 c = 11: c = 9: i i 6 8 • • 9 10 10 10 2 2 0 1 1 2 2 0 1 1 • • • • • • • • 11 • • • 11 13 13 • • • • 6 6 • • • • • • • • • • 8 9 7 7 3 5 4 14 8 7 7 3 5 4 14 4 3 c = 5: i • • c = 6: 0 • • 2 2 0 1 1 2 2 0 1 1 • • • • • • • • • • • • 9 10 • • • • • • • • 13 3 4 • • • • 3 5 4 There are no more critical edges left, so the construction of M (X , f ) is ﬁnished. Since there are different notions of merge trees in the literature and since the merge trees in our setting carry a lot of structure, there are multiple possibilities of how to deﬁne equivalences of merge trees. In the remainder of this section, we deﬁne and discuss some versions of equivalence of merge trees. Since merge trees are deﬁned to be chiral rooted binary trees, the obvious notion for isomorphisms of merge trees is isomorphisms of chiral rooted binary trees. In detail, this means bijections between the sets of nodes and the sets of vertices which map the root to the root and are compatible with the chiral child relation. For Mo trees (Deﬁnition 2.17) we have more notions of equivalence. Deﬁnition 2.23 Let (T , ≤) and (T , ≤ ) be Mo trees. An isomorphism of Mo trees (T , ≤) (T , ≤ ) is an order-preserving isomorphism of the underlying merge trees. 123 On merge trees and discrete Morse functions on paths and... Let (T ,λ) and (T ,λ ) be Ml trees. An isomorphism of Ml trees is and isomorphism of the underlying merge trees over R, that is, an isomorphism of merge trees ϕ : T → T such that λ ◦ ϕ = λ. Deﬁnition 2.24 Let (T ,λ) and (T ,λ ) be Ml trees. A shufﬂe equivalence (ϕ, ψ ) : (T ,λ) → (T ,λ ) of Ml trees is a pair of an isomorphism of the underlying merge trees ϕ : T → T and a bijection ψ : R → R such that • ψ ◦ λ = λ ◦ ϕ holds, • The restriction of ψ to values on leaves is order-preserving, and • The restriction of ψ to values on inner nodes is order-preserving. In the special case that the restriction ψ : im(λ) → im(λ ) is an order preserving |im(λ) bijection, we call (ϕ, ψ ) an order equivalence. A shufﬂe equivalence (T , ≤) → (T , ≤ ) between Mo trees is an isomorphism ϕ of the underlying merge trees such that • The restriction of ϕ to leaf nodes is order-preserving, and • The restriction of ϕ to inner nodes is order-preserving. Remark 2.25 The name of shufﬂe equivalences hints at the fact that two given total orders, one total order on the leaves, and another total order on the inner nodes, might be combined to produce a total order on all nodes in different ways, a bit like shufﬂing cards. Shufﬂe equivalence checks if two Morse orders arise from the same underlying orders by different ways of shufﬂing. But the necessity of ranking ancestors higher than descendants and being compatible with the chirality prevents arbitrary ways of shufﬂing two given orders on the leaves and inner nodes from producing Morse orders. Shufﬂe equivalences induce by deﬁnition isomorphisms on the underlying merge trees. We now make the relationship between Mo trees and Ml trees precise. Proposition 2.26 The Morse labeling induced by a Morse order and the order induced by a Morse labeling deﬁne inverse bijections iMl : MoT /∼ ← → MlT / : iMo where = ∼ ∼ denotes order equivalence. Proof Let (T , ≤) be a Mo tree. It is immediate that (T ,λ ) has the property that λ ≤ ≤ induces ≤ as its induced order on T . Thus, the composition iMo ◦ iMl is the identity on MoT . Let (T ,λ) be an Ml tree. By deﬁnition, the labeling λ induces a Morse order ≤ on T which makes (T , ≤ ) a Mo tree. Since the induced Morse labeling λ by λ ≤ construction induces ≤ as its induced order, it follows that (T ,λ) and (T ,λ ) are λ ≤ order equivalent. Corollary 2.27 The induced Morse order iMo and the induced Morse labeling iMl induce a bijection between shufﬂe equivalences of Mo trees and shufﬂe equivalences of Ml trees. Proof The assignment iMl maps shufﬂe equivalences of Mo trees to shufﬂe equiva- lences of Ml trees by Deﬁnition 2.24. 123 J. Brüggemann Let λ : T → R and λ : T → R be shufﬂe-equivalent Morse labelings and let (ϕ, ψ ) be the corresponding shufﬂe equivalence. Then by Deﬁnition 2.19 the map iMo(ϕ, ψ ) = ϕ : (T , ≤ ) → (T , ≤ ) has the property that the restriction of ϕ to leaf λ λ nodes is order-preserving, and the restriction of ϕ to inner nodes is order-preserving. Hence, ϕ = iMo(ϕ, ψ ) is a shufﬂe equivalence of Mo trees. Remark 2.28 In particular, the aforementioned proposition and corollary mean that two Mo trees are isomorphic (respectively shufﬂe equivalent) if and only if the cor- responding Ml trees are order equivalent (respectively shufﬂe equivalent) and vice versa. 2.2 Generic properties and equivalences of DMFs In this subsection, we will take a closer look at generic properties that dMfs can be assumed to have. Furthermore we consider some notions of equivalences between dMfs. A ﬁrst example of a generic property is the notion of index-ordered dMfs as deﬁned above. It is inspired by the eponymous notion from the smooth case. We use index- ordered dMfs in order to distinguish critical simplices by their dimension because merge trees have the same property: Critical 0-simplices appear as leaves whereas critical 1-simplices appear as inner nodes of the induced merge tree (see Construction 2.14). Thus, index-ordered dMfs seem to be especially suitable for working with merge trees. Nonetheless, index-ordered dMfs are not compatible with the structure of rooted subtrees. In detail, consider the following: Remark 2.29 Let f : X → R be an index-ordered dMf on a tree such that the following holds: The tree X has a critical 1-simplex σ such that the corresponding inner node p in M (X , f ) has two inner nodes c and c as children. Then the image of f on at least one of the connected components corresponding to c or c is not an interval in f (Cr( f )). Example 2.30 The following is a small example: (X , f ) M (X , f ) 0 1 3 2 • • • • 4 5 0 4 1 6 2 5 3 • • • • • • Neither the subtree with root labeled 4, nor the subtree with root labeled 5 is labeled with an interval in f (Cr( f )) ⊆ R. Still, we can assume compatibility with the structure of rooted subtrees as a property: 123 On merge trees and discrete Morse functions on paths and... Deﬁnition 2.31 Let f : X → R be a dMf. The function f is called sublevel-connected if for all critical 1-simplices v the set f (X [v]) is an interval in f (Cr( f )). f (v) Remark 2.32 Since both ‘index-ordered’ and ‘sublevel-connected’ are properties that only rely on the values of f on critical simplices, they can easily be arranged without changing the partial matching if the tree X is ﬁnite. It is also possible to do this without changing the induced merge tree. One way to obtain a sublevel-connected dMf would be to choose a collapsing order for the induced matching such that the respective connected components of sublevel sets correspond to intervals in said collapsing order. But as seen in Remark 2.29, the two properties are in most cases mutually exclusive. Example 2.33 Here is a possibility how to modify the dMf from the previous example in order to make it sublevel-connected without changing the induced merge tree: (X , f ) M (X , f ) 0 1 4 3 • • • • 2 5 0 2 1 6 3 5 4 • • • • • • Since dMfs can be modiﬁed to fulﬁll either of the two properties, one can always choose the one which is more convenient for the task at hand. Thus, we give two different constructions in this work, one for each property. We recall that by Remark 2.3 each dMf f : X → R induces an order on the 0- simplices of X and on the 1-simplices of X, respectively. This yields the following deﬁnition, which induces a merge-tree-invariant notion of equivalence between dMfs. Deﬁnition 2.34 Let f : X → R and g : X → R be dMfs on a tree X. We call f and g shufﬂe-equivalent if they have the same critical simplices and if they induce the same order on the critical 0-simplices as well as the same order on the critical 1-simplices. Let (X , f ) and (X , f ) be two dMfs on trees. A shufﬂe equivalence (ϕ, ψ ) : f → f between f and f consists of a simplicial map ϕ : X → X and a bijection ψ : R → R such that • ψ ◦ f = f ◦ ϕ, • ϕ : Cr( f ) → Cr( f ) is a bijection, |Cr( f ) • The restriction of ψ to values on critical 0-simplices is order preserving, and • The restriction of ψ to values on critical 1-simplices is order preserving. In the special case that the restriction ψ : Cr( f ) → Cr( f ) is an order preserving |Cr( f ) bijection, we call (ϕ, ψ ) an order equivalence. Remark 2.35 It is immediate that shufﬂe equivalence of dMfs is an equivalence rela- tion. The name is inspired analogously as for the eponymous notion for Mo trees and Ml trees. Shufﬂe equivalence checks if two dMfs arise from the same underlying orders by different ways of shufﬂing. Nonetheless not all ways of shufﬂing given orders on 123 J. Brüggemann the critical 0-simplices and critical 1-simplices produce a dMf because dMfs have to be weakly increasing. Furthermore, shufﬂe equivalence, and in particular order equivalence, also considers dMfs to be equivalent if they only differ by scaling because a different scaling does not change the induced orders on simplices. We split the deﬁnition of shufﬂe equivalences in two steps to simplify the proofs of the following propositions. It is immediate that for two dMfs on the same tree X there is a shufﬂe equivalence between them if and only if they are shufﬂe equivalent. Proposition 2.36 Let X be a tree and let f : X → R and g : X → R be two shufﬂe- equivalent dMfs. Then M (X , f ) and M (X , g) are isomorphic as merge trees. The following two lemmas will be helpful for the proof of the proposition: Lemma 2.37 Let X be a tree and let f : X → R be a dMf such that X has at least one critical 1-simplex. Then the function f attains its maximum on a critical |Cr( f ) 1-simplex. Sketch of Proof Backtracking gradient paths, see Forman (1998, Def 8.4), as long as possible leads to a local maximum which turns out to be a critical 1-simplex. Lemma 2.38 Let X be a tree and let f : X → R and g : X → R be two shufﬂe- equivalent dMfs. We denote the critical 1-simplices of f and g by c < c < ··· < c 0 1 n where < denotes the ordering induced by f or g, respectively. Then the connected components X [c ] of sublevel complexes contain the same critical simplices as f (c ) X [c ] for all j < i. g(c ) Sketch of Proof First we observe that restrictions of dMfs on trees to connected com- ponents of sublevel complexes are again dMfs on trees. With help of Lemma 2.37, it can be proved inductively that in the construction of M (X , f ) and M (X , g) the same critical 1-simplices are considered in the same order. The statement then follows inductively. Proof of Proposition 2.36 We consider the construction of the induced merge tree (see Construction 2.14) and prove inductively the slightly stronger result that both functions yield isomorphic merge trees at every step of the construction. This implies that f and g induce isomorphic merge trees. Since f and g impose the same order on the set of critical 1-simplices, the construc- tion algorithm considers the same critical 1-simplices during the same steps for both functions. This already proves the base case. In particular, this means that the created root node corresponds to the same critical 1-simplex for both functions. Although the label of the root node might be different for the two dMfs, it does not affect the isomorphism type of the induced merge tree because the labeling is not part of the data of merge trees. For the inductive step, we observe that in every step of the construction we consider f g a connected component of sublevel complexes X [c ]/X [c ] that contains at j j f (c ) g(c ) i i least one critical 1-simplex, namely the one with the highest remaining critical value 123 On merge trees and discrete Morse functions on paths and... c . Thus, by Lemma 2.38 in each step of the construction, the same critical simplices occur. Assume we are at the step that considers the critical 1-simplex c . For the two new nodes which are created in the inductive step, two pieces of information are important for the isomorphism type of the induced merge tree, namely the chirality of the new nodes and which critical simplices the new nodes correspond to. The chirality of the new nodes affects the isomorphism type of the induced merge tree directly. The critical simplex corresponding to a child node c decides which connected component of the respective sublevel complex is used to build the subtree with root c and at which point said connected component will be subdivided next. Both pieces of information are deﬁned by the two connected components that belong to the boundary 0-simplices of c . The two child nodes correspond to the critical simplices with the highest critical values. There are three cases: (1) Both connected components contain at least one critical 1-simplex c . (2) One connected component contains at least one critical 1-simplex c whereas the other one only contains one critical 0-simplex c. (3) Each of the two connected components contains only one critical 0-simplex c. It follows by Lemma 2.37 that in case (1) the corresponding 1-simplices with the highest critical values are critical 1-simplices c . In case (2) the same is true for the connected component that contains at least one critical 1-simplex. For the connected components in case (2) and (3) that only contain one critical 0-simplex, respectively, it is true that the critical 0-simplex is the only critical simplex in its corresponding connected component. Thus, the new nodes correspond to the same critical simplices for f and for g because both functions induce the same order on 1-simplices and because connected components only correspond to critical 0-simplices if they are the only critical simplex left in the corresponding connected component. Furthermore, f g connected components X [c]/X [c] that only contain one critical 0-simplex do f (c ) g(c ) i i not have any inﬂuence on the induced merge tree M (X , f )/M (X , g) because their corresponding nodes have already been created during a step that considered a critical 1-simplex with a higher critical value and they are not considered in later steps of the construction. The chirality of the new nodes depends on the minimal values on critical f g simplices of the two respective connected components X [c ]/X [c ] or j j f (c ) g(c ) i i f g X [c]/X [c]. By Lemma 2.7, these minima belong to critical 0-simplices. By f (c ) g(c ) i i assumption, f and g induce the same order on the critical 0-simplices, so the same 0-simplex is minimal with respect to both functions. Thus, f and g assign the same chirality to the new nodes. Remark 2.39 The functions f and g might induce different order relations between 0-simplices and 1-simplices. Therefore, in sublevel complexes that appear during the same step of the construction there might be different connected components that contain only one critical 0-simplex each with respect to the two dMfs. However, those connected components that contain only one critical 0-simplex and no critical 1- simplices do not affect the isomorphism type of the induced merge tree. This is because 123 J. Brüggemann those connected components correspond to leaves of the merge tree which have already been created during the step that considered the critical 1-simplex between said con- nected components and other connected components. Furthermore, those connected components do not appear in later steps of the construction of the induced merge tree because they do not contain any critical 1-simplices. Proposition 2.40 Shufﬂe equivalences of dMfs induce shufﬂe equivalences of the induced Ml trees. Moreover, order equivalences of dMfs induce order equivalences of the induced Ml trees. Sketch of Proof Since ϕ is bijective on critical simplices and simplicial, it follows that ϕ induces a bijection between connected components of sublevel complexes. With this, it follows analogously to the proof of Proposition 2.36 that M (X , f ) = M (X , f ) holds. The proof that the induced Morse labelings are shufﬂe equivalent is straightforward and only uses that the restrictions of ψ to 0-simplices and to 1-simplices are order preserving, and the compatibility between ϕ, ψ, f and f . Remark 2.41 The criterion from Proposition 2.36 for merge tree equivalence is sufﬁ- cient but not necessary, as the following example shows: (X , f ) (X , g) M (X , f ) M (X , g) 0 1 • • 0 2 1 1 2 0 • • • • The two dMfs f and g induce inverse orders on the two 0-simplices. Nonetheless, f and g induce the same unlabeled merge tree. This remark leads us to yet another kind of equivalence relation between dMfs that arises from symmetries of sublevel complexes. In order to make this notion of sym- metry precise, we need some preparations. Deﬁnition 2.42 Let f : X → R be a dMf on a tree. For each non-empty connected f f f component X [v] of a sublevel complex X we denote by Aut(X [v]) the group of c c c f f simplicial automorphisms of X [v]. For each a ∈ Aut(X [v]) there is an extension c c to a self-bijection X → X by the identity. The group Aut(X [v]) is deﬁned to be the group of said extensions of elements of Aut(X [v]) by the identity. We consider Aut(X [v]) as a subgroup of the group of all self-bijections of X. The total order f f on Cr( f ) induced by f induces chains Aut(X [v]) ⊂ Aut(X [v]) ⊂ ... of inclu- c c 0 1 f f sions of subgroups. Moreover, we have inclusions Aut(X [v]) ⊂ Aut(X [v]) = c c i j f f Aut(X [w]) ⊃ Aut(X [w]) if v and w are in different connected components of c c j i some sublevel complex X that merge together in some other sublevel complex X for j > i. We deﬁne the sublevel automorphism group of (X , f ), denoted by Aut (X , f ), to be the subgroup generated by Aut(X [v]). We call the sl c c∈Cr( f ),v∈X elements of Aut (X , f ) sublevel automorphisms. sl 123 On merge trees and discrete Morse functions on paths and... Remark 2.43 Even though sublevel automorphisms are built out of simplicial automor- phisms of connected components X [v] of sublevel complexes, they are in general not simplicial maps X → X. To be precise, if a simplicial automorphism of X [v] was used to construct a sublevel automorphism a ∈ Aut (X , f ), then a will fail to sl be simplicial at the boundary of X [v]⊂ X. Proposition 2.44 Let f : X → R be a dMf on a tree and let a ∈ Aut (X , f ) be a sl sublevel automorphism. Then f ∗ a deﬁned by f ∗ a(σ ) := f (a(σ )) is a dMf on X. Moreover, this deﬁnes a right group action of Aut (X , f ) on the set of dMfs on X. sl Sketch of Proof The proof that f ∗ a is a dMf is straightforward and the compatibility of the group action follows directly by associativity of the composition of maps. Remark 2.45 Since automorphisms of simplicial complexes preserve the dimension of simplices, the action of Aut (X , f ) on the set of dMfs on a tree X preserves the sl properties of being index-ordered or sublevel-connected. Deﬁnition 2.46 Let f : X → R and g : X → R be dMfs on a tree X. We call f and f g g sublevel-equivalent if Cr( f ) = Cr(g) and X = X for all c ∈ Cr( f ) = Cr(g). c c If additionally g = f ∗ a holds for a sublevel automorphism a ∈ Aut (X , f ) = sl Aut (X , g), then we call f and g symmetry-equivalent. We call the map a a symmetry sl equivalence from f to g. We call two dMfs f : X → R and g : Y → R symmetry-equivalent if there is a simplicial isomorphism ϕ : X → Y such that f and g ◦ ϕ are symmetry-equivalent. Example 2.47 We give a list of some symmetry-equivalent dMfs on a path with four vertices. Here we denote the sublevel equivalence induced by the reﬂection of the connected component of the sublevel complex of level k by a [k]: 0 4 1 5 2 6 3 a [6] 3 6 2 5 1 4 0 • • • • • • • • a [5] 3 6 0 4 1 5 2 a [4] 3 6 1 4 0 5 2 5 4 • • • • • • • • Proposition 2.48 Let f : X → R and g : X → R be symmetry-equivalent dMfs on a tree X. Then M (X , f ) and M (X , g) are isomorphic as Ml trees. Sketch of Proof The proposition can be proved by induction over the level c of the sublevel automorphisms that the given symmetry equivalence consists of. We check that in each step the single sublevel automorphism a of the connected component X [σ ] with the 1-simplex σ labeled c in X only affects steps of the construction of c c the induced Ml tree that consider simplices of X [σ ]. Moreover, it is straightforward to prove that in these steps, the created nodes and their induced Morse labels are the same as without the application of a. Remark 2.49 Sublevel automorphisms of dMfs on paths only consist of reﬂections of the corresponding connected component of a subcomplex. When such a connected component of a sublevel complex of a critical level c is considered during the con- struction of the induced Ml tree, the reﬂection of the connected component only causes 123 J. Brüggemann the two new parts that are obtained by considering a slightly lower level c − ε to appear as their mirror images. In particular, the given dMf attains the same values on the two new parts as before. Hence, the two parts that appear are simplicially isomorphic to the ones that appear without application of the reﬂection. Deﬁnition 2.50 Let (X , f ) and (X , f ) be dMfs on trees. A component-merge equiv- alence (cm equivalence) of level a is a bijection ϕ : X → X such that one of the following, not necessarily exclusive, cases holds: (1) ϕ is a symmetry equivalence. (2) ϕ fulﬁlls the following: • f ◦ ϕ = f , • ϕ induces a bijection between the sets of connected components of sublevel complexes such that each restriction ϕ : X [v]→ X [ϕ(v)] is a |X [v] a−ε a−ε a−ε cm equivalence of some level b < a, and • The edge σ ∈ X with f (σ ) = a merges the two connected components X [v ] and X [v ] in X [v ]= X [v ] if and only if the edge ϕ(σ ) merges a−ε 1 a−ε 2 a 1 a 2 the two connected components X [ϕ(v )] and X [ϕ(v )] in X [ϕ(v )]= 1 2 1 a−ε a−ε a X [ϕ(v )]. If ϕ fulﬁlls property (2) but not property (1), we call ϕ non-trivial. Example 2.51 We give an example of two cm-equivalent dMfs on trees. The non-trivial cm equivalence from the left-hand-side to the right-hand-side consists of a symmetry equivalence of level 5 and the attachment of the edge labeled 6 between the vertices labeled 1 and 3 rather than 2 and 3. That is, it is a cm-equivalence of level 6. 4 5 6 5 4 • • • • • • • 0 1 2 3 2 1 0 Proposition 2.52 Cm equivalent dMfs on trees induce isomorphic Ml trees. Proof Let ϕ : (X , f ) → (X , f ) be a cm equivalence. By property (ii) of Deﬁnition 2.1, at most one non-trivial cm equivalence of level a can occur for any level a because there is at most one edge labeled a in (X , f ), (X , f ), respectively. Thus, we can decompose any cm equivalence into a sequence (ϕ ) of non-trivial cm equivalences a a of decreasing levels such that each ϕ only changes the attachment of the single edge σ with f (σ ) = a and acts as a symmetry equivalence on the rest of path and dMf. It sufﬁces to consider a single level a because the statement then follows by induction from highest to lowest over all levels a. For such a non-trivial cm equivalence ϕ we consider the step of the construction of the induced Ml trees that considers the edge σ with f (σ ) = a and the edge ϕ(σ ).We inductively assume that ϕ induces an isomorphism of induced Ml trees everywhere outside the subtrees corresponding to the two connected components of X that a−ε are merged by the edge σ with f (σ ) = a. That is, on the rest of M (X , f ) the map 123 On merge trees and discrete Morse functions on paths and... M (ϕ) is a bijection compatible with the chiral child relation onto M (X , f ) except for the subtrees of M (X , f ) which correspond to the connected components of X a−ε which are merged by the edge ϕ(σ ). Since the map ϕ is compatible with the dMfs and f f because it restricts to a cm equivalence X → X , the dMf f attains the same a−ε a−ε minima and maxima on the two relevant connected components of X as f does a−ε on their counterparts of X via ϕ. Since Construction 2.14 only considers which a−ε two connected components are merged by the considered edge, it makes no difference for the isomorphism type of the induced Ml trees that σ in general merges the two connected components of X at vertices that do not correspond via ϕ to the ones a−ε adjacent to ϕ(σ ) in X . Thus, the construction of the induced Ml tree produces a−ε nodes with the same chirality and label for both induced Ml trees in the steps that f f consider σ, ϕ(σ ), respectively. By assumption, the restriction ϕ f : X → X a−ε a−ε a−ε is a symmetry equivalence, so the isomorphism of Ml trees extends to the subtrees that correspond to the respective connected components. Proposition 2.53 Let (X , f ) be a dMf on a tree. There is a dMf on a path (P, f ) such that (X , f ) is cm-equivalent to (P, f ). Sketch of Proof A suitable cm equivalence can be constructed inductively by re- attaching 1-simplices of level a that would become the third 1-simplex incident to some 0-simplex in X . Remark 2.54 The way we deﬁned cm equivalence makes it a generalization of sym- metry equivalence. In fact, cm equivalences are the same as symmetry equivalences, i.e. they are always trivial, if we restrict ourselves to dMfs on paths: Without loss of generality, cm equivalences of some level a of a dMf on a path (P, f ) describe all different possibilities of how two glue two paths together with a new edge in order to obtain a path again. This means that the edge labeled a can only be adjacent to the vertices that are adjacent to less than two edges, respectively, of the two old paths in P . Thus, there are at most four possibilities for the two vertices which may a−ε be adjacent to the edge labeled a. All of these possibilities result in dMfs which are related to each other by reﬂections of the original two paths in P . Hence, they are a−ε all symmetry-equivalent to each other. 3 Construction of the induced index-ordered DMF We address the inverse question: For any given merge tree T , is there a discrete Morse function f on a path P such that M (P, f ) = T ? We answer this question afﬁrmatively by presenting an explicit construction of P and two possible choices for f . The basic idea for the construction is to reverse-engineer the construction of the induced merge tree from Construction 2.14. To start with the index-ordered case, we deﬁne two different orders on T.First we deﬁne a Morse order on T , which we call the index Morse order. Afterwards, we deﬁne the simplex order on the nodes of T , which we use to turn the Morse labeling induced 123 J. Brüggemann by the index Morse order into a dMf on P. In Sect. 4 we will present an alternative dMf which represents T , namely the sublevel-connected dMf. We will discuss in Sect. 5 to what extent the constructed dMf is a unique represen- tative for T . 3.1 The index Morse order To deﬁne the index Morse order, we ﬁrst observe that every node a of T is uniquely determined by the shortest path from the root to a. We recall that the depth of T is the maximal length of any path in T that appears as the shortest path from the root to a leaf. Because T is chiral, we can identify such shortest paths with certain words: Deﬁnition 3.1 Let T be a merge tree of depth n and let a be a node of T.The path n+1 word corresponding to a is a word a a ... a ∈{L, R, _} where _ denotes the 0 1 n empty letter. If a is of depth k, the letters a ... a are given by the chirality of the 0 k nodes belonging to the shortest path from the root to a. The letters a ... a are then k+1 n empty. Remark 3.2 Let a, b be nodes of a merge tree T and let a a ... a be the path word 0 1 n corresponding to a and b b ... b be the path word corresponding to b. Then the 0 1 n equation a = b = L always holds because we consider paths that begin at the 0 0 root. Because of a = b = L and because we consider ﬁnite trees, there is always a 0 0 maximal k ∈ N such that a = b holds for all i ≤ k. Furthermore, the last non-empty i i letter of a path word is always the chirality of the considered node. We now deﬁne the index Morse order, which will produce an index-ordered dMf on P afterwards. Deﬁnition 3.3 Let T be a merge tree. We deﬁne the index Morse order ≤ on the io nodes of T as follows: Let a and b be arbitrary nodes of T.If a is a leaf node and b is an inner node, then we deﬁne a ≤ b. If either both a and b are leaf nodes or both a and b are inner io nodes, we consider the following: Let a a ... a be the path word corresponding to a and b b ... b the path word 0 1 n 0 1 n corresponding to b. Furthermore, let k ∈ N be maximal such that a = b for all i ≤ k. i i If a = b = L/R we deﬁne a ≤ b if and only if one of the following cases hold: k k io (a) a = L and b = R/a = R and b = L k+1 k+1 k+1 k+1 (b) b = _ k+1 (c) a = b (⇔ k = n) The index Morse order is tailor-made to induce an index-ordered dMf later on. Nonetheless, we will see in Example 5.2 that it is in general not the only Morse order which induces an index-ordered dMf. In Sect. 4 we will introduce a different, perhaps more natural, Morse order that is more closely related to the sublevel ﬁltration of the induced dMf. But for now we consider an example of the index Morse order and prove that ≤ is actually is a Morse order. io 123 On merge trees and discrete Morse functions on paths and... Example 3.4 We consider the following merge tree T : • • LL RL LL RR • • • • LLL_ LL R_ LRL_ LRR_ • • LL__ LR__ L___ The path words are written underneath their corresponding nodes. The index Morse order produces the following chain of inequalities where we denote the nodes by their corresponding path words: LLL_ LL RR LL RL LRR_ LRL_ LL R_ LL__ LR__ L___ The inequalities from LLL_to LRL_ arise from the path words of the leaf nodes. The inequality LRL_ LL R_ holds because the node corresponding to LRL_is a leaf node and the node corresponding to LL R_ is an inner node. The inequalities from LL R_to L___ arise from the path words of the inner nodes. Remark 3.5 By deﬁnition, the root node is always the maximal element of (V (T ), ≤ ). io Furthermore, the leftmost leaf node of T is always the minimal element of (V (T ), ≤ ). io Proposition 3.6 The index Morse order is a Morse order on T . Sketch of Proof The proof is a straightforward application of the deﬁnitions and involves case distinctions corresponding to the cases a), b), and c) from Deﬁnition 3.3. Deﬁnition 3.7 We call the Morse labeling λ : (V (T ), ≤ ) →{0, 1,..., i (T ) + io io l(T ) − 1} induced by the index Morse order, see Deﬁnition 2.19,the index Morse labeling on T . That is, a node c of T is labeled with λ (c). io Example 3.8 The index Morse order from Example 3.4 induces the following index Morse labeling: 2 1 • • 0 5 4 3 • • • • 6 7 • • 123 J. Brüggemann 3.2 The simplex order We now deﬁne the simplex order on the nodes of T . The simplex order will tell us which nodes of T correspond to which simplices of P. Remark 3.9 Let T be a merge tree and let a, b be nodes of T . Because T is in particular a rooted binary tree, there is a unique node p which is a common ancestor of a and b and has no descendants which are common ancestors of a and b. Deﬁnition 3.10 We call the node p from Remark 3.9 the youngest common ancestor of a and b. Deﬁnition 3.11 Let T be a merge tree. We deﬁne the simplex order on V (T ) as follows: For two nodes a and b of T we deﬁne a b if and only if one of following mutually exclusive cases holds, where p denotes the youngest common ancestor of a and b: (1) a is a node of the subtree with root p and b is a node of the subtree with root p . l r (2) a is a node of the subtree with root b (in particular b = p). (3) b is a node of the subtree with root a (in particular a = p). (4) a = b. Proposition 3.12 The simplex order is a total order on the nodes of T . Sketch of Proof of Proposition 3.12 The proof is a bit tedious and consists of many careful case distinctions corresponding to the different cases from Deﬁnition 3.11. Otherwise, the proof is a straightforward application of the deﬁnitions, paired with a contradiction argument here and there. We use the following deﬁnition to make the intuition of leaves being adjacent precise. This allows us to analyze the simplex order further. Deﬁnition 3.13 Let T be a merge tree and let a and b be leaves of T . We call a and b adjacent if one of the following holds: (1) a b and there is no leaf node c of T such that a c b holds. (2) b a and there is no leaf node c of T such that b c a holds. Lemma 3.14 Subtrees of T form chains of cover relations in (V (T ), ). In detail, this means the following: Let p be an inner node of T and let a/b be the leftmost/rightmost leaf of the subtree with root p. Then the nodes of the subtree with root p in T form the chain of cover relations a ≺ ··· ≺ p ≺ ··· ≺ bin (V (T ), ). Moreover, any two adjacent leaves of T have the property that the left one of the two adjacent leaves is covered by the youngest common ancestor of the two, whereas the right one covers the youngest common ancestor. Proof We prove the lemma inductively. Let p be a node of T such that both child nodes of p are leaves. It follows directly by Deﬁnition 3.11 that p covers p and p 123 On merge trees and discrete Morse functions on paths and... covers p . That is, the subtree with root p forms the chain of cover relations a = p ≺ l l p ≺ p = b. If p is an arbitrary inner node, then by the inductive hypothesis the subtree with root p /p forms the chain of cover relations a ≺ ··· ≺ p ≺ ··· ≺ b /a ≺ ··· ≺ l r 1 l 1 2 p ≺ ··· ≺ b where a /a is the leftmost and b /b the rightmost leaf of the subtree r 2 1 2 1 2 with root p /p . Since b /a is a node of the subtree with root p / p ,itfollows by l r 1 2 l r case (2)/(3) of Deﬁnition 3.11 that b ≺ p/p ≺ a holds. For all nodes c of T which 1 2 are not nodes of the subtree with root p, the same case from Deﬁnition 3.11 holds for c and p as for c and b /a . Thus, and because b /a is maximal / minimal in 1 2 1 2 the subtree with root p /p by the inductive assumption, there is no node c such that l r b ≺ c ≺ p/p ≺ c ≺ a holds. In conclusion, p covers b /a covers p. 1 2 1 2 As mentioned before, we will use the simplex order to relate the nodes of T to the simplices of a path P. In order to do that, we now deﬁne a corresponding simplex order on the simplices of P. Deﬁnition 3.15 Let P be a path. There are two 0-simplices p and p in P which 0 1 belong only to one respective 1-simplex. For each simplex σ of P there is a unique shortest path γ from p to σ . We denote the length, that is, the number of simplices, σ 0 of such a path γ by L(γ ).The simplex order on P is deﬁned as follows: For two σ σ simplices σ and τ of P we deﬁne σ τ if and only if L(γ ) ≤ L(γ ). σ τ Lemma 3.16 The simplex order on P is a total order on the simplices of P. Sketch of Proof The proof is straightforward and only uses that P is a path and that the integers are linearly ordered. Remark 3.17 Connected subcomplexes of P correspond to chains of cover relations with respect to the simplex order. Furthermore, any 1-simplex covers its left boundary 0-simplex and is covered by its right boundary 0-simplex. If one visualizes P as being horizontally embedded in a plane such that p is the leftmost 0-simplex of P and p 0 1 is the rightmost 0-simplex of P, then for simplices s, s ∈ P the relation s ≺ s holds if and only if s is left of s . This reminds us of the fact that the simplex order is only deﬁned up to a choice of orientation. Remark 3.18 Let T be a merge tree and let P be a path with i (T ) 1-simplices. Then we have a unique isomorphism φ : (P, ) − → (V (T ), ) of totally ordered sets. The isomorphism φ only depends on the choice of p and p , that is, on a choice of 0 1 orientation on P. Choosing p and p the other way around would reverse the simplex 0 1 order on P. Before we continue with the deﬁnition of the index-ordered dMf, we consider how the simplex order can be used to classify the connected components of sublevel complexes of dMfs on paths (P, f ): Proposition 3.19 Let f : P → N be a dMf on a path P. Then the connected components P [v] of sublevel complexes P of P are precisely maximal sequences c c σ := (s ,...,v,..., s ) of simplices of P such that s ∈ P for all i = 0,..., k and 0 k i c s ≺ ··· ≺ v ≺ ··· ≺ s is a chain of cover relations in (P, ). 0 k Proof The proof is straightforward and uses Remark 3.17 123 J. Brüggemann 3.3 The induced index-ordered DMF Now we explain how the simplex order can be used to construct dMfs on P from Morse orders on T : Deﬁnition 3.20 Let T be a merge tree and P be a path such that the number of 1- simplices is i (T ) and let φ : (P, ) → (V (T ), ) be the isomorphism from Remark 3.18. For a Morse order ≤ and its induced Morse labeling λ we deﬁne a map f : P → N λ 0 by f := λ ◦ φ.The map f is then called the dMf induced by the Morse order ≤ or λ λ the dMf induced by the Morse labeling λ. In particular, the map f := λ ◦ φ induced by the index Morse order is called the io io induced index-ordered dMf . Remark 3.21 Although φ and λ are order-preserving maps with respect to the previ- ously deﬁned total orders, the map f does not respect the simplex order in general. io Since f is supposed to be an index-ordered dMf, it does not need to respect the io simplex order. Because the map f is supposed to be index-ordered, it rather needs io to be compatible with face relation on P, which we will see to be true later on. Example 3.22 The index Morse order from Example 3.4, respectively the index Morse labeling from Example 3.8, produces the following pair (P, f ): io 0 6 2 5 1 8 4 7 3 • • • • • Proposition 3.23 For any given Morse order ≤ on any merge tree T the dMf induced by ≤ is a dMf that has only critical cells. Sketch of Proof The proof is straightforward and uses Lemma 3.14, Remark 3.17, and property (1) of Deﬁnition 2.17. Remark 3.24 The previous proposition proves that Morse orders ≤ on merge trees T always induce dMfs f . It is a priori unclear though whether the induced dMf f λ λ induces the given merge tree T as its induced merge tree M (P, f ). We prove this to be true in Theorem 5.5. Furthermore, condition (1) from Deﬁnition 2.17 is necessary for f to be a dMf, because a violation of (1) between an inner node and a leaf would result in a violation of f being weakly increasing on the corresponding simplices. Before we continue with the sublevel-connected dMf, we consider how the simplex order can be used to improve our understanding of sublevel complexes of dMfs on paths (P, f ) and how they are related to subtrees of T . The condition for this approach to be applicable is that the dMf f is induced by a Morse order ≤ on T as in Deﬁnition 3.20, which we will see to be the general case later on. We will apply this approach to the sublevel-connected case in Sect. 4 where it will be of more importance. Proposition 3.25 Let f : P → N be a dMf on a path P that is induced by a Morse λ 0 order ≤ on T . Then the connected components P [v] of sublevel complexes P of c c (P, f ) induce subtrees of T via φ. 123 On merge trees and discrete Morse functions on paths and... Sketch of Proof It follows by Proposition 3.19 and the deﬁnition of φ in Remark 3.18 that connected components of sublevel complexes P [v] induce maximal chains of cover relations such that the corresponding simplices are of at most level c in (V (T ), ). The next step is to prove that such chains are equal to the subtree with the chain’s maximum as root. The proof that the chain is contained in the subtree is straightforward. The other inclusion can be proved by contradiction, using that a node outside the subtree would contradict the property of being a chain of cover relations. 4 The sublevel-connected DMF As remarked in Sect. 2.2 it might sometimes be more convenient to work with sublevel- connected dMfs rather than with index-ordered dMfs. In this section we introduce a slightly different version of the Morse order from Deﬁnition 3.3 to construct a sublevel- connected dMf which is shufﬂe-equivalent to the induced index-ordered dMf and, hence, induces the same given merge tree. Deﬁnition 4.1 Let T be a merge tree. We deﬁne the sublevel-connected Morse order ≤ on the nodes of T as follows: sc Let a, b be arbitrary nodes of T.Let a a ... a be the path word corresponding to 0 1 n a and b b ... b the path word corresponding to b (see Deﬁnition 3.1). Furthermore, 0 1 n let k ∈ N be maximal such that a = b for all i ≤ k.If a = b = L/R we deﬁne i i k k a ≤ b if and only if one of the following cases hold: sc (a) a = L and b = R/a = R and b = L k+1 k+1 k+1 k+1 (b) b = _ k+1 (c) a = b Remark 4.2 The only difference between the deﬁnition of the index Morse order and the deﬁnition of the sublevel-connected Morse order is that we do not treat leaves and inner nodes differently anymore. Thus, both orders induce the same order on inner nodes and the same order on leaves, which makes the index Morse order and the sublevel-connected Morse order shufﬂe-equivalent. However, the order relation between a leaf and an inner node is in general different then in the index Morse order. Remark 4.3 The fact that the sublevel-connected Morse order is a Morse order can be proved the same way as the corresponding statement Proposition 3.6 for the index Morse order was proved. There are just fewer case distinctions to be made for the sublevel-connected Morse order. Lemma 4.4 Subtrees of T form intervals in (V (T ), ≤ ). sc Sketch of Proof The proof is straightforward and uses the fact that all path words of a subtree T start with the same couple of letters corresponding to the root of T . The induced sublevel-connected labeling λ and the induced sublevel-connected dMf sc f are deﬁned analogously to the index-ordered case: sc 123 J. Brüggemann Deﬁnition 4.5 Let T be a merge tree and P be a path such that the number of 1- simplices is i (T ). We call the Morse labeling λ : (V (T ), ≤ ) →{0, 1,..., i (T ) + sc sc l(T ) − 1} induced by the sublevel-connected Morse order the sublevel-connected Morse labeling on T . The dMf f = λ ◦ φ induced by λ is called the induced sc sc sc sublevel-connected dMf . Example 4.6 Let T be the merge tree from Example 3.4. The sublevel-connected Morse labeling on T and the induced sublevel-connected dMf are given below. 2 1 • • 0 3 6 5 • • • • 4 7 • • 0 4 2 3 1 8 6 7 5 • • • • • There are now two things left to prove: that the map f is indeed a sublevel-connected sc dMf and that it induces the given merge tree T . Proposition 4.7 The induced sublevel-connected dMf f is a sublevel-connected dMf sc that has only critical cells. Proof As a dMf induced by a Morse order, the map f is by Proposition 3.23 adMf sc that has only critical cells. It is left to prove that f is sublevel-connected: sc By Proposition 3.25, the connected components of sublevel complexes of (P, f ) induce subtrees of T via φ. By Lemma 4.4, subtrees of T form intervals in (T , ≤ ). sc The sublevel-connected Morse labeling λ by deﬁnition maps intervals of (T , ≤ ) sc sc to intervals of N . By concatenation of these arguments, it follows that f = λ ◦ φ 0 sc sc maps connected components of sublevel complexes to intervals of N , i.e. the map f 0 sc is sublevel-connected. Theorem 4.8 Let T be a merge tree and let P be a path such that the number of 1-simplices in P is i (T ). Then f and f are shufﬂe-equivalent where f is the io sc sc induced sublevel-connected dMf and f is the induced index-ordered dMf. Thus, io M (P, f ) = M (P, f ) holds as merge trees. sc io Proof By Remark 4.2, the index Morse order and the sublevel-connected Morse order are shufﬂe equivalent. It follows by Corollary 2.27 and Deﬁnition 3.20 the the index-ordered dMf and the sublevel-connected dMf are shufﬂe equivalent. Thus, M (P, f ) = M (P, f ) follows by Proposition 2.36, where f is the induced index- sc io io ordered dMf deﬁned in Deﬁnition 3.20. 5 Relationships between merge trees and DMFs on paths In this section we want to take a look at the bigger picture again and consider how we can relate dMfs on paths and trees to merge trees. In order to do this in a structured way, 123 On merge trees and discrete Morse functions on paths and... we consider the different sets of dMfs and merge trees and relate them to each other by bijections that are compatible with the various notions of equivalence we introduced earlier. Afterwards, we use said bijections in order to prove that the aforementioned dMfs f , Deﬁnition 3.20, and f , Proposition 4.7, both represent the given merge io sc tree. We also relate the sets of dMfs and merge trees mentioned here to the setting of Curry (2019). Remark 5.1 In order to obtain bijections that are compatible with the various notions of equivalence, we restrict ourselves to the case of dMfs for which all simplices are critical. Since the induced merge tree does not take matched cells into account, we would otherwise need to deﬁne a notion of equivalence similar to Forman equivalence (see Johnson and Scoville 2022, Def 4.1) of dMfs that in particular takes simple homotopy equivalences as well as combinatorial aspects of dMfs into account. This could be done by additional pre- and post-composition of the equivalences as we deﬁned them with simple homotopy equivalences that are compatible with the given dMfs. For simplicity, we chose to leave this aspect out of this work. We denote the set of merge trees up to isomorphism by Mer and the set of dMfs crit on paths with only critical simplices up to symmetry equivalence by DM F .It crit follows by Proposition 2.48 that the assignment M (_ , _) is well-deﬁned on DM F . Furthermore, the construction of the induced dMf from Deﬁnition 3.20 extends to a map which we denote by . Since φ is well deﬁned up to a choice of orientation, the map is in particular well deﬁned up to symmetry equivalence. This leaves us with the diagram in Fig. 1. The arrows induced by the index Morse order and the sublevel-connected Morse order are not left-inverse to the forget arrow as the following example shows. We have marked them in red because they are the only arrows that prevent the diagram from commuting completely. Nonetheless, it is obvious that the arrows induced by the two Morse orders are right-inverses of the forgetful arrow. Example 5.2 Consider the following Ml trees and their corresponding Mo trees: (T ,λ) (T ,λ ) 0 1 0 2 • • • • 3 2 3 1 • • • • • • 4 4 It is immediate the (T ,λ) and (T ,λ ) are neither isomorphic nor shufﬂe equiva- M( , ) crit Mer DMF ≤ ≤ forget M( , ) sc io Φ iMl MoT MlT iMo Fig. 1 Relationships Between Merge Trees and DMFs on Paths 123 J. Brüggemann lent. Thus, (T ,λ ) (T ,λ) = (forget(T ,λ ), λ ) holds. Nonetheless, the Ml tree io (T ,λ ) induces an index-ordered dMf. But we clearly have the following. Remark 5.3 Let T , T be isomorphic merge trees. Then (T , ≤ ) = (T , ≤ ) and io io ∼ ∼ ∼ (T , ≤ ) = (T , ≤ ) holds as Mo trees. Furthermore, we have forget(T , ≤ ) = T = sc sc io forget(T , ≤ ) as merge trees. sc We have already seen in Proposition 2.26 that the maps iMo and iMl are inverse to each other in the sense that they are bijections compatible with isomorphisms, order equivalences and shufﬂe-equivalences. We now show that M (_ , _) and are also inverse to each other up to the respective notions of equivalence. Theorem 5.4 The induced labeled merge tree M (_ , _) and the induced dMf deﬁne crit maps M (_ , _) : DM F ← → MlT : that are inverse to each other in the following sense: (1) For any dMf (P, f ) with only critical cells, the dMf (M (P, f ), λ ) is symmetry- equivalent to (P, f ), and (2) For any Ml tree (T ,λ), the Ml tree M (T , f ) is isomorphic to (T ,λ). Proof (1) Let (P, f ) be a dMf on a path. We construct a symmetry equivalence between f and f . It is given as follows: For any simplex σ of M (P, f ) there is exactly one simplex σ ˜ of P such that f (σ) ˜ = f (σ ). This induces a bijection ϕ : P → M (P, f ) which is compatible with f , f and id by deﬁnition. But in λ R general, the map ϕ is not simplicial. This is because the simplex order on M (P, f ) might be different than the left/right relation on the corresponding simplices of P. In other words, the map M (_) : P → M (P, f ) is in general not compatible with the two different simplex orders. Nonetheless, the Morse labeling λ induced by f orders the nodes of M (P, f ) in the same order as their corresponding simplices of P. Thus, connected components of sublevel complexes of (P, f ) still correspond to subtrees of M (P, f ). Since the induced merge tree assigns the chirality of child nodes according to which connected component carries the minimal value of f ,at each inner node of M (P, f ) the chirality of the two child nodes is either assigned in accordance with the left/right relation on the corresponding sublevel complex, or it is the opposite. If it is the opposite, this can be corrected by application of the reﬂection of the corresponding sublevel complex, that is, by application of a sublevel equivalence. In consequence, the difference between the right/left relation of the corresponding simplices in P and the simplex order only lies in symmetry equivalences of P. Thus, ϕ can be decomposed into a symmetry equivalence of P and a simplicial isomorphism ϕ ˜. Hence, (ϕ, ψ ) is a symmetry equivalence of dMfs on paths. (2) Let (T ,λ) be an Ml tree. Let c < c < ··· < c be the critical values of f 0 1 n λ and let σ ∈ T such that f (σ ) = c . We recall that the induced merge tree M i λ i i deﬁnes in particular a bijection between the critical simplices of T and the nodes of M (T , f ). For any simplex σ ∈ T , we denote the node of M (T , f ) that λ λ corresponds to σ by M (σ ). An isomorphism ϕ : (T ,λ) → M (T , f ) is given 123 On merge trees and discrete Morse functions on paths and... −1 by ϕ := M ◦ φ . It is immediate that ϕ is a bijection because M and φ are. Furthermore, ϕ is by construction compatible with the respective Morse labelings. It is only left to show that ϕ is compatible with the chiral child relation and the respective roots. Consider σ ∈ T . For both trees, the simplex σ corresponds to the root of the n n respective tree. In M (T , f ) this is the case because σ carries the maximal λ n value of f .In (T ,λ) this holds because φ(σ ) holds the maximal Morse label λ n λ(φ (σ )) = c . Thus, the map ϕ maps the root of (T ,λ) to the root of M (T , f ). n n λ Let σ be a simplex of T . We now prove that ϕ is compatible with the chiral child relation, that is, that ϕ(φ(σ ) ) = M (σ ) /ϕ(φ(σ ) ) = M (σ ) holds. If σ i l i l i r i r i is a 0-simplex then there is nothing to show because then both M (σ ) and φ(σ ) i i are leaves. Let σ be a critical edge with chirality L. The case for chirality R works symmetrically to the case with chirality L. By Construction 2.14, the node M (σ ) /M (σ ) corresponds to a critical simplex of i l i r the connected component of T that carries/does not carry the minimal value c −ε of f on these two connected components. Furthermore, the node M (σ ) /M (σ ) λ i l i r corresponds to the critical simplex that carries the maximal value of f of the respective connected component of T . c −ε By application of Proposition 3.25, we see that the connected components −1 −1 T [M (M (σ ) )]/T [M (M (σ ) )] induce subtrees of (T ,λ) via φ. c −ε i l c −ε i r i i It follows that the node φ(σ ) /φ(σ ) is contained in the subtree that corre- i l i r −1 −1 sponds to T [M (M (σ ) )]/T [M (M (σ ) )] via φ because by (2) c −ε i l c −ε i r i i of Deﬁnition 2.17 the subtree with root φ(σ ) does/φ(σ ) does not carry the i l i r minimal Morse label of the subtree with root φ(σ ) in (T ,λ). Furthermore, the node φ(σ ) /φ(σ ) corresponds to the simplex that carries the maximal value of i l i r −1 −1 f of T [M (M (σ ) )]/T [M (M (σ ) )] because by (1) of Deﬁnition λ c −ε i l c −ε i r i i 2.17 it carries the maximal Morse label on said subtree and because φ is order- preserving. Thus, ϕ(φ(σ ) ) = M (σ ) /ϕ(φ(σ ) ) = M (σ ) holds. i l i l i r i r By considering Fig. 1 we see that the difference between taking the induced merge tree of a dMf on a path is the same as taking its induced Ml tree and forgetting the Morse labeling. Thus, constructing a dMf that represents a given merge tree T is up to symmetry equivalence the same as choosing a Morse order on T . This leads us to: Theorem 5.5 Let T be a merge tree and let P be a path such that the number of ∼ ∼ 1-simplices in P is i (T ). Then T = M (P, f ) = M (P, f ) holds as merge trees io sc where f denotes the induced index-ordered dMf (Deﬁnition 3.20) and f denotes io sc the sublevel-connected dMf (Deﬁnition 4.5). Proof The statement follows by Theorem 5.4, Proposition 2.26, and the fact that by Deﬁnition 2.23, isomorphisms of Mo trees are in particular isomorphisms of the underlying merge trees. Furthermore, M (P, f ) M (P, f ) holds by Theorem 4.8. io sc Using the notion of component-merge equivalence, Deﬁnition 2.50, we can extend Theorem 5.4 to a bijection between the set of dMfs with only critical simplices on crit trees up to cm equivalence DM F and the set of Ml trees up to isomorphism MlT : 123 J. Brüggemann Theorem 5.6 The induced labeled merge tree M (_ , _) and the induced dMf deﬁne crit maps M (_ , _) : DM F ← → MlT : that are inverse to each other in the sense that: (1) For any dMf (X , f ) with only critical cells, the dMf (M (X , f ), λ ) is cm- equivalent to (X , f ), and (2) For any Ml tree (T ,λ), the Ml tree M (T , f ) is isomorphic to (T ,λ). Proof The proof for statement (2) works exactly as in the proof for Theorem 5.4 because symmetry equivalences are in particular cm equivalences. For (1) we apply Proposition 2.53 to consider a representative of the cm equivalence class of (X , f ) which is a dMf on a path (P, f ). By Proposition 2.52, the isomorphism type of the induced Ml tree does not depend on this choice. Thus, Theorem 5.4 implies that (M (P, f )) is symmetry-equivalent to (P, f ). Since (P, f ) is cm-equivalent to (X , f ),sois (M (P, f )). Corollary 5.7 Let T be a merge tree. By Theorems 5.5 and 5.6 it follows that there are dMfs on trees (X , f ) such that M (X , f ) T as merge trees. Corollary 5.8 Applying Theorem 5.6 together with Propositions 2.26 and 2.40 yields crit the result that there is a bijection DM F / = MoT where ∼ denotes order equiv- alence. We conclude this section by discussing our results and comparing them to the results of Curry (2019). Using the bijections appearing in Fig. 1 and Theorem 5.6 we replaced the question of ﬁnding dMfs on paths or arbitrary trees that represent a given merge tree T by ﬁnding Morse orders on T instead. This argument can be used to replace the question of classifying merge equivalence classes of dMfs on trees by classifying Morse orders. Example 5.2 tells us that, if a merge tree T has at least three leaves, there might be different Morse orders on T which are not shufﬂe-equivalent. That is, there are dMfs on trees (X , f ) contained in the image of ◦ iMl which induce T as their merge tree but are neither isomorphic, nor symmetry-equivalent, nor cm-equivalent, nor shufﬂe-equivalent, nor a combination of the four to each other. We found a non- empty shufﬂe equivalence class of Morse orders on any merge tree, deﬁned by either the index Morse order or the sublevel-connected Morse order, since the two have been shown to be shufﬂe-equivalent and, hence, merge-equivalent in Theorem 4.8.This allowed us to answer the aforementioned question of Johnson–Scoville afﬁrmatively. That is, any merge tree is indeed represented by a dMf on a path, which is induced by a Morse order. Using a non-trivial cm equivalence, one can also ﬁnd a dMf on a tree other than a path as a representative. Furthermore, our results from Sects. 2.1, 2.2 and 5 allow us to structure the study of the set of merge equivalence classes of dMfs on trees using the following four notions of merge-invariant equivalences between dMfs on trees: Forman equivalence, symmetry equivalence, cm equivalence, and shufﬂe equivalence. We discussed in Remark 5.1 how Forman equivalences could be considered together with the other notions of equivalence and why we left Forman equivalences out of this work. In Theorem 5.4 it becomes quite clear that passing to the induced Ml tree identiﬁes symmetry-equivalent dMfs with each other up to isomorphism. Passing from 123 On merge trees and discrete Morse functions on paths and... the induced Ml tree to the induced Mo tree then identiﬁes dMfs up to order equivalence with each other up to isomorphism of the underlying Mo tree. Last of all, passing from the induced Mo tree to the induced merge tree in particular identiﬁes shufﬂe- equivalent dMfs with each other. This allows us to study the different equivalence classes separately for dMfs on paths. The more liberal notion of cm equivalence, Deﬁnition 2.50, allowed us to generalize Theorem 5.4 to dMfs on arbitrary trees as seen in Theorem 5.6. In Curry (2019), the author establishes a bijection between graph-equivalence (Curry 2019, Def 6.1) classes of Morse-like (Curry 2019, Def 6.9) continuous functions on the interval that attain minima at the boundary on the one hand and isomorphism classes of chiral merge trees (Curry 2019, Def 5.3) on the other hand. At ﬁrst glance it might seem likely that Ml trees in the sense of Deﬁnition 2.19 and chiral merge trees in the sense of Curry (2019, Def 5.3) are directly related by geometric realization and considering the corresponding abstract simplicial complex but, as mentioned in the introduction, there is a subtle difference in the construction of the induced merge tree. To be precise, the two constructions only differ in the induced chirality. In Curry (2019, Sec 5) the chirality is given by which of the two merging components is the left or right one with respect to the chosen orientation on the interval. In Johnson and Scoville (2022) the chirality is given such that drawing the induced merge tree is compatible with the elder rule: The component with the minimal value gets the same chirality as the merged component. This means that following the same chirality leads to the oldest component. This convention leads to the necessity to assume property (2) of Deﬁnition 2.17: a certain compatibility between the Morse order and the chirality. The compatibil- ity between Morse orders and the chirality implies, as seen in Proposition 2.48, that the induced Ml tree does not distinguish between symmetry-equivalent dMfs. If one deﬁnes induced Ml trees analogously to Curry (2019), that is by inducing the chirality by a chosen orientation of the path, this notion of induced Ml trees would distinguish symmetry-equivalent dMfs on paths. Moreover, Ml trees induced by symmetry-equivalent dMfs would be related by sequences of reﬂections of subtrees. The deﬁnition could be as follows: Deﬁnition 5.9 Let T be a merge tree. A Curry Morse order is a total order ≤ on the nodes of T such that the maximal node of any subtree is the root of said subtree. A Curry Morse labeling on a merge tree T is a labeling λ on the nodes of T that induces a Curry Morse order on T . A pair (T , ≤) of a merge tree with a Curry Morse order on it is called a Curry Morse ordered merge tree (CMo tree). A pair (T ,λ) of a merge tree with a Curry Morse labeling on it is called a Curry Morse labeled merge tree (CMl tree). Let f : P → R be a dMf where P is an oriented path. Then the CMl tree induced by f is constructed as is Construction 2.14 with the difference that the chirality is assigned according to the position of the corresponding connected components with respect to the orientation instead of according to critical values. Remark 5.10 CMl trees as deﬁned above are basically the same concept as generic merge trees as deﬁned in Curry et al. (2021, Def 2.2). We stick to the name CMl 123 J. Brüggemann trees instead of generic merge trees because we already use the term merge tree in a different way. Example 5.11 We consider two of the symmetry-equivalent dMfs from Example 2.47 and see how the induced CMl tree distinguishes them whereas the induced Ml trees identiﬁes them as one: g : f : 0 4 1 5 2 6 3 3 6 1 4 0 5 2 • • • • • • • • ∼ ∼ M (P, f ) = M (P, f ) = M (P, g) : M (P, g) : C C 0 1 1 0 • • • • 4 2 4 2 • • • • 5 3 3 5 • • • • • • 6 6 The notion of CMl trees is related to the notion of chiral merge trees in the sense of Curry (2019) by the interplay between abstract and geometrical simplicial complexes. In detail, the bijection is given as follows: Construction 5.12 Let (T ,λ) be a CMl tree. We deﬁne a chiral merge tree |(T ,λ)| associated to (T ,λ) as follows: The compact rooted tree is given by the geometric realization |T |. We attach a distinguished edge e to the vertex which corresponds to the root of T in order to obtain a cell complex which we will by abuse of notation also refer to as |T |.The map π :|T|→ R is given by λ on vertices, and by a linear extension of λ on edges. For the other way around let π : T → R be a chiral merge tree in the sense of Curry (2019, Def 5.3). We deﬁne an Ml tree abs(T ) associated to T as follows: We take the 0-skeleton T as the vertex set and the 1-skeleton (T \{e }) as the 0 ∞ 1 set of edges. We deﬁne the node which corresponds to v to be the root of abs(T ). The labeling λ is given by π. The proof that the two constructions are inverse to each other is straightforward. Furthermore, there is a similar bijection between the two notions of Morse functions: Construction 5.13 Let (P, f ) be a dMf with only critical cells on an oriented path. We deﬁne a Morse-like function f on the interval which attains minima at the boundary as follows: Let k + 1 be the number of 0-simplices in P. We denote the 0-simplices of P by n , n ,..., n from left to right with respect to the given orientation. Then we 0 1 k deﬁne f ( ) := f (n ) for i ∈{0, 1,..., k}. We denote the 1-simplices of P by 2i −1 e ,..., e , again according to the given orientation. Then we deﬁne f ( ) := f (e ) 1 k i 2k for i ∈{0, 1,..., k}. We deﬁne f on the rest of the interval as the linear extension. This ˜ ˜ makes f a distinct-valued PL function that attains minima at the boundary. Hence, f is Morse-like. 123 On merge trees and discrete Morse functions on paths and... For the other way around let f : I → R be a Morse-like function that attains minima at the boundary. We deﬁne a path P and a dMF f on P as follows: Let n , n ,..., n be the local minima of f ordered by the orientation on I,so 0 1 k in particular n = 0 and n = 1. We deﬁne P to be a path with k + 1 simplices of 0 k dimension 0. We choose one of the endpoints to be denoted by s and the one by s . 0 k We denote the other 0-simplices such that their indices are in accordance with their position in the simplex order (Deﬁnition 3.15), making s the minimal simplex with respect to the simplex order. The dMf f is deﬁned by f (s ) := f (n ) on 0-simplices. i i Let c ,..., c be the local maxima of f , ordered in accordance to the orientation on I , 1 k and let e ,..., e be the 1-simplices of P, ordered in accordance to the aforementioned 1 k simplex order on P. Then f is deﬁned by f (e ) := f (c ) on 1-simplices. i i It is easy to check that the two given constructions are inverse to each other. A theorem which, analogously to Theorem 5.4, deﬁnes a pair of inverse bijections + crit M (_ , _) : DM F ↔ CMlT : can be proved similarly to the proof of Theorem 5.4. The difference is that the induced CMl tree keeps track of symmetry equivalences in the sense that symmetry equivalences of dMfs induce reﬂections at roots of sub- trees on the induced CMl trees. The map can be deﬁned the same way as before. −1 Alternatively, one could deﬁne the bijection as the composition abs ◦ ◦|_| in the diagram in Fig. 2: Here denotes the bijection between the set of Morse-like functions on the interval M and the set of chiral merge trees X from Curry (2019, Cor 6.11). The map i is the inclusion induced by considering Ml trees as CMl trees. Ml trees can be considered as a special kind of CMl trees because they only differ in the additional property (2) of Deﬁnition 2.17 which does not need to hold for CMl trees. The map / is the symm quotient map that identiﬁes symmetry equivalent dMFs. The map o is deﬁned as the JS composition ◦i ◦ M (_ , _). This deﬁnition coincides with choosing the representative of a dMf (P, f ) with respect to symmetry equivalence such that the simplex order on P is compatible with f in the following way: At each critical edge e with f (e) = c the connected component of P that corresponds to M (e) /M (e) is left/right is c−ε l r left/right of the edge e with respect to the orientation induced by the simplex order. Here we recall that M (e) denotes the inner node of M (P, f ) that corresponds to the critical edge e and that M (e) /M (e) denotes the left/right denotes the left/right child l r node of M (e). In Example 5.11 we have o (P, g) = (P, f ) where (P, f ) is oriented JS from left to right. The map JS is deﬁned as JS := M (_ , _) ◦ / ◦ . This deﬁnition coincides symm with division by the equivalence relation generated by reﬂections of subtrees. Example 5.14 We consider how a sequence of reﬂections of subtrees maps the CMl trees from Example 5.11 to each other. Here, we denote by a the reﬂection of the subtree with root labeled λ. 0 1 1 0 0 1 1 0 • • • • • • • • 4 2 2 4 4 2 4 2 • • a • • a • • a • • 6 5 4 5 3 3 5 3 5 3 5 • • • • • • • • • • • • 6 6 6 6 123 J. Brüggemann The proof that the two possible deﬁnitions for coincide and that the diagram from Fig. 2 commutes are straightforward. As a result, the map can be seen as a discrete version of the map from Curry (2019, Cor 6.11). Moreover, moving from the setting of Curry (2019) to the setting of Johnson and Scoville (2022) basically means to divide by symmetry equivalences which allows the authors of Johnson and Scoville (2022) to generalize the construction of the induced merge tree to dMfs on trees. In order to extend our generalization Theorem 5.6 to the oriented case, one would need to ﬁnd a notion of orientation- preserving cm equivalences which distinguishes symmetry-equivalent dMfs. 6 Further directions and possible applications In this section we want to take a look at possible applications of our results. The structured overview of the different notions of equivalence of discrete Morse functions and their connections to each other might be useful to explore the space of discrete Morse functions on a given simplicial complex. Even though the construction of the induced merge tree from Johnson and Scoville (2022) does not easily extend to arbitrary simplicial complexes, the notions of equivalence from this article do. Hence, one could try to use e.g. the notion of symmetry equivalence to structure the space of discrete Morse functions in a nice way, i.e. into orbits of a groupoid action. In a second step, one could then try to deﬁne the space of merge trees as a quotient of the space of discrete Morse functions on some “large enough” simplicial complex. With such a construction, one could assemble the results from this article and the results from Curry et al. (2021) into an analysis of a larger instance of the persistence map. Aside from this, one could try to generalize and enhance the construction of the induced merge tree from Johnson and Scoville (2022) to arbitrary simplicial com- plexes. Then, in a second step, one could try to use the induced merge tree to ﬁnd possible cancellations of pairs of critical simplices. This way, the induced merge tree might be helpful to optimize discrete Morse functions. Furthermore, one could study the possible Morse orders on a given merge tree. With a classiﬁcation of all Morse orders on a given merge tree T , one could classify all discrete Morse functions on any given tree that induce T as the induced merge tree with the help of Deﬁnition 3.20 and cm equivalences. | | M ( , ) JS crit + crit DMF DMF Mer M P P / abs symm −1 ≤ ≤ forget M ( , ) M ( , ) sc io Φ C Φ Ψ Ψ | | iMl i MoT MlT CMlT X iMo JS abs Fig. 2 Relationship to the continuous case 123 On merge trees and discrete Morse functions on paths and... Ultimately, the proofs of Theorem 5.6 and all the lemmas that lead to it describe exactly which information is lost when considering the induced Ml tree instead of the original dMf. This knowledge might be useful for applications in TDA because it tells the user which kind of features will not be seen by the induced merge tree, and hence, by the persistent zeroth homology and the barcode. Moreover, the knowledge about the exact lost information can be used to enhance the induced merge tree with extra structure such that it no longer disregards certain desired information. Acknowledgements The author would like to thank Benjamin Johnson and Nicholas A. Scoville for the suggested questions in their article (Johnson and Scoville 2022) which led to this project. Furthermore, the author would like to thank the mathematical faculty of Ruhr-University of Bochum, especially the chair for topology, for the great scientiﬁc environment in which this endeavor was started. In addition to that the author thanks Max Planck Institute for Mathematics for the great scientiﬁc environment in which this project was ﬁnished. Most notably the author thanks his advisor, Viktoriya Ozornova, for her advice and the many helpful discussions which increased the quality of this article. Last but not least, the author thanks the anonymous referees for the helpful and detailed feedback. Funding Open Access funding enabled and organized by Projekt DEAL. Declarations Conﬂict of interest The author states that there is no conﬂict of interest. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References Baryshnikov, Y.: Time Series, Persistent Homology and Chirality. (2019). arXiv:1909.09846 Curry, J, DeSha, J., Garin, A., Hess, K., Kanari, L., Mallery, B.: From Trees to Barcodes and Back Again II: Combinatorial and Probabilistic Aspects of a Topological Inverse Problem. 07 (2021). arXiv:2107.11212v2 Carr, H., Snoeyink, J., Axen, U.: Computing contour trees in all dimensions. Comput. Geom.: Theory Appl. 24(2), 75–94 (2003) Curry, J.: The ﬁber of the persistence map for functions on the interval. J. Appl. Comput. Topol. 2(3), 301–321 (2019) Forman, R.: Morse theory for cell complexes. Adv. Math. 134, 90–145 (1998) Forman, Robin: A user’s guide to discrete morse theory. Sem. Lothar. Combin. 48, 12 (2001) Heine, C., Leitte, H., Hlawitschka, M., Iuricich, F., De Floriani, L., Scheuermann, G., Hagen, H., Garth, C.: A survey of topology-based methods in visualization. Comput. Graph. Forum 35, 643–667 (2016) Johnson, B., Scoville, N.A.: Merge trees in discrete Morse theory. Res. Math. Sci. 9(3), 1–7 (2022) Kweon, I.S., Kanade, T.: Extracting topographic terrain features from elevation maps. CVGIP: Image Underst. 59, 171–182 (1994) Liu, S., Maljovec, D., Wang, B., Bremer, P.-T., Pascucci, V.: Visualizing high-dimensional data: advances in the past decade. IEEE Trans Vis. Comput. Graph. 23(3), 1249–1268 (2016) Nanda, V., Tamaki, D., Tanaka, K.: Discrete Morse theory and classifying spaces. Adv. Math. 340, 723–790 (2018) 123 J. Brüggemann Oesterling, P., Heine, C., Weber, G.H., Morozov, D., Scheuermann, G.: Computing and Visualizing Time-Varying Merge Trees for High-Dimensional Data. Topological Methods in Data Analysis and Visualization, pp. 87–101 (2017) Oesterling, P., Heine, C., Weber, G.H., Scheuermann, G.: Visualizing ND point clouds as topological landscape proﬁles to guide local data analysis. IEEE Trans. Vis. Comput. Graph. 19, 514–526 (2013) Shinagawa, Y., Kunii, T.L., Kergosien, Y.L.: Surface coding based on morse theory. IEEE Comput. Graph. Appl. 11(05), 66–78 (1991) Tarasov, S.P., Vyalyi, M.N.: Construction of contour trees in 3D in O(n log n) steps. In: SCG 98: Proceedings of the Fourteenth Annual Symposium on Computational Geometry, pp. 68–75 (1998) van Kreveld, M., van Oostrum, R., Bajaj, C., Pascucci, V., Schikore, D.: Contour trees and small seed sets for isosurface traversal. In: SCG 97: Proceedings of the Thirteenth Annual Symposium on Computational Geometry, pp. 212–220 (1997) Weber, G.H., Bremer, P.T., Pascucci, V.: Topological landscapes: a terrain metaphor for scientiﬁc data. IEEE Trans. Vis. Comput. Graph. 13, 1416–1423 (2007) Yan, L., Wang, Y., Munch, E., Gasparovic, E., Wang, B.: A structural average of labeled merge trees for uncertainty visualization. IEEE Trans. Vis. Comput. Graph. 26, 832–842 (2019) Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional afﬁliations.
Journal of Applied and Computational Topology – Springer Journals
Published: Nov 26, 2022
Keywords: Discrete Morse theory; Combinatorial algebraic topology; Merge trees; 57Q70 (Primary); 05C05 (Secondary); 05C90
You can share this free article with as many people as you like with the url below! We hope you enjoy this feature!
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get DeepDyve free for 14 days.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.