Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Stratifying the space of barcodes using Coxeter complexes

Stratifying the space of barcodes using Coxeter complexes Embeddings of the space of barcodes in Euclidean spaces are unstable due to the permutation of the bars of a barcode. We use tools from geometric group theory to produce a stratification of the space B of barcodes with n bars that takes into account these permutations. This gives insights in the combinatorial structure of B . The top- dimensional strata are indexed by permutations associated to barcodes as defined by Kanari, Garin and Hess. More generally, the strata correspond to marked double cosets of parabolic subgroups of the symmetric group Sym . This subdivides B into regions that consist of barcodes with the same averages and standard deviations of birth and death times and the same permutation type. We obtain coordinates that form a new invariant of barcodes, extending the one of Kanari–Garin–Hess. This description also gives rise to metrics on B that coincide with modified versions of the bottleneck and Wasserstein metrics. Keywords Barcodes · Topological data analysis · Coxeter complex · Geometric group theory Mathematics Subject Classification 51F15 · 55N31 · 20F55 · 57N80 1 Introduction Barcodes Carlsson (2009); Edelsbrunner et al. (2008); Ghrist (2008) are topological summaries of the persistent homology of a filtered space. The barcode B associated to a filtration {X } is a multiset of points (b, d) ∈ R . It summarises the creation t t ∈R and destruction of homology classes while varying the parameter t, which is often interpreted as “time”. A bar (b, d) ∈ B corresponds to a homology cycle appearing in B Adélie Garin adelie.garin@gmail.com ETH Zurich, Zurich, Switzerland École Polytechnique Fédérale de Lausanne: Ecole Polytechnique Federale de, Lausanne, Switzerland 123 B. Brück, A. Garin X and becoming a boundary in X . The first element of the pair (b, d) is called the b d birth and the second one the death. Persistent homology has applications in many fields, from biology Byrne et al. (2019); Gameiro et al. (2015); Kanari et al. (2018); Reimann et al. (2017) to material science Delgado-Friedrichs et al. (2014); Lee et al. (2018); Robins et al. (2016), astron- omy Heydenreich et al. (2021) and climate science Muszynski et al. (2019). In many of these applications, it is necessary to study statistics on barcodes. Unfortunately, the space of barcodes is not a Hilbert space, which means that it can be difficult to apply statistical methods to it. Several ways to overcome the issue exist, such as the creation of kernels to map barcodes into a Hilbert space Bubenik (2015); Carrière et al. (2015); Adams et al. (2017); Di Fabio et al. (2015). In this paper, we tackle this issue from a different perspective. We use combinatorial tools from geometric group theory to define new coordinates for describing barcodes. These coordinates divide the space of barcodes into regions indexed by the averages and the standard deviations of births and deaths and by the permutation type of a barcode as defined in Kanari et al. (2020); Curry et al. (2021). By associating to a barcode the coordinates of its region, we define a new invariant of barcodes. This opens the door to doing statistics on barcodes using methods from the field of permutation statistics. 1.1 Motivation The motivation for this work is to understand the space of barcodes from a combina- torial and geometric point of view and to show that it almost has a locally Euclidean structure. We call a barcode strict if there are no two pairs in it that have the same birth or death. It was observed in Kanari et al. (2020) that to a strict barcode B = {(b , d )} i i i ∈{1,...,n} with n bars, one can associate a permutation σ ∈ Sym . It is the permutation such that the bar with the i-th smallest death has the σ (i )-th smallest birth. This divides the set of strict barcodes with n bars into n! equivalence classes, one for each element of the symmetric group Sym . Based on this observation, one can study the combinatorial properties of strict barcodes by describing these equivalence classes—or equivalently, the elements of Sym —and the relations between them. A first approach to this, taken in Kanari et al. (2020); Curry et al. (2021), is to consider the Cayley graph of the symmetric group with respect to the generating set given by adjacent transpositions (i , i + 1). This yields a combinatorial representation of the elements of Sym . It tells us how a pair of permutations can be transformed into one another using transpositions one step at a time. However, it yields no information about “higher order relations” that exist among larger sets of permutations. A way to resolve this is to add higher dimensional cells to the Cayley graph and to consider it more geometrically as a cell complex instead of as a (combinatorial) graph. A first approach would be to use that the Cayley graph of Sym is the 1-skeleton of the permutohedron Postnikov (2009) of order n, see Fig. 1. This observation embeds the Cayley graph into a polyhedral decomposition of the (n − 2)-sphere. As this is a more geometric object, it allows to continuously “walk” from one permutation to another. 123 Stratifying the space of barcodes… Fig. 1 The permutohedron Postnikov (2009) of order 4 is a polyhedral decomposition of the sphere where each vertex corresponds to an element of the symmetric group Sym . Its 1-skeleton is the Cayley graph of Sym (see also Fig. 5) Fig. 2 Two barcodes with the same associated permutation (the identity [1234]) but with large differences in their birth and death values The problem is that only the vertices (and not the higher dimensional cells) of the permutohedron have an interpretation in terms of elements of the symmetric group. Furthermore, this representation lacks a notion of “size” for barcodes. For instance, the two barcodes depicted in Fig. 2 lie in the same equivalence class, i.e. have the same associated permutation. The alternative that we suggest to overcome these problems is to work with Coxeter complexes instead of permutohedra. The Coxeter complex associated to Sym is the dual of the permutohedron of order n (see Fig. 3). It forms a simplicial decomposition of the (n − 2)-sphere and is well-studied in the context of reflection groups and Tits buildings. For us, it has the advantage that its top-dimensional simplices correspond in a natural way to permutations and only passing through a face of lower dimension changes such a permutation. This allows for a better description of continuous changes between different permutations. It also has the advantage that it comes with an embedding in R , where the additional two real parameters that are needed to describe positions 123 B. Brück, A. Garin Fig. 3 The permutohedron of order 4 (black) is the dual of the Coxeter complex (Sym ) (grey) relative to this (n − 2)-dimensional space have a natural interpretation in terms of the “size” of barcodes. Moreover, using the Coxeter complex description for barcodes allows to define the permutation type of any barcode. For non-strict barcodes, it is defined only up to parabolic subgroups of Sym , i.e. subgroups that are generated by sets of adjacent transpositions. 1.2 Contributions In this paper, we use Coxeter complexes to develop a description of the set B of barcodes with n bars with coordinates that have natural interpretations when doing statistics with barcodes. These coordinates define a stratification of B where the top- dimensional strata are indexed by the symmetric group Sym . Our main contributions can be summarised as follows. Theorem 1.1 Let B denote the set of barcodes with n bars. 2n 1. B can in a natural way be seen as a subset of a quotient Sym \R . 2. B is stratified over the poset of marked double cosets of parabolic subgroups of Sym . 3. Using this description, one obtains a decomposition of B into different regions. Each region is characterised as the set of all barcodes having the same average birth and death, the same standard deviation of births and deaths and the same permutation type σ ∈ Sym . 4. This description gives rise to metrics on B that coincide with modified versions of the bottleneck and Wasserstein metrics. Intuitively, this means that there are two types of small perturbations of a barcode. One is to perturb it such that one obtains another barcode with the same permutation 123 Stratifying the space of barcodes… type. Such a perturbation takes place in a Euclidean subspace (a single stratum) of B . The other is to change the permutation type and hence going from one Euclidean area (i.e. stratum) to another. For more detailed and formal statements of these results, see Proposition 4.2, Theorem 4.9, Corollary 4.10 and Proposition 5.2. To obtain this description of B we proceed as follows. A barcode is an (unordered) multiset of n pairs of real numbers (births and deaths). It can hence be seen as a n n point in the quotient space Sym \(R × R ), where the action of Sym permutes the n n coordinate pairs. Since the birth is smaller than the death for every barcode, B is a 2n proper subset of this quotient of R . The Coxeter complex (Sym ) associated to Sym is a simplicial complex whose n n geometric realisation is homeomorphic to an (n−2)-sphere. Hence, we can decompose R as R = cone((Sym )) × R, n−1 where cone((Sym )) = (Sym ) ×[0, ∞) /(x , 0) ∼ (y, 0) R .This n n decomposition allows one to describe each point x ∈ R via coordinates x , x¯ , v , θ x where x specifies a point on the Coxeter complex, v  is the “cone parameter” and θ x x¯ parametrises the remaining R (for details, see Proposition 3.2, where the naming becomes clear as well). In summary, this describes B as a subset of B ⊂ Sym \ cone((Sym )) × R × cone((Sym )) × R . n n n We call the coordinates that we obtain from this description Coxeter coordinates. ¯ ¯ It turns out that for each barcode, these coordinates are b , b, v  and d , d, v , θ b θ d ¯ ¯ where b and d are the averages of the births and deaths, v  and v  are their standard b d deviations and the coordinates b and d describe the permutation equivalence class of θ θ the barcode of Kanari et al. (2020); Curry et al. (2021). The stratification one obtains is induced by the simplicial structure of (Sym ). Hence, each stratum is Euclidean. The advantages of these new coordinates are two-fold: Firstly, using points in Cox- eter complexes, one obtains coordinates that uniquely specify barcodes and are yet compatible with the combinatorial structure of B given by permutation equivalence classes. Secondly, one resolves the earlier-mentioned problem that permutation equiv- alence classes themselves carry no notion of “size”: The decomposition of B into regions subdivides these equivalence classes by also taking into account the averages and standard deviations of births and deaths. This makes these regions a finer invari- ant than the permutation type. Therefore, they offer a new way to study statistics of barcodes by using both the average and standard deviation of births and deaths, which are commonly used summaries in Topological Data Analysis (TDA), and permutation statistics tools. The latter include the number of descents for instance, or the inversion numbers, which have proven useful for the study of the inverse problem for trees and barcodes Kanari et al. (2020); Curry et al. (2021). 123 B. Brück, A. Garin 1.3 Related work This paper is a follow-up of the work started in Kanari et al. (2020); Curry et al. (2021) to study the space of barcodes from a combinatorial point of view. It extends the approach of considering permutations to classify barcodes to a finer classification that also takes into account the average and standard deviation of births and deaths. In Xu (2020), the author also observes a connection between barcodes and the symmetric group in a different setting, by studying the space of barcode bases using Schubert cells. Similarly, Jacquard et al. (2022) also studies the space of barcode bases. The idea of giving coordinates to the space of barcodes is not new Di Fabio et al. (2015); Kališnik (Feb 2019). For example, the space of barcodes was given tropical coordinates in Kališnik (Feb 2019). In Adcock et al. (2013), it is mentioned that the space of barcodes can be identified with the n-fold symmetric product of R , and the authors study the corresponding algebra of polynomials associated to the variety. Finally, defining a polyhedral structure on a space to study statistics has been done for spaces of (phylogenetic) trees Billera et al. (2001); Grindstaff and Owen (2018). The connection between phylogenetic trees, merge trees and barcodes is studied in Curry et al. (2021). The polyhedral structure defined in this paper and in Billera et al. (2001) seem to be related, but we leave this as future work. 1.4 Overview In Sect. 2 we review the necessary background on barcodes and on Coxeter complexes. We use a standard way of realising Sym as a reflection group to explain what we mean with “Coxeter coordinates” on R in Sect. 3. We then describe the space B n n of barcodes with n bars in terms of Sym \R × R in Sect. 4.1, before adapting the coordinates of R to B in Sect. 4.2. In Sect. 4.3, we describe the stratification of B n n induced by these coordinates. Corollary 4.10 decomposes the space of barcodes into regions indexed by the average and standard deviation of the births and deaths and the permutation associated to a barcode. Finally, in Sect. 5, we show that B can be given metrics inspired by the bottleneck and Wasserstein distances and that it defines n n an isometry between a subset of Sym \R × R and B . 2 Background 2.1 Background on TDA We start by reviewing the necessary background on TDA. For the reader who is com- pletely new to this, we refer to the reviews Carlsson (2009); Edelsbrunner et al. (2008); Ghrist (2008). Even though this work focuses on the space of barcodes and could be apprehended from a purely combinatorial point of view, we shortly mention where barcodes arise in the field of TDA. This section is not necessary for the understanding of this paper, and we will give the combinatorial definition of barcodes that we use in the next section. 123 Stratifying the space of barcodes… Barcodes are topological summaries of a filtered topological space, i.e. a sequence of spaces ordered by inclusion. To obtain a barcode from a filtered space, one computes homology at each step and considers the maps induced by the inclusions. The output is called a persistence module, and it summarises the evolution of the homology at each step of the filtration. More precisely, let {X } be a filtered topological space, that is, each X is a t t ∈R t topological space and X ⊆ X  if t ≤ t .The k-th persistence module associated to {X } is given by H ({X } ), where H denotes the k-th homology functor t t ∈R k t t ∈R k (over a field k). The Crawley–Bovey Theorem Crawley-Boevey (2015) states that under mild tameness conditions on {X } , the associated persistence module can t t ∈R ⊕n be decomposed as a direct sum of interval modules k , where the interval j ∈J module k is the free k-module of rank 1 on the interval I ⊆ R, with identity maps I j internal to I , and is 0 elsewhere. This decomposition is unique up to reordering. Each interval represents the lifetime of a cycle in the filtered space. For instance, if a 1-cycle (a loop) appears in the topological space X for the first time and becomes a boundary (gets “filled in”) in X , then this 1-cycle will be represented by the interval I =[b , d ).The barcode associated to the persistence module is the multiset j j j B ={I } , j ∈J where each interval I appears n times. Usually, each I is a half open interval j j j I =[b , d ), where b is called the birth of the homological feature corresponding j j j j to I and d is called its death. If the interval I is a half infinite interval, i.e. it is of j j j the form [b , ∞),itiscalledan essential class. In this paper, we will identify such an interval with the pair (b , d ), since we j j are mostly interested in the combinatorics of the pairs and not the corresponding persistence module. Moreover, b and d will always take finite values in R. j j 2.1.1 The space of barcodes We introduce here the main definitions used in this paper. We start by a more combi- natorial definition of barcodes that we will use in this article. Definition 2.1 A barcode {(b , d )} is a multiset of pairs (b , d ) ∈ R such that i i i ∈J i i b < d for each i ∈ J and |J | < ∞. Each such pair is called a bar; its first coordinate i i b is called the birth (time) and the second one d is called its death (time). A barcode i i is called strict if b = b and d = d for i = j.Welet B denote the set of barcodes i j i j n st with n bars and B the set of strict barcodes with n bars. Remark 2.2 The reader familiar with persistent homology will notice that we suppose that the bars corresponding to essential classes have finite values instead of being half- open intervals. This is usually the case in practical applications, where such essential classes are given finite values for representing them on a computer. We also assume that every barcode consists of only finitely many bars. 123 B. Brück, A. Garin Fig. 4 A A barcode with 4 bars. B The same barcode with a different indexing where the bars are ordered by increasing birth times Remark 2.3 The definition of strict barcodes was first introduced in Kanari et al. (2020) to define the bijection between the symmetric group on n elements and some equiv- alence classes of barcodes that we introduce in the next section. The setting in this paper is slightly different from Kanari et al. (2020) and Curry et al. (2021), because all the barcodes considered there are specific to merge trees and arise from their 0-th persistent homology. This is why the definition of a strict barcode in Kanari et al. (2020) and Curry et al. (2021) assumes the existence of an essential bar (b , d ) that 0 0 contains all the others. In this paper however, barcodes can come from arbitrary fil- trations in arbitrary dimension, and such a bar (b , d ) need not exist. Therefore we 0 0 slightly adapt the definition of a strict barcode and the relation to the symmetric group in the next sections. In practice, for finite barcodes, the indexing set J is commonly the set {1, ..., n}, giving the bars in the barcode an arbitrary but fixed ordering. We will also adopt this convention from now on. Note however that reordering the bars might change the indexing, but not the underlying barcode (see Example 2.4). It can sometimes be convenient to assume that the indexing is such that the births are ordered increasingly b < b < ... < b , but we do not make this assumption in this paper unless specified. 1 2 n We often represent a barcode by the set of intervals [b , d ]⊂ R (as in Fig. 4). i i Another common way to represent barcodes is what is called a persistence diagram, where the pairs (b , d ) are represented as points in R (as in Fig. 8). These points lie i i above the diagonal since b < d for all i. i i Example 2.4 Figure 4 shows an example of a strict barcode with two different indexing conventions. To turn the set of barcodes into a topological space, one needs to specify a topology. One option to do this is by introducing the bottleneck or Wasserstein distances, two commonly used metrics for barcodes. Intuitively, the bottleneck distance between two barcodes B and B tries all possible matchings between the bars of B and the bars of B and chooses the one that minimises the “energy” required to move the matched pair of bars with maximal separation. However, it does not only consider matching of bars between B and B but also with points on the diagonal  ={(x , x ) | x ∈ R}. 123 Stratifying the space of barcodes… Definition 2.5 Let B ={(b , d )} and B ={(b , d )} be two bar- i i i ∈{1,...,n} i ∈{1,...,m} i i codes. The bottleneck distance between B and B is d (B, B ) = min maxx − γ(x ) , B ∞ x ∈B where γ runs over all possible matchings, i.e. maps that assign to each bar (b , d ) ∈ B i i either a bar in B or a point in the diagonal , such that no point of B is in the image ∞ 2 more than once. Here, · is the l -norm on R . Remark 2.6 The permutation γ acts as a “reindexing” of the indices of B and B , and in particular ensures that d (B, B ) does not depend on any indexing of the bars. The Wasserstein distance is defined in a similar way by taking the sum over all l -distances between x and γ(x ) instead: d (B, B ) = min  x − γ(x ) ). W x ∈B Remark 2.7 Note that in general, the barcodes B and B need not have the same number of bars. The diagonal allows matchings between barcodes with different number of bars, since “ummatched” bars can be sent to the diagonal. In this paper however, we study the set of barcodes B with exactly n bars (for arbitrary, but fixed n) and restrict ourselves to this case. We are mainly interested in B as a set and the main results we prove do not depend on the metric that is chosen on B . We will still with a slight abuse of notation mostly talk of B as a space, without specifying a specific metric on it. An exception to that is Sect. 5, where we explain how a metric d on B , which is closely related to the B n bottleneck distance, occurs in an alternative description of the set B that we work with later on. 2.1.2 Relation to the symmetric group We write Sym for the symmetric group on n letters, i.e. the group of all permutations of {1,..., n}. We usually use the one-line notation for permutations. That is, we specify σ ∈ Sym by the its image of the ordered set {1,..., n}, e.g. we write σ =[132]∈ Sym if σ(1) = 1, σ(2) = 3 and σ(3) = 2. We make an exception for transpositions to simplify the notation: the transposition that switches i and j is denoted by (i , j ). st Definition 2.8 Kanari et al. (2020)Let B ={(b , d )} ∈ B be a strict bar- i i i ∈{1,...,n} code. If we order the births increasingly such that b < ··· < b , the indexing in i i 1 n {1, ..., n} gives a permutation τ by τ (k) = i , i.e. τ is the (unique) permutation such b b k b that b < ··· < b . (1) τ (1) τ (n) b b Similarly, ordering the deaths d < ··· < d gives rise to a permutation τ with j j d 1 n −1 τ (k) = j .The permutation σ associated to B is defined as σ = τ τ ; it tracks d k B B d the ordering of the death values with respect to the birth values. 123 B. Brück, A. Garin Fig. 5 (Figure from Kanari et al. (2020)) The Cayley graph of Sym generated by the three transpo- sitions (12), (23), (34). Four barcodes are drawn next to the extremities of the graphs (permutations [1234], [2134], [2143], [1243]) to illustrate a typical barcode corresponding to each permutation Remark 2.9 The permutations τ and τ both depend on the indexing choice of the b b d i and d . However, the permutation σ does not depend on any indexing of the births and deaths, it is intrinsic to the multiset B. Indeed, σ can be defined directly as the permutation that sends the i-th death (in increasing order) to the σ(i )-th birth (idem). If we assume that the births are ordered increasingly, then τ = id and σ can be b B defined directly by σ =[ j j ... j ], the indices of the deaths when they are ordered B 1 2 n increasingly. Example 2.10 Figure 4A shows an example of a strict barcode. Its birth permutation is τ =[3241], since b < b < b < b . 3 2 4 1 Similarly, its death permutation is τ =[1342], since d < d < d < d .The d 1 3 4 2 −1 permutation σ associated to the barcode of Fig. 4Ais σ =[4132]= τ τ . B B d Figure 4B shows the same barcode with the bars ordered by birth times. The corre- sponding permutations τ =[1234] and τ =[4132] are different, but the product b d −1 σ = τ τ =[4132] is the same, as it does not depend on the indexing of the bars. B d Further examples are depicted in Fig. 5. We extend Definition 2.8 to non-strict barcodes in Sect. 4.3. 2.2 Background on Coxeter groups and complexes 2.2.1 Coxeter groups Coxeter groups form a family of groups that was defined by Tits in its modern form. They are abstract versions of reflection groups; in fact, the family of finite Coxeter 123 Stratifying the space of barcodes… groups coincides with the family of finite reflection groups. Besides their close con- nections to geometry and topology Davis et al. (2015), Coxeter groups have a rich combinatorial theory Björner et al. (2005). They appear in many areas of mathemat- ics, e.g. as Weyl groups in Lie theory. We will view Sym as one of the most basic examples of a Coxeter group. Usually, one does not consider a Coxeter group W by itself but instead a Cox- eter system (W , S), where S is a generating set of W that consists of involutions called the simple reflections. In what follows, we will tacitly assume that such a set of simple reflections is always fixed when we talk about a Coxeter group W.In the case where W = Sym , we will take S to be the set of adjacent transpositions S = {(i , i + 1) | 1 ≤ i ≤ n − 1}. A rank-(|S|− 1 − k) (standard) parabolic subgroup of W is a subgroup of the form P = T , where T ⊂ S is a subset of size (|S|−1−k). 2.2.2 Coxeter complexes Each Coxeter group W can be assigned a simplicial complex (W ),the Coxeter complex, that is equipped with an action of W.If W is a finite group with set of simple reflections S, the complex (W ) is a triangulation of a sphere of dimension |S|− 1. Coxeter complexes have nice combinatorial properties and are in particular colourable flag complexes Abramenko et al. (2008) [Sect. 1.6] that are shellable Björner (1984). The top-dimensional simplices of (W ) are in one-to-one correspondence with the elements of the group W . Furthermore, one recovers the Cayley graph of (W , S) as the chamber graph of (W ), i.e. the graph that has a vertex for each top-dimensional simplex of (W ) and an edge connecting two vertices if the corresponding simplices share a codimension-1 face Abramenko et al. (2008) [Corollary 1.75]. More generally, the set of k-simplices in (W ) is in one-to-one correspondence with the cosets of rank-(|S|− 1 − k) parabolic subgroups of W : Definition 2.11 The Coxeter complex (W ) of the Coxeter system (W , S) is defined as the simplicial complex (W ) = W /P ={τ P | τ ∈ W , T ⊆ S}, T T T ⊆S where each simplex τ P has dimension dim(τ P ) =|S \T |−1 and the face relation T T is defined by the partial order τ P ≤ τ P  ⇔ τ P ⊇ τ P  . (2) T T T T The group W acts simplicially on (W ) by left multiplication on the cosets, γ · (τ P):=γτ P. Remark 2.12 With a slight abuse of notation, we will in what follows often use the cosets τ P to also denote simplices in the geometric realisation of the Coxeter complex. Note that we take the (combinatorial) convention that this simplicial complex has a unique face of dimension −1. This face does not appear in the geometric realisation. 123 B. Brück, A. Garin Fig. 6 The geometric realisation of the Coxeter complex (Sym ). The permutation corresponding to each triangle of the front of the sphere is indicated in black. The hyperplanes x = x depicted in colours i j correspond to the transpositions (i , j ). The hyperplanes corresponding to adjacent transpositions (i , i + 1) are in boldface. A detailed description of how to obtain such a geometric realisation of the Coxeter complex can be found in Sect. 3 To be coherent with the definition of a stratification (Definition 2.13), we will always consider these simplices to be closed. 2.2.3 The Coxeter complex (Sym ) For the case W = Sym that we are interested in, the Coxeter complex n n (Sym ) is of dimension n −2 and is isomorphic to the barycentric subdivision of the boundary of an (n−1)-simplex. It can be realised geometrically as a triangulation of the (n − 2)-sphere. This complex is the dual to the permutohedron of order n (see Fig. 3). Figure 6 depicts the Coxeter complex (Sym ). The top-dimensional simplices of (Sym ) are in one-to-one correspondence with the elements of Sym . Two such n n simplices share a codimension-1 face if and only if the corresponding permutations differ by precomposing with an adjacent transposition (i , i + 1), i.e. by exchanging two neighbouring entries of the permutation. As a consequence, if x lies in the interior of a maximal simplex of the geometric realisation of (Sym ), it can be assigned a permutation τ ∈ Sym .If x lies on a face of dimension k, then τ is well-defined only up to applying an element of a parabolic subgroup P ≤ Sym that is generated by |S|− 1 − k = n − 2 − k adjacent transpositions. A concrete embedding of (Sym ) in R will be described in more detail in Sect. 3. n−2 For later reference, we note that the identification S = (Sym ) gives a strat- ification of the sphere by its simplicial decomposition. The strata are the (closed) simplices of the geometric realisation and the stratification is over the partially ordered set (poset) specified by Eq. (2). Definition 2.13 Bridson et al. (1999)Aset X is stratified over a poset P if there exists a collection of subsets {X } of X such that: i i ∈P 123 Stratifying the space of barcodes… 1. X = X ; 2. i ≤ j if and only if X ⊆ X ; i j 3. If X ∩ X =∅, then it is a union of strata; i j 4. For every x ∈ X, there exists a unique i ∈ P such that X = X . x i i X x x Each X is called a stratum. 3 Coxeter complex coordinates on R In this section, we describe R as the product of a cone over the Coxeter complex (Sym ) with a 1-dimensional space orthogonal to it. This description is obtained by describing a standard way for realising Sym as a reflection group Abramenko et al. (2008) [Example 1.11]. In terms of Coxeter groups, this is often called the “dual representation”, see e.g. Abramenko et al. (2008) [Sect. 2.5.2]. Example 3.4 below goes through the following steps in detail for the case n = 3. n 2 In what follows, we will consider R with the l -norm · that is induced by the standard scalar product ·, · .Welet e ,..., e denote the standard basis. The 1 n symmetric group Sym acts on R by permuting this standard basis. This action can be expressed in coordinates as γ · (x ,..., x ) = (x ,..., x ). (3) −1 −1 1 n γ (1) γ (n) It is norm-preserving and fixes the 1-dimensional subspace L = e spanned by e:=e + ··· + e = (1,..., 1). Hence, there is an induced action on the orthogonal 1 n complement V = e , which can be described as n n V = (x ,..., x ) ∈ R  x = 0 . 1 n i i =1 Note that L is the subspace consisting of all (x ,..., x ) ∈ R where x = x for all 1 n i j i , j. So in particular, every (x ,..., x ) ∈ R \ L has at least two coordinates that are 1 n different from one another. The subspace V has a natural structure of a cone over the Coxeter complex (Sym ) associated to Sym ,see Remark 3.3. The transposition (i , j ) ∈ Sym acts on V by n n orthogonal reflection along the hyperplane (x ,..., x ) ∈ R x = x , 1 n i j permuting the i-th and j-th coordinates. Let H be the collection of all these hyper- planes, and let S denote the (n − 2)-sphere of radius r > 0 around the origin in V (with respect to the norm induced by the restriction of the standard scalar product on R ), i.e. S ={v ∈ V |v= r }. Lemma 3.1 (Abramenko et al. (2008) [Examples 1.10, 1.4.7 & 1.81)] The hyperplanes H induce a triangulation of S . The resulting simplicial complex  is isomorphic to the Coxeter complex (Sym ) as Sym -spaces. n n 123 B. Brück, A. Garin The set of points x ∈ R such that all coordinates are different is the configuration space Conf (R) ={(x ,..., x ) ∈ R | i = j ⇒ x = x }. n 1 n i j The previous lemma describes how a permutation in Sym can be associated to each point x ∈ Conf (R). To understand why this is true, observe that if C is a connected component of S \ H, then for all (x ,..., x ) ∈ C: r 1 n • If i = j, then x = x , i.e. (x ,..., x ) ∈ Conf (R); i j 1 n n • If (y ,..., y ) ∈ C, then y < y if and only if x < x . 1 n i j i j In particular, there is a unique τ ∈ Sym such that (x ,..., x ) ∈ C ⇐⇒ x < x < ··· < x . (4) 1 n τ(1) τ(2) τ(n) In other words, the order of the elements x ,..., x is given by τ((1,..., n)),see 1 n Fig. 6 above for the case n = 4. The connected components of S \ H are exactly the (interiors of) the maximal simplices of . Sending each such component C to the facet of (Sym ) that corresponds to the permutation τ defined by Eq. 4 gives the desired isomorphism  = (Sym ). Using spherical coordinates, we can express every point v ∈ V in terms of a radial component r > 0 and an angular component, which is equivalent to specifying a point v ∈ S (i.e. a point in the geometric realisation of (Sym )). The upshot of this is θ r that we obtain a new set of coordinates for points in R \ L. Proposition 3.2 Let n ≥ 2. There exist two projection maps p : R −→ R × R : x →,(x¯ , v ), ≥0 x 1/2 n n 1 2 where x¯ = x and v = |x −¯x | , and i x i n i =1 i =1 q : R \ L −→ (Sym ) that define a bijection ( p n , q) : R \ L −→ R × R × (Sym ). >0 R \L n Let Sym act on R by permuting the coordinates (Eq. 3) and on the product R × R × (Sym ) by extending the action on (Sym ) trivially on the first two >0 n n factors. Then the map ( p| , q) is Sym -equivariant. R \L n n n Proof For every x ∈ R , the orthogonal decomposition R = e ⊕ V gives a unique way to write x =¯x · e + v with x¯ ∈ R and v ∈ V , where x x n n e, x 1 x¯ = = x /n = x . i i e, e n i =1 i =1 123 Stratifying the space of barcodes… We can describe the projection v = x −¯x · e ∈ V in spherical coordinates. Its norm (the radius of the sphere) is 1/2 v =x −¯x · e= |x −¯x | , x i i =1 so v is determined by this value together with a point x on the (n − 2)-sphere S , x θ v or equivalently on the geometric realisation of (Sym ). Notice that x ∈ L if and only if v = 0, as the line L intersects V at its origin. We define the map p : R −→ R × R : x → (x¯ , v ) and the map q : ≥0 x n n−2 R \ L −→ S : x → x . The point x is well-defined since x ∈ / L and therefore θ θ there exist i , j such that x = x . It is easy to see that ( p| n , q) is a bijection, i j R \L i.e. that given c ∈ R, c ∈ R and c ∈ (Sym ), there is a unique x ∈ R \ L 1 2 >0 3 such that c =¯x, c =v  and c = x . 1 2 x 3 θ The fact that ( p n , q) is Sym -equivariant follows from Lemma 3.1 and because R \L n permuting the coordinates of x ∈ R changes neither the average x nor the 1/2 standard deviation |x −¯x | . To summarise, every point x = (x ,..., x ) ∈ R \ L determines the following 1 n three things: 1 n 1. Its projection to L, given by x¯ = x ∈ R; i =1 1/2 2. The norm of its projection to V , given by v = |x −¯x | ∈ R ; x i >0 i =1 3. A point x in the geometric realisation of the Coxeter complex (Sym ) associated to Sym . Furthermore, x is uniquely determined by these three coordinates. Remark 3.3 There is an isomorphism R ×(Sym ) cone((Sym ))\{∗}, where >0 n n cone((Sym )) = (Sym ) ×[0, ∞) /(x , 0) ∼ (y, 0) n n n n and ∗ is the cone point, i.e. the equivalence class of (x , 0). Since R = R \ L  L, the above map ( p n , q) gives rise to a decomposition R = cone((Sym )) × R. R \L n n n Indeed, the line L ⊂ R corresponds to points x ∈ R with v = 0, which could be seen as “spheres of radius 0” in the projection q. Example 3.4 We go through the previous construction in detail for the case of R equipped with the natural action of the symmetric group Sym , illustrating the exam- ple in Fig. 7. Consider R = e , e , e . The symmetric group Sym acts on it by 1 2 3 permuting the coordinates of each vector (x , x , x ): 1 2 3 γ · (x , x , x ) = (x −1 , x −1 , x −1 ). 1 2 3 γ (1) γ (2) γ (3) Each γ ∈ Sym can be written as a product of transpositions (i , j ) and its action on R is given by the performing the corresponding sequence of reflections along the 123 B. Brück, A. Garin Fig. 7 Example of the decomposition of R in Coxeter coordinates hyperplanes x = x . The three (2-dimensional) planes corresponding to the equations i j x = x , x = x and x = x are indicated as lines on the left hand side of Fig. 7 to 1 2 2 3 1 3 make the picture clearer. The subspace L that is invariant under this action is spanned by the vector (1, 1, 1) = e, shown in red in Fig. 7. 3 ⊥ We can define new coordinates on R , lying in e = L and e = V,a2- dimensional subspace whose affine shift is depicted in green in Fig. 7, reflecting 3 3 the decomposition of R into a product of e and V . A point x ∈ R can now be written as x¯ · e + v , where x¯ ∈ R and v ∈ V . x x We show on the right hand side of Fig. 7 how V , represented as R , has the structure of a cone over a Coxeter complex. The figure shows the projections of the planes x = x , x = x and x = x and the intersection of V with the subspace e (red 1 2 2 3 1 3 dot). To obtain the cone structure on V , we give it spherical coordinates (i.e. polar coordinates in this case). The first coordinate is the radius r, which determines a 1- sphere centred at the origin (the black circle). On the circle, a point v is determined by an angle x . Intersecting the circle with the hyperplanes, we decompose it into | Sym |= 6 (coloured) strata indexed by the symmetric group and forget about the angle x . For instance, if v = (v ,v ,v ) with v <v <v , the point v lies in θ 1 2 3 2 3 1 the stratum indexed by [231]; this is the unique region that lies on those sides of the hyperplanes that satisfy x > x , x < x and x > x . 1 2 2 3 1 3 Let γ = (12).Itactson v via γ · v = (v −1 ,v −1 ,v −1 ) = (v ,v ,v ).We 2 1 3 γ (1) γ (2) γ (3) γ γ γ γ denote its image by v :=γ · v. The order of the coordinates of v satisfies v ≤ v ≤ 1 3 γ γ v ,so v lies in the stratum indexed by the permutation [132]. The image v of v through the action of γ corresponds to the reflection through the hyperplane x = x . 1 2 Remark 3.5 There are two special cases in Proposition 3.2, when x = x for all i , j, i j i.e. (x ,..., x ) ∈ L and when x = x for all i = j, i.e. (x ,..., x ) ∈ Conf (R). 1 n i j 1 n n For the former, we have p(x ) = (x¯ , v ) = (x , 0) and x is not defined. For the x i θ latter, q(x ) = x lies in the interior of a top-dimensional simplex of (Sym ). Hence, it determines a unique element τ ∈ Sym . In fact, these are just the two extremes of a family of situations that can occur: 123 Stratifying the space of barcodes… If x = x for some i = j, then x lies on the corresponding hyperplane in H and i j θ hence on a lower-dimensional face of (Sym ). There exists a permutation τ ∈ Sym n n such that x ≤ x ≤ ··· ≤ x , τ(1) τ(2) τ(n) but τ is not unique. It is defined only up to multiplication by the subgroup P = γ ∈ Sym x = x . τ(i ) τγ (i ) Note that P is generated by adjacent transpositions (i , i + 1), i.e. it is of the form T , where T ⊂ S is a subset of the set S of simple reflections of Sym . Hence, it is a parabolic subgroup of Sym (see Sect. 2.2). The number of adjacent transpositions in P depends on how many coordinates of (x ,..., x ) agree, or, equivalently, the 1 n number of hyperplanes in H it lies on. Intuitively speaking, one could phrase this as “the more of the x ’s take the same value, the less ‘permutation information’ is left”. The coset τ P ={ρ ∈ Sym | x ≤ ··· ≤ x }, ρ(1) ρ(n) corresponds to the lowest dimensional face of (Sym ) that x lies on. It depends only on the values of the x , not on the choice of τ.If x ∈ L,wehave τ P = Sym . This could be interpreted as the degenerate case where x lies on the unique (−1)- dimensional face of (Sym ) (see Definition 2.11). 4 Coxeter coordinates for the space of barcodes We are finally ready to turn to our main goal, namely to describe a stratification of B . Recall that this will decompose B into different regions, where each region is n n characterised as the set of all barcodes having the same average birth and death, the same standard deviation of births and deaths and the same permutation type. 4.1 Describing B as a quotient 2n In this section, we describe B as a subset of a quotient of R . This will be used in the next section to equip this space with Coxeter complex coordinates. n n Let X := Sym \R × R , where Sym acts diagonally by permuting the coordi- n n nates, i.e. for γ ∈ Sym ,weset γ · (x ,..., x , y ,..., y ) = (x −1 ,..., x −1 , y −1 ,..., y −1 ). 1 n 1 n γ (1) γ (n) γ (1) γ (n) The elements of X are equivalence classes of tuples (x ,..., x , y ,..., y ) ∈ R × 1 n 1 n R , which are denoted by [x ,..., x , y ,..., y ]. 1 n 1 n 123 B. Brück, A. Garin n n Remark 4.1 We write X := Sym \R × R to emphasise that Sym acts from the left n n on this space. The reason we stress this is that later on, we will combine the statements here with descriptions of the Coxeter complex. There, the simplices are given by cosets τ P and the symmetric group acts on them by left multiplication. There is a map φ from the space of barcodes with n bars to X given by n n φ : B → X = Sym \R × R {(b , d )} →[b ,..., b , d ,..., d ]. i i i ∈{1,...,n} 1 n 1 n The image of φ is independent of the choice of indices for the bars of the barcode because the action of Sym is factored out. The map φ is clearly injective, but it is not surjective as the birth time of a homology class is always smaller than its death time. The image of φ is the subspace Y of X given by n n Y := Sym \ (x ,..., x , y ,..., y ) ∈ R × R x < y ∀ i . 1 n 1 n i i For later reference, we note this observation in the following. n n Proposition 4.2 The map φ defines a bijection B → Y ⊂ Sym \R × R . In Sect. 5, we equip B with metrics inspired by the bottleneck and Wasserstein distances. The map φ is an isometry with respect to these metrics. 4.2 Coxeter complexes for birth and death We now introduce the Coxeter complex coordinates for B . These coordinates are obtained by applying the map ( p n , q) of Proposition 3.2 to the two copies of R R \L in Y . Theorem 4.3 Every barcode B = {(b , d )} ∈ B such that at least two of the i i i ∈{1,...,n} n b and two of the d are different from each other determines the following five data: i i 1. Its average birth time b = b /n ∈ R; i =1 2. Its average death time d = d /n ∈ R; i =1 1/2 3. Its birth standard deviation v = |b − b| ∈ R ; b i >0 i =1 1/2 4. Its death standard deviation v = |d − d| ∈ R ; d i >0 i =1 5. An orbit Sym ·(b , d ) ∈ Sym \(Sym ) × (Sym ). θ θ n n n n Furthermore, these five data uniquely determine B. Proof Let B = {(b , d )} be such that at least two b and two d are different. i i i i i ∈{1,...,n} By assumption, both (b ,..., b ) and (d ,..., d ) are points in R \ L. The image 1 n 1 n of B under φ (Proposition 4.2)is n n φ(B) =[b , ..., b , d , ..., d ]∈ Sym \(R \ L × R \ L). 1 n 1 n 123 Stratifying the space of barcodes… Since the map ( p| n , q) is Sym -equivariant (Proposition 3.2), it induces a bijection R \L n n n Sym \ R \ L × R \ L Sym \ (R × R × (Sym )) × (R × R × (Sym )) . >0 >0 n n n The image of [b , ..., b , d , ..., d ] under this bijection is the Sym -orbit of 1 n 1 n ¯ ¯ ( p| n , q) (b , ..., b , d , ..., d ) = (b, v , b , d, v , d ). 1 n 1 n b θ d θ R \L ¯ ¯ The claim now follows since the action of Sym on (b, v , b , d, v , d ) is b θ d θ ¯ ¯ trivial on b, v , d, v  and is given by the action of Sym on the Coxeter complex b d (Sym ) for b , d . θ θ 4.3 A stratification of B In this section, we describe the stratification that we obtain from the description of B in terms of Coxeter complexes. We start by extending Definition 2.8, the permutation assigned to a strict barcode, to the general case of B . For non-strict barcodes, we cannot uniquely assign a permu- tation. However, there is a nice description of the set of all possible such permutations in terms of double cosets of parabolic subgroups: Definition 4.4 For a barcode B = {(b , d )} ∈ B ,let τ and τ be elements i i n b d i ∈{1,...,n} of Sym such that b ≤ ··· ≤ b and d ≤ ··· ≤ d .Let τ (1) τ (n) τ (1) τ (n) n b b d d B B P = γ ∈ Sym b = b , P = γ ∈ Sym d = d . τ (i ) τ γ(i ) τ (i ) τ γ(i ) n n b b b d d d −1 B B The double coset D associated to B is defined as D :=P τ τ P . B B d b b d Remark 4.5 Note that while τ and τ depend on the ordering of the barcode, P and b d B B B P do not. The groups P and P are parabolic subgroups of Sym , as was observed d b d n in Remark 3.5. The cosets τ P ={ρ ∈ Sym | b ≤ ··· ≤ b } b ρ(1) ρ(n) b n and τ P ={ρ ∈ Sym | d ≤ ··· ≤ d }, d ρ(1) ρ(n) d n which are the sets of permutations that preserve the order of the b and d respectively, i i B −1 do not depend on the indexing of B either. Hence, the double coset D = (τ P ) · B b τ P is indeed an invariant of the barcode B. Furthermore, if B is a strict barcode, B B −1 then P = {id} = P ,so D = τ τ = {σ } and we recover the definition of B d B b d b Kanari et al. (2020) as given in Definition 2.8. 123 B. Brück, A. Garin Example 4.6 Let B ={(b , d ) = (1, 10), (b , d ) = (2, 5), (b , d ) = (4, 5), (b , d ) = (4, 7)}∈ B . 1 1 2 2 3 3 4 4 4 One has b < b < b = b and d = d < d < d .Let τ =[1234] and 1 2 3 4 2 3 4 1 b τ =[2341]. They satisfy b ≤ ··· ≤ b and d ≤ ··· ≤ d respectively, d τ (1) τ (4) τ (1) τ (4) b b d d but so do τ =[1243] and τ =[3241]. In this case, one has P ={id,(34)}, b d b B B B P ={id,(12)} and τ P ={[1234], [1243]}, τ P ={[2341], [3241]}. The double b d d b d coset −1 B B D ={γ τ τ γ | γ ∈ P ,γ ∈ P } B b d d b d b d −1 −1 −1  −1 ={τ τ ,τ τ ,τ τ ,τ τ } d d d d b b b b ={[2341], [2431], [3241], [4231]} is the set of all the permutations σ that satisfy that the j-th death (in increasing order) is paired with the σ( j )-th birth. Recall that the Coxeter complex (Sym ) is a simplicial complex with simplices given by cosets of parabolic subgroups τ P. This simplicial decomposition gives it the structure of a stratified space over the poset of cosets of parabolic subgroups equipped with reverse inclusion (see Sect. 2.2). Taking the cone and products of these simplices yields a decomposition of 2n R = cone((Sym )) × R × cone((Sym )) × R (5) n n into strata that are compatible with the action of Sym , i.e. each stratum is sent to another stratum of same dimension by the action of Sym . This follows from Remark 3.3 and the fact that (Sym ) is stratified and the map ( p n , q) of Propo- n R \L sition 3.2 is Sym -equivariant. The strata in Eq. (5) are indexed by pairs of cosets (τ P ,τ P ), where τ ,τ ∈ Sym and P , P ≤ Sym are parabolic subgroups . 1 1 2 2 1 2 1 2 n n The partial ordering on these pairs is given component-wise by reverse inclusion [cf. Eq. (20]. 2n It follows that the quotient X = Sym \R is stratified over the quotient P of this poset by the action of Sym . More concretely, P can be described as follows: The elements of P are orbits of the form Sym ·(τ P ,τ P ), where τ ,τ ∈ Sym and 1 1 2 2 1 2 n n P , P ≤ Sym are parabolic subgroups. The partial ordering is given by 1 2 Sym ·(τ P ,τ P ) ≤ Sym ·(τ P ,τ P ) 1 1 2 2 n n 1 1 2 2 if there is γ ∈ Sym such that τ P ⊇ γτ P and τ P ⊇ γτ P . 1 1 2 2 1 1 2 2 2 n n Note that, following Remark 3.5, the points in Conf (R) × Conf (R) ⊂ R × R are exactly the ones n n n n that belong to the top-dimensional strata. Similarly, the points of L × L ⊂ R × R belong to the lowest dimensional strata, corresponding to the cone points in Eq. (5). 123 Stratifying the space of barcodes… This quotient poset P has a more explicit description in terms of another poset Q, which consists of “marked” double cosets of parabolic subgroups: Definition 4.7 Let Q be the poset consisting of all triples (P , P σ P , P ), where 1 1 2 2 σ ∈ Sym and P , P ≤ Sym are parabolic subgroups and where 1 2 n n (P , P σ P , P ) ≤ (P , P σ P , P ) 1 1 2 2 1 1 2 2 if and only if there is component-wise containment in the reverse direction, P ⊇ P , P ⊇ P and P σ P ⊇ P σ P . 1 2 1 2 1 2 1 2 A very similar poset is also studied as a two-sided version of the Coxeter complex by Hultman Hultman (2007) and Petersen Petersen (2018). We remark that Q is different from the poset of all double cosets of the form P σ P : There can be P = P , P = P 1 2 1 2 1 2 such that P σ P = P σ P (see Petersen (2018)[Remark 4]). 1 2 1 2 Lemma 4.8 The map φ : P → Q −1 Sym ·(τ P ,τ P ) → (P , P τ τ P , P ) 1 1 2 2 1 1 2 2 2 is an isomorphism of posets. Proof To see that φ is a bijection of the underlying sets, consider the following map: ψ : Q → P (P , P σ P , P ) → Sym ·(P ,σ P ). 1 1 2 2 1 2 It is easy to verify that φ and ψ are independent of the choices of representatives and are inverse to one another. That φ is indeed a map of posets, i.e. that it preserves the partial ordering, follows from elementary manipulations of cosets. Theorem 4.9 The set B of barcodes with n bars is stratified over the poset Q. The lowest dimensional stratum containing the barcode B is the stratum corresponding to B B (P , D , P ) ∈ Q.Itisofthe form b d B B (P ,D ,P ) b d B B B = Sym ·(cone(τ P ) × R × cone(τ P ) × R) ∩ Y . n b d n b d 2n Proof Recall that B Y is a subset of X = Sym \R (Proposition 4.2). As observed above, X is stratified over the poset P and, by Lemma 4.8, this poset is isomorphic to Q. It follows that B is also stratified over Q. The strata are obtained by taking the intersection with Y . This stratification is induced by the simplicial structure of the Coxeter complexes in X Sym \ cone((Sym )) × R × cone((Sym )) × R . n n n 123 B. Brück, A. Garin Hence, the strata that contain a barcode B ∈ B only depend on the coordinate Sym ·(b , d ) ∈ Sym \(Sym ) × (Sym ) that B determines by Theorem 4.3. θ θ n n n n As explained in Remark 3.5, the associated points b , d ∈ (Sym ) lie in the interior θ θ B B of the simplices τ P ,τ P . Hence, the lowest dimensional stratum that contains B b d b d B B corresponds to the Sym -orbit of (τ P ,τ P ). b d n b d Let B be a strict barcode, that is, b = b and d = d for i = j. Then B is i j i j contained in the top-dimensional stratum −1 ({id},{id}τ τ {id},{id}) { } { } B = Sym ·(cone(τ id ) × R × cone(τ id ) × R) ∩ Y . n b d Changing the representative of the Sym -orbit, this can be rewritten as ({id},{σ },{id}) B = Sym ·(cone({id}) × R × cone(σ {id}) × R) ∩ Y , n n −1 where σ = τ τ is the permutation associated to B as in Definition 2.8. In partic- B d ular, the strata containing strict barcodes are in one-to-one correspondence with the elements of Sym . When one considers the cone and real line parameters in the stratification of The- orem 4.9, one obtains regions that are determined by the averages and standard deviations of Theorem 4.3 and by parabolic subgroups. Corollary 4.10 The Coxeter coordinates of Theorem 4.3 decompose the space B of barcodes with n bars into disjoint regions. The region containing the barcode B = {(b , d )} ∈ B is defined as the set of all barcodes B such that: i i i ∈{1,...,n} n ¯ ¯ 1. Its average birth time is the same as that of B, i.e. b = b; ¯ ¯ 2. Its average death time is the same as that of B, i.e. d = d; 3. Its birth standard deviation is the same as that of B, i.e. v =v ; b b 4. Its death standard deviation is the same as that of B, i.e. v =v ; d d B B B B 5. P = P ,P = P and D = D . B B b b d d For strict barcodes, the information of the last Item 5 is equivalent to specifying σ , the permutation associated to barcodes in Definition 2.8. 5 A metric on B In this section, we explain how the description of B given in Sect. 4.1 with R equipped with the l -norm gives rise to a naturally defined metric d on B that B n 2 n is closely related to the bottleneck distance. Similarly, the l -norm on R leads to a modified Wasserstein distance d on B . W n 2n ∞ To describe d , we equip R with the metric d induced by the l -norm. This B ∞ metric induces a map X × X → R on the quotient by taking the minimum value over all representatives of the corresponding equivalence classes: 123 Stratifying the space of barcodes… d : X × X → R (6) [x , y], [x , y ] → min d ((x˜ , y ˜), (x˜ , y ˜ )). (x˜,y ˜)∈[x ,y], (x˜ ,y ˜ )∈[x ,y ] We will show that this map restricted to Y agrees with a modified version of the bottleneck distance. Definition 5.1 Let B ={(b , d )} and B ={(b , d )} be two barcodes i i i ∈{1,...,n} i ∈{1,...,n} i i in B .The modified bottleneck distance between B and B is d (B, B ):= min max (b , d ) − (b , d ) . B i i ∞ γ(i ) γ(i ) γ ∈Sym i ∈{1,...,n} ∞ 2 where · is the l -norm on R . Note that the difference between the modified bottleneck distance and the original bottleneck distance as defined in Definition 2.5 is that for the modified version, one does not allow to match points of the barcodes to the diagonal  (see Fig. 8). Furthermore, d (B, B ) is well-defined only if both B and B contain the same number of bars, i.e. if they are both elements of the same B . This is not necessary for the definition of the regular bottleneck distance, cf. Remark 5.3. Proposition 5.2 The map d defines a metric on Y with respect to which φ : (B , d ) −→ (Y , d) is an isometry. n B Proof As observed before in Proposition 4.2, φ maps B bijectively onto Y . Hence, it is sufficient to show that for arbitrary barcodes B and B , d (B, B ) = d(φ (B), φ (B )). This follows from simply spelling out the definitions. For points (x , y) and (x , y ) n n in R × R , d ((x , y), (x , y )) = max |x − x |,..., |x − x |, |y − y |,..., |y − y | ∞ 1 n 1 n 1 n 1 n = max max |x − x |, |y − y | i i i i i =1,...,n = max (x , y ) − (x , y ) , i i ∞ i i i =1,...,n ∞ 2 where · is the l -norm on R . Combining this with the definition of d on X [see Eq. (6)], we obtain d(φ (B), φ (B )) = min d (φ(B), γ · φ(B )) γ ∈Sym = min max (b , d ) − (b , y ) . i i −1 −1 ∞ γ (i ) γ (i ) γ ∈Sym i =1,...,n This is the same as the modified bottleneck distance of Definition 5.1. 123 B. Brück, A. Garin Fig. 8 Two barcodes (red and blue) represented as persistence diagrams in R . A. The matching that minimises the bottleneck or Wasserstein distance matches all the bars to the diagonal, as they are all very close to it. B. If bars are not allowed to be matched with the diagonal, the matching that minimises (b , d ) − (b , y ) for the bottleneck distance or (b , d ) − (b , y ) respectively for i i ∞ i i 2 γ(i ) γ(i ) γ(i ) γ(i ) the Wasserstein distance is different (color figure online) 2n 2 Similarly, starting with R equipped with the l -norm, one can establish an isom- etry between Y and B equipped with a modified Wasserstein distance instead. Remark 5.3 Forgetting about the diagonal as done above opens the door to defining new n n metrics on barcodes by considering distances on R × R and then taking the quotient as was done in this section. It could potentially be extended to barcodes with different number of bars. One could for instance imagine a map that forces matchings between as many bars as possible and then adds a positive weight equal to their distance to the diagonal to the unmatched bars if there are any. This is different from the bottleneck distance (or Wasserstein distance), which allows as many matchings as needed with the diagonal, see Fig. 8. When using barcodes to study data, bars close to the diagonal are usually considered as related to noise. However, there are cases where all the bars matter, for instance when the barcode is the one of a merge tree Kanari et al. (2020); Curry et al. (2021). In such a case, a new metric that does not take the diagonal into account could turn out useful. We leave this for future work. 6 Future directions In this paper, we showed that the space B of barcodes with n bars is stratified over the poset of marked double cosets of parabolic subgroups of Sym . A question that arises is how this could be extended to the whole space of barcodes, i.e. to the union B . An approach here would be to use appropriate inclusions B → B for n m n n∈N m ≤ n. Note that on the group level, there are natural injections Sym → Sym . m n On the level of simplicial complexes, (Sym ) also contains copies of (Sym ) for n m m ≤ n. It was shown in Kanari et al. (2020); Curry et al. (2021) that the permutation σ associated to a strict barcode B gives nice combinatorial insight on the number of merge trees that have the same barcode. This number, called the tree-realisation num- ber (TRN), is derived directly from the permutation. It can also be used to do statistics 123 Stratifying the space of barcodes… on barcodes. Our coordinates (Corollary 4.10) firstly extend this work to any (possibly non-strict) barcode and secondly return a finer invariant than just the permutation. A ¯ ¯ future direction would be to study this finer invariant defined by (b, d, v , v ,σ ). b d B It might be well-suited for studying statistical questions: The first four elements already have descriptions as averages and standard deviations. The behaviour of the permuta- tion σ could be studied using tools from permutation statistics, such as the number of inversions or descents. In a different direction, the description of B in terms of Coxeter complexes allows to rephrase these combinatorial questions in more geometric terms. Using this geometric perspective might give new ways for studying invariants and statistics on barcodes. It would be interesting to see if the geometric and combinatorial tools developed here can help to understand inverse problems in TDA as the ones in Kanari et al. (2020); Curry et al. (2021); Curry (2018); Leygonie et al. (2022). Since the merge tree to barcode problem is related to the symmetric group Kanari et al. (2020); Curry et al. (2021), it is also natural to ask whether the stratification that we obtain in Theorem 4.9 can be extended to the space of merge trees with n leaves. Lastly, the modified bottleneck and Wasserstein distances seem to have a different behaviour than the usual ones. A deeper study of their properties and their potential extension to the space of barcodes (see Remark 5.3) is a natural next step to consider. Acknowledgements This project started from discussions on the space of barcodes with Justin Curry and Brendan Mallery. The authors would also like to thank Jérôme Scherer, Kathryn Hess and Darrick Lee for the fruitful discussions and their useful comments on the manuscript. Funding Open access funding provided by EPFL Lausanne Declarations Conflict of interest On behalf of all authors, the corresponding author states that there is no conflict 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 Abramenko, P., Brown, K.S.: Buildings. Graduate Texts in Mathematics, vol. 248. Springer, New York (2008) Adams, H., Emerson, T., Kirby, M., Neville, R., Peterson, C., Shipman, P., Chepushtanova, S., Hanson, E., Motta, F., Ziegelmeier, L.: Persistence images: a stable vector representation of persistent homology. J. Mach. Learn. Res. 18(8), 1–35 (2017) Adcock, A., Carlsson, E., Carlsson, G.: The ring of algebraic functions on persistence bar codes. Homol. Homot. Appl. 18, 04 (2013) 123 B. Brück, A. Garin Billera, L.J., Holmes, S.P., Vogtmann, K.: Geometry of the space of phylogenetic trees. Adv. Appl. Math. 27(4), 733–767 (2001) Björner, A.: Some combinatorial and algebraic properties of Coxeter complexes and Tits buildings. Adv. Math. 52(3), 173–212 (1984) Björner, A., Brenti, F.: Combinatorics of Coxeter groups. Graduate Texts in Mathematics, vol. 231. Springer, New York (2005) Bridson, M.R., Haefliger, A.: Metric spaces of non-positive curvature. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 319. Springer-Verlag, Berlin (1999) Bubenik, P.: Statistical topological data analysis using persistence landscapes. J. Mach. Learn. Res. 16(01), 77–102 (2015) Byrne, H.M., Harrington, H.A., Muschel, R., Reinert, G., Stolz, B.J., Tillmann, U.: Topological methods for characterising spatial networks: a case study in tumour vasculature (2019) Carlsson, G.: Topology and data. Bull. Am. Math. Soc. (N.S.) 46(2), 255–308 (2009) Carrière, M., Oudot, S., Ovsjanikov, M..: Stable topological signatures for points on 3d shapes. Comput. Graph. Forum 34 (2015). https://doi.org/10.1111/cgf.12692 Crawley-Boevey, W.: Decomposition of pointwise finite-dimensional persistence modules. J. Algebra Appl. 14(05), 1550066 (2015) Curry, J.: The fiber of the persistence map for functions on the interval. J. Appl. Comput. Topol. 2(3), 301–321 (2018) Curry, J., DeSha, J., Garin, A., Hess, K., Kanari, L., Mallery, B.: From Combinatorial and Probabilistic Aspects of a Topological Inverse Problem (2021). https://doi.org/10.48550/ARXIV.2107.11212 Davis, M.W.: The geometry and topology of Coxeter groups. In Introduction to modern mathematics, volume 33 of Adv. Lect. Math. (ALM), pp. 129–142. Int. Press, Somerville (2015) Delgado-Friedrichs, O., Robins, V., Sheppard, A.: Morse theory and persistent homology for topologi- cal analysis of 3D images of complex materials. In 2014 IEEE International Conference on Image Processing (ICIP), vol. 10, pp. 4872–4876 (2014) Di Fabio, B., Ferri, M.: Comparing persistence diagrams through complex vectors. In Murino, V., Puppo, E. (eds) Image Analysis and Processing—ICIAP 2015, pp. 294–305, Springer International Publishing, Cham (2015) Edelsbrunner, H., Harer, J.: Persistent homology—a survey. In Surveys on Discrete and Computational Geometry, volume 453 of Contemp. Math., pp. 257–282. American Mathematical Society, Providence (2008) Gameiro, M., Hiraoka, Y., Izumi, S., Kramár, M., Mischaikow, K., Nanda, V.: A topological measurement of protein compressibility. Jpn. J. Ind. Appl. Math. 32, 1–17 (2015) Ghrist, R.: Barcodes: the persistent topology of data. Bull. Am. Math. Soc. (N.S.) 45(1), 61–75 (2008) Grindstaff, G., Owen, M.: Geometric comparison of phylogenetic trees with different leaf sets (2018). https://doi.org/10.48550/ARXIV.1807.04235 Heydenreich, S., Brück, B., Harnois-Déraps, J.: Persistent homology in cosmic shear: constraining param- eters with topological data analysis. Astron. Astrophys. 648, A74 (2021) Hultman, A.: The combinatorics of twisted involutions in Coxeter groups. Trans. Am. Math. Soc. 359(6), 2787–2798 (2007) Jacquard, E., Nanda, V., Tillmann, U.: The space of barcode bases for persistence modules. J. Appl. Comput. Topol. (2022). https://doi.org/10.1007/s41468-022-00094-6 Kališnik, S.: Tropical coordinates on the space of persistence barcodes. Found. Comput. Math. 19(1), 101–129 (2019) Kanari, L., Dłotko, P., Scolamiero, M., Levi, R., Shillcock, J., Hess, K., Markram, H.: A topological representation of branching neuronal morphologies. Neuroinformatics 16(1), 3–13 (2018) Kanari, L., Garin, A., Hess, K.: From trees to barcodes and back again: theoretical and statistical perspectives. Algorithms 13 (2020). https://doi.org/10.3390/a13120335 Lee, Y., Barthel, S., Dłotko, P., Moosavi, S.M., Hess, K., Smit, B.: High-throughput screening approach for nanoporous materials genome using topological data analysis: Application to zeolites. J. Chem. Theory Comput. 14, 4427–4437 (2018) Leygonie, J., Tillmann, U.: The fiber of persistent homology for simplicial complexes. J Pure Appl Algebra 226 (2022). https://doi.org/10.1016/j.jpaa.2022.107099 123 Stratifying the space of barcodes… Muszynski, G., Kashinath, K., Kurlin, V., Wehner, M.F., Prabhat, M.: Topological data analysis and machine learning for recognizing atmospheric river patterns in large climate datasets. Geosci. Model Dev. 12, 613–628 (2019) Petersen, T.K.: A two-sided analogue of the Coxeter complex. Electr. J. Comb. 25(4), 28 (2018) Postnikov, A.: Permutohedra, associahedra, and beyond. Int. Math. Res. Not. IMRN 6, 1026–1106 (2009) Reimann, M.W., Nolte, M., Scolamiero, M., Turner, K., Perin, R., Chindemi, G., Dlotko, P., Levi, R., Hess, K., Markram, H.: Cliques of neurons bound into cavities provide a missing link between structure and function. Front. Comput. Neurosci. 11 (2017). https://doi.org/10.3389/fncom.2017.00048 Robins, V., Saadatfar, M., Delgado-Friedrichs, O., Sheppard, A.P.: Percolating length scales from topological persistence analysis of micro-CT images of porous materials. Water Resour. Res. 52(1), 315–329 (2016) Xu, C.: A correspondence between schubert cells and persistence diagrams. Master thesis, Kyoto university, Supervisor: Yasuaki Hiraoka (2020) Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Journal of Applied and Computational Topology Springer Journals

Stratifying the space of barcodes using Coxeter complexes

Download PDF
27 pages

Loading next page...
 
/lp/springer-journals/stratifying-the-space-of-barcodes-using-coxeter-complexes-DWBpx3YPV7

References (45)

Publisher
Springer Journals
Copyright
Copyright © The Author(s) 2022
ISSN
2367-1726
eISSN
2367-1734
DOI
10.1007/s41468-022-00104-7
Publisher site
See Article on Publisher Site

Abstract

Embeddings of the space of barcodes in Euclidean spaces are unstable due to the permutation of the bars of a barcode. We use tools from geometric group theory to produce a stratification of the space B of barcodes with n bars that takes into account these permutations. This gives insights in the combinatorial structure of B . The top- dimensional strata are indexed by permutations associated to barcodes as defined by Kanari, Garin and Hess. More generally, the strata correspond to marked double cosets of parabolic subgroups of the symmetric group Sym . This subdivides B into regions that consist of barcodes with the same averages and standard deviations of birth and death times and the same permutation type. We obtain coordinates that form a new invariant of barcodes, extending the one of Kanari–Garin–Hess. This description also gives rise to metrics on B that coincide with modified versions of the bottleneck and Wasserstein metrics. Keywords Barcodes · Topological data analysis · Coxeter complex · Geometric group theory Mathematics Subject Classification 51F15 · 55N31 · 20F55 · 57N80 1 Introduction Barcodes Carlsson (2009); Edelsbrunner et al. (2008); Ghrist (2008) are topological summaries of the persistent homology of a filtered space. The barcode B associated to a filtration {X } is a multiset of points (b, d) ∈ R . It summarises the creation t t ∈R and destruction of homology classes while varying the parameter t, which is often interpreted as “time”. A bar (b, d) ∈ B corresponds to a homology cycle appearing in B Adélie Garin adelie.garin@gmail.com ETH Zurich, Zurich, Switzerland École Polytechnique Fédérale de Lausanne: Ecole Polytechnique Federale de, Lausanne, Switzerland 123 B. Brück, A. Garin X and becoming a boundary in X . The first element of the pair (b, d) is called the b d birth and the second one the death. Persistent homology has applications in many fields, from biology Byrne et al. (2019); Gameiro et al. (2015); Kanari et al. (2018); Reimann et al. (2017) to material science Delgado-Friedrichs et al. (2014); Lee et al. (2018); Robins et al. (2016), astron- omy Heydenreich et al. (2021) and climate science Muszynski et al. (2019). In many of these applications, it is necessary to study statistics on barcodes. Unfortunately, the space of barcodes is not a Hilbert space, which means that it can be difficult to apply statistical methods to it. Several ways to overcome the issue exist, such as the creation of kernels to map barcodes into a Hilbert space Bubenik (2015); Carrière et al. (2015); Adams et al. (2017); Di Fabio et al. (2015). In this paper, we tackle this issue from a different perspective. We use combinatorial tools from geometric group theory to define new coordinates for describing barcodes. These coordinates divide the space of barcodes into regions indexed by the averages and the standard deviations of births and deaths and by the permutation type of a barcode as defined in Kanari et al. (2020); Curry et al. (2021). By associating to a barcode the coordinates of its region, we define a new invariant of barcodes. This opens the door to doing statistics on barcodes using methods from the field of permutation statistics. 1.1 Motivation The motivation for this work is to understand the space of barcodes from a combina- torial and geometric point of view and to show that it almost has a locally Euclidean structure. We call a barcode strict if there are no two pairs in it that have the same birth or death. It was observed in Kanari et al. (2020) that to a strict barcode B = {(b , d )} i i i ∈{1,...,n} with n bars, one can associate a permutation σ ∈ Sym . It is the permutation such that the bar with the i-th smallest death has the σ (i )-th smallest birth. This divides the set of strict barcodes with n bars into n! equivalence classes, one for each element of the symmetric group Sym . Based on this observation, one can study the combinatorial properties of strict barcodes by describing these equivalence classes—or equivalently, the elements of Sym —and the relations between them. A first approach to this, taken in Kanari et al. (2020); Curry et al. (2021), is to consider the Cayley graph of the symmetric group with respect to the generating set given by adjacent transpositions (i , i + 1). This yields a combinatorial representation of the elements of Sym . It tells us how a pair of permutations can be transformed into one another using transpositions one step at a time. However, it yields no information about “higher order relations” that exist among larger sets of permutations. A way to resolve this is to add higher dimensional cells to the Cayley graph and to consider it more geometrically as a cell complex instead of as a (combinatorial) graph. A first approach would be to use that the Cayley graph of Sym is the 1-skeleton of the permutohedron Postnikov (2009) of order n, see Fig. 1. This observation embeds the Cayley graph into a polyhedral decomposition of the (n − 2)-sphere. As this is a more geometric object, it allows to continuously “walk” from one permutation to another. 123 Stratifying the space of barcodes… Fig. 1 The permutohedron Postnikov (2009) of order 4 is a polyhedral decomposition of the sphere where each vertex corresponds to an element of the symmetric group Sym . Its 1-skeleton is the Cayley graph of Sym (see also Fig. 5) Fig. 2 Two barcodes with the same associated permutation (the identity [1234]) but with large differences in their birth and death values The problem is that only the vertices (and not the higher dimensional cells) of the permutohedron have an interpretation in terms of elements of the symmetric group. Furthermore, this representation lacks a notion of “size” for barcodes. For instance, the two barcodes depicted in Fig. 2 lie in the same equivalence class, i.e. have the same associated permutation. The alternative that we suggest to overcome these problems is to work with Coxeter complexes instead of permutohedra. The Coxeter complex associated to Sym is the dual of the permutohedron of order n (see Fig. 3). It forms a simplicial decomposition of the (n − 2)-sphere and is well-studied in the context of reflection groups and Tits buildings. For us, it has the advantage that its top-dimensional simplices correspond in a natural way to permutations and only passing through a face of lower dimension changes such a permutation. This allows for a better description of continuous changes between different permutations. It also has the advantage that it comes with an embedding in R , where the additional two real parameters that are needed to describe positions 123 B. Brück, A. Garin Fig. 3 The permutohedron of order 4 (black) is the dual of the Coxeter complex (Sym ) (grey) relative to this (n − 2)-dimensional space have a natural interpretation in terms of the “size” of barcodes. Moreover, using the Coxeter complex description for barcodes allows to define the permutation type of any barcode. For non-strict barcodes, it is defined only up to parabolic subgroups of Sym , i.e. subgroups that are generated by sets of adjacent transpositions. 1.2 Contributions In this paper, we use Coxeter complexes to develop a description of the set B of barcodes with n bars with coordinates that have natural interpretations when doing statistics with barcodes. These coordinates define a stratification of B where the top- dimensional strata are indexed by the symmetric group Sym . Our main contributions can be summarised as follows. Theorem 1.1 Let B denote the set of barcodes with n bars. 2n 1. B can in a natural way be seen as a subset of a quotient Sym \R . 2. B is stratified over the poset of marked double cosets of parabolic subgroups of Sym . 3. Using this description, one obtains a decomposition of B into different regions. Each region is characterised as the set of all barcodes having the same average birth and death, the same standard deviation of births and deaths and the same permutation type σ ∈ Sym . 4. This description gives rise to metrics on B that coincide with modified versions of the bottleneck and Wasserstein metrics. Intuitively, this means that there are two types of small perturbations of a barcode. One is to perturb it such that one obtains another barcode with the same permutation 123 Stratifying the space of barcodes… type. Such a perturbation takes place in a Euclidean subspace (a single stratum) of B . The other is to change the permutation type and hence going from one Euclidean area (i.e. stratum) to another. For more detailed and formal statements of these results, see Proposition 4.2, Theorem 4.9, Corollary 4.10 and Proposition 5.2. To obtain this description of B we proceed as follows. A barcode is an (unordered) multiset of n pairs of real numbers (births and deaths). It can hence be seen as a n n point in the quotient space Sym \(R × R ), where the action of Sym permutes the n n coordinate pairs. Since the birth is smaller than the death for every barcode, B is a 2n proper subset of this quotient of R . The Coxeter complex (Sym ) associated to Sym is a simplicial complex whose n n geometric realisation is homeomorphic to an (n−2)-sphere. Hence, we can decompose R as R = cone((Sym )) × R, n−1 where cone((Sym )) = (Sym ) ×[0, ∞) /(x , 0) ∼ (y, 0) R .This n n decomposition allows one to describe each point x ∈ R via coordinates x , x¯ , v , θ x where x specifies a point on the Coxeter complex, v  is the “cone parameter” and θ x x¯ parametrises the remaining R (for details, see Proposition 3.2, where the naming becomes clear as well). In summary, this describes B as a subset of B ⊂ Sym \ cone((Sym )) × R × cone((Sym )) × R . n n n We call the coordinates that we obtain from this description Coxeter coordinates. ¯ ¯ It turns out that for each barcode, these coordinates are b , b, v  and d , d, v , θ b θ d ¯ ¯ where b and d are the averages of the births and deaths, v  and v  are their standard b d deviations and the coordinates b and d describe the permutation equivalence class of θ θ the barcode of Kanari et al. (2020); Curry et al. (2021). The stratification one obtains is induced by the simplicial structure of (Sym ). Hence, each stratum is Euclidean. The advantages of these new coordinates are two-fold: Firstly, using points in Cox- eter complexes, one obtains coordinates that uniquely specify barcodes and are yet compatible with the combinatorial structure of B given by permutation equivalence classes. Secondly, one resolves the earlier-mentioned problem that permutation equiv- alence classes themselves carry no notion of “size”: The decomposition of B into regions subdivides these equivalence classes by also taking into account the averages and standard deviations of births and deaths. This makes these regions a finer invari- ant than the permutation type. Therefore, they offer a new way to study statistics of barcodes by using both the average and standard deviation of births and deaths, which are commonly used summaries in Topological Data Analysis (TDA), and permutation statistics tools. The latter include the number of descents for instance, or the inversion numbers, which have proven useful for the study of the inverse problem for trees and barcodes Kanari et al. (2020); Curry et al. (2021). 123 B. Brück, A. Garin 1.3 Related work This paper is a follow-up of the work started in Kanari et al. (2020); Curry et al. (2021) to study the space of barcodes from a combinatorial point of view. It extends the approach of considering permutations to classify barcodes to a finer classification that also takes into account the average and standard deviation of births and deaths. In Xu (2020), the author also observes a connection between barcodes and the symmetric group in a different setting, by studying the space of barcode bases using Schubert cells. Similarly, Jacquard et al. (2022) also studies the space of barcode bases. The idea of giving coordinates to the space of barcodes is not new Di Fabio et al. (2015); Kališnik (Feb 2019). For example, the space of barcodes was given tropical coordinates in Kališnik (Feb 2019). In Adcock et al. (2013), it is mentioned that the space of barcodes can be identified with the n-fold symmetric product of R , and the authors study the corresponding algebra of polynomials associated to the variety. Finally, defining a polyhedral structure on a space to study statistics has been done for spaces of (phylogenetic) trees Billera et al. (2001); Grindstaff and Owen (2018). The connection between phylogenetic trees, merge trees and barcodes is studied in Curry et al. (2021). The polyhedral structure defined in this paper and in Billera et al. (2001) seem to be related, but we leave this as future work. 1.4 Overview In Sect. 2 we review the necessary background on barcodes and on Coxeter complexes. We use a standard way of realising Sym as a reflection group to explain what we mean with “Coxeter coordinates” on R in Sect. 3. We then describe the space B n n of barcodes with n bars in terms of Sym \R × R in Sect. 4.1, before adapting the coordinates of R to B in Sect. 4.2. In Sect. 4.3, we describe the stratification of B n n induced by these coordinates. Corollary 4.10 decomposes the space of barcodes into regions indexed by the average and standard deviation of the births and deaths and the permutation associated to a barcode. Finally, in Sect. 5, we show that B can be given metrics inspired by the bottleneck and Wasserstein distances and that it defines n n an isometry between a subset of Sym \R × R and B . 2 Background 2.1 Background on TDA We start by reviewing the necessary background on TDA. For the reader who is com- pletely new to this, we refer to the reviews Carlsson (2009); Edelsbrunner et al. (2008); Ghrist (2008). Even though this work focuses on the space of barcodes and could be apprehended from a purely combinatorial point of view, we shortly mention where barcodes arise in the field of TDA. This section is not necessary for the understanding of this paper, and we will give the combinatorial definition of barcodes that we use in the next section. 123 Stratifying the space of barcodes… Barcodes are topological summaries of a filtered topological space, i.e. a sequence of spaces ordered by inclusion. To obtain a barcode from a filtered space, one computes homology at each step and considers the maps induced by the inclusions. The output is called a persistence module, and it summarises the evolution of the homology at each step of the filtration. More precisely, let {X } be a filtered topological space, that is, each X is a t t ∈R t topological space and X ⊆ X  if t ≤ t .The k-th persistence module associated to {X } is given by H ({X } ), where H denotes the k-th homology functor t t ∈R k t t ∈R k (over a field k). The Crawley–Bovey Theorem Crawley-Boevey (2015) states that under mild tameness conditions on {X } , the associated persistence module can t t ∈R ⊕n be decomposed as a direct sum of interval modules k , where the interval j ∈J module k is the free k-module of rank 1 on the interval I ⊆ R, with identity maps I j internal to I , and is 0 elsewhere. This decomposition is unique up to reordering. Each interval represents the lifetime of a cycle in the filtered space. For instance, if a 1-cycle (a loop) appears in the topological space X for the first time and becomes a boundary (gets “filled in”) in X , then this 1-cycle will be represented by the interval I =[b , d ).The barcode associated to the persistence module is the multiset j j j B ={I } , j ∈J where each interval I appears n times. Usually, each I is a half open interval j j j I =[b , d ), where b is called the birth of the homological feature corresponding j j j j to I and d is called its death. If the interval I is a half infinite interval, i.e. it is of j j j the form [b , ∞),itiscalledan essential class. In this paper, we will identify such an interval with the pair (b , d ), since we j j are mostly interested in the combinatorics of the pairs and not the corresponding persistence module. Moreover, b and d will always take finite values in R. j j 2.1.1 The space of barcodes We introduce here the main definitions used in this paper. We start by a more combi- natorial definition of barcodes that we will use in this article. Definition 2.1 A barcode {(b , d )} is a multiset of pairs (b , d ) ∈ R such that i i i ∈J i i b < d for each i ∈ J and |J | < ∞. Each such pair is called a bar; its first coordinate i i b is called the birth (time) and the second one d is called its death (time). A barcode i i is called strict if b = b and d = d for i = j.Welet B denote the set of barcodes i j i j n st with n bars and B the set of strict barcodes with n bars. Remark 2.2 The reader familiar with persistent homology will notice that we suppose that the bars corresponding to essential classes have finite values instead of being half- open intervals. This is usually the case in practical applications, where such essential classes are given finite values for representing them on a computer. We also assume that every barcode consists of only finitely many bars. 123 B. Brück, A. Garin Fig. 4 A A barcode with 4 bars. B The same barcode with a different indexing where the bars are ordered by increasing birth times Remark 2.3 The definition of strict barcodes was first introduced in Kanari et al. (2020) to define the bijection between the symmetric group on n elements and some equiv- alence classes of barcodes that we introduce in the next section. The setting in this paper is slightly different from Kanari et al. (2020) and Curry et al. (2021), because all the barcodes considered there are specific to merge trees and arise from their 0-th persistent homology. This is why the definition of a strict barcode in Kanari et al. (2020) and Curry et al. (2021) assumes the existence of an essential bar (b , d ) that 0 0 contains all the others. In this paper however, barcodes can come from arbitrary fil- trations in arbitrary dimension, and such a bar (b , d ) need not exist. Therefore we 0 0 slightly adapt the definition of a strict barcode and the relation to the symmetric group in the next sections. In practice, for finite barcodes, the indexing set J is commonly the set {1, ..., n}, giving the bars in the barcode an arbitrary but fixed ordering. We will also adopt this convention from now on. Note however that reordering the bars might change the indexing, but not the underlying barcode (see Example 2.4). It can sometimes be convenient to assume that the indexing is such that the births are ordered increasingly b < b < ... < b , but we do not make this assumption in this paper unless specified. 1 2 n We often represent a barcode by the set of intervals [b , d ]⊂ R (as in Fig. 4). i i Another common way to represent barcodes is what is called a persistence diagram, where the pairs (b , d ) are represented as points in R (as in Fig. 8). These points lie i i above the diagonal since b < d for all i. i i Example 2.4 Figure 4 shows an example of a strict barcode with two different indexing conventions. To turn the set of barcodes into a topological space, one needs to specify a topology. One option to do this is by introducing the bottleneck or Wasserstein distances, two commonly used metrics for barcodes. Intuitively, the bottleneck distance between two barcodes B and B tries all possible matchings between the bars of B and the bars of B and chooses the one that minimises the “energy” required to move the matched pair of bars with maximal separation. However, it does not only consider matching of bars between B and B but also with points on the diagonal  ={(x , x ) | x ∈ R}. 123 Stratifying the space of barcodes… Definition 2.5 Let B ={(b , d )} and B ={(b , d )} be two bar- i i i ∈{1,...,n} i ∈{1,...,m} i i codes. The bottleneck distance between B and B is d (B, B ) = min maxx − γ(x ) , B ∞ x ∈B where γ runs over all possible matchings, i.e. maps that assign to each bar (b , d ) ∈ B i i either a bar in B or a point in the diagonal , such that no point of B is in the image ∞ 2 more than once. Here, · is the l -norm on R . Remark 2.6 The permutation γ acts as a “reindexing” of the indices of B and B , and in particular ensures that d (B, B ) does not depend on any indexing of the bars. The Wasserstein distance is defined in a similar way by taking the sum over all l -distances between x and γ(x ) instead: d (B, B ) = min  x − γ(x ) ). W x ∈B Remark 2.7 Note that in general, the barcodes B and B need not have the same number of bars. The diagonal allows matchings between barcodes with different number of bars, since “ummatched” bars can be sent to the diagonal. In this paper however, we study the set of barcodes B with exactly n bars (for arbitrary, but fixed n) and restrict ourselves to this case. We are mainly interested in B as a set and the main results we prove do not depend on the metric that is chosen on B . We will still with a slight abuse of notation mostly talk of B as a space, without specifying a specific metric on it. An exception to that is Sect. 5, where we explain how a metric d on B , which is closely related to the B n bottleneck distance, occurs in an alternative description of the set B that we work with later on. 2.1.2 Relation to the symmetric group We write Sym for the symmetric group on n letters, i.e. the group of all permutations of {1,..., n}. We usually use the one-line notation for permutations. That is, we specify σ ∈ Sym by the its image of the ordered set {1,..., n}, e.g. we write σ =[132]∈ Sym if σ(1) = 1, σ(2) = 3 and σ(3) = 2. We make an exception for transpositions to simplify the notation: the transposition that switches i and j is denoted by (i , j ). st Definition 2.8 Kanari et al. (2020)Let B ={(b , d )} ∈ B be a strict bar- i i i ∈{1,...,n} code. If we order the births increasingly such that b < ··· < b , the indexing in i i 1 n {1, ..., n} gives a permutation τ by τ (k) = i , i.e. τ is the (unique) permutation such b b k b that b < ··· < b . (1) τ (1) τ (n) b b Similarly, ordering the deaths d < ··· < d gives rise to a permutation τ with j j d 1 n −1 τ (k) = j .The permutation σ associated to B is defined as σ = τ τ ; it tracks d k B B d the ordering of the death values with respect to the birth values. 123 B. Brück, A. Garin Fig. 5 (Figure from Kanari et al. (2020)) The Cayley graph of Sym generated by the three transpo- sitions (12), (23), (34). Four barcodes are drawn next to the extremities of the graphs (permutations [1234], [2134], [2143], [1243]) to illustrate a typical barcode corresponding to each permutation Remark 2.9 The permutations τ and τ both depend on the indexing choice of the b b d i and d . However, the permutation σ does not depend on any indexing of the births and deaths, it is intrinsic to the multiset B. Indeed, σ can be defined directly as the permutation that sends the i-th death (in increasing order) to the σ(i )-th birth (idem). If we assume that the births are ordered increasingly, then τ = id and σ can be b B defined directly by σ =[ j j ... j ], the indices of the deaths when they are ordered B 1 2 n increasingly. Example 2.10 Figure 4A shows an example of a strict barcode. Its birth permutation is τ =[3241], since b < b < b < b . 3 2 4 1 Similarly, its death permutation is τ =[1342], since d < d < d < d .The d 1 3 4 2 −1 permutation σ associated to the barcode of Fig. 4Ais σ =[4132]= τ τ . B B d Figure 4B shows the same barcode with the bars ordered by birth times. The corre- sponding permutations τ =[1234] and τ =[4132] are different, but the product b d −1 σ = τ τ =[4132] is the same, as it does not depend on the indexing of the bars. B d Further examples are depicted in Fig. 5. We extend Definition 2.8 to non-strict barcodes in Sect. 4.3. 2.2 Background on Coxeter groups and complexes 2.2.1 Coxeter groups Coxeter groups form a family of groups that was defined by Tits in its modern form. They are abstract versions of reflection groups; in fact, the family of finite Coxeter 123 Stratifying the space of barcodes… groups coincides with the family of finite reflection groups. Besides their close con- nections to geometry and topology Davis et al. (2015), Coxeter groups have a rich combinatorial theory Björner et al. (2005). They appear in many areas of mathemat- ics, e.g. as Weyl groups in Lie theory. We will view Sym as one of the most basic examples of a Coxeter group. Usually, one does not consider a Coxeter group W by itself but instead a Cox- eter system (W , S), where S is a generating set of W that consists of involutions called the simple reflections. In what follows, we will tacitly assume that such a set of simple reflections is always fixed when we talk about a Coxeter group W.In the case where W = Sym , we will take S to be the set of adjacent transpositions S = {(i , i + 1) | 1 ≤ i ≤ n − 1}. A rank-(|S|− 1 − k) (standard) parabolic subgroup of W is a subgroup of the form P = T , where T ⊂ S is a subset of size (|S|−1−k). 2.2.2 Coxeter complexes Each Coxeter group W can be assigned a simplicial complex (W ),the Coxeter complex, that is equipped with an action of W.If W is a finite group with set of simple reflections S, the complex (W ) is a triangulation of a sphere of dimension |S|− 1. Coxeter complexes have nice combinatorial properties and are in particular colourable flag complexes Abramenko et al. (2008) [Sect. 1.6] that are shellable Björner (1984). The top-dimensional simplices of (W ) are in one-to-one correspondence with the elements of the group W . Furthermore, one recovers the Cayley graph of (W , S) as the chamber graph of (W ), i.e. the graph that has a vertex for each top-dimensional simplex of (W ) and an edge connecting two vertices if the corresponding simplices share a codimension-1 face Abramenko et al. (2008) [Corollary 1.75]. More generally, the set of k-simplices in (W ) is in one-to-one correspondence with the cosets of rank-(|S|− 1 − k) parabolic subgroups of W : Definition 2.11 The Coxeter complex (W ) of the Coxeter system (W , S) is defined as the simplicial complex (W ) = W /P ={τ P | τ ∈ W , T ⊆ S}, T T T ⊆S where each simplex τ P has dimension dim(τ P ) =|S \T |−1 and the face relation T T is defined by the partial order τ P ≤ τ P  ⇔ τ P ⊇ τ P  . (2) T T T T The group W acts simplicially on (W ) by left multiplication on the cosets, γ · (τ P):=γτ P. Remark 2.12 With a slight abuse of notation, we will in what follows often use the cosets τ P to also denote simplices in the geometric realisation of the Coxeter complex. Note that we take the (combinatorial) convention that this simplicial complex has a unique face of dimension −1. This face does not appear in the geometric realisation. 123 B. Brück, A. Garin Fig. 6 The geometric realisation of the Coxeter complex (Sym ). The permutation corresponding to each triangle of the front of the sphere is indicated in black. The hyperplanes x = x depicted in colours i j correspond to the transpositions (i , j ). The hyperplanes corresponding to adjacent transpositions (i , i + 1) are in boldface. A detailed description of how to obtain such a geometric realisation of the Coxeter complex can be found in Sect. 3 To be coherent with the definition of a stratification (Definition 2.13), we will always consider these simplices to be closed. 2.2.3 The Coxeter complex (Sym ) For the case W = Sym that we are interested in, the Coxeter complex n n (Sym ) is of dimension n −2 and is isomorphic to the barycentric subdivision of the boundary of an (n−1)-simplex. It can be realised geometrically as a triangulation of the (n − 2)-sphere. This complex is the dual to the permutohedron of order n (see Fig. 3). Figure 6 depicts the Coxeter complex (Sym ). The top-dimensional simplices of (Sym ) are in one-to-one correspondence with the elements of Sym . Two such n n simplices share a codimension-1 face if and only if the corresponding permutations differ by precomposing with an adjacent transposition (i , i + 1), i.e. by exchanging two neighbouring entries of the permutation. As a consequence, if x lies in the interior of a maximal simplex of the geometric realisation of (Sym ), it can be assigned a permutation τ ∈ Sym .If x lies on a face of dimension k, then τ is well-defined only up to applying an element of a parabolic subgroup P ≤ Sym that is generated by |S|− 1 − k = n − 2 − k adjacent transpositions. A concrete embedding of (Sym ) in R will be described in more detail in Sect. 3. n−2 For later reference, we note that the identification S = (Sym ) gives a strat- ification of the sphere by its simplicial decomposition. The strata are the (closed) simplices of the geometric realisation and the stratification is over the partially ordered set (poset) specified by Eq. (2). Definition 2.13 Bridson et al. (1999)Aset X is stratified over a poset P if there exists a collection of subsets {X } of X such that: i i ∈P 123 Stratifying the space of barcodes… 1. X = X ; 2. i ≤ j if and only if X ⊆ X ; i j 3. If X ∩ X =∅, then it is a union of strata; i j 4. For every x ∈ X, there exists a unique i ∈ P such that X = X . x i i X x x Each X is called a stratum. 3 Coxeter complex coordinates on R In this section, we describe R as the product of a cone over the Coxeter complex (Sym ) with a 1-dimensional space orthogonal to it. This description is obtained by describing a standard way for realising Sym as a reflection group Abramenko et al. (2008) [Example 1.11]. In terms of Coxeter groups, this is often called the “dual representation”, see e.g. Abramenko et al. (2008) [Sect. 2.5.2]. Example 3.4 below goes through the following steps in detail for the case n = 3. n 2 In what follows, we will consider R with the l -norm · that is induced by the standard scalar product ·, · .Welet e ,..., e denote the standard basis. The 1 n symmetric group Sym acts on R by permuting this standard basis. This action can be expressed in coordinates as γ · (x ,..., x ) = (x ,..., x ). (3) −1 −1 1 n γ (1) γ (n) It is norm-preserving and fixes the 1-dimensional subspace L = e spanned by e:=e + ··· + e = (1,..., 1). Hence, there is an induced action on the orthogonal 1 n complement V = e , which can be described as n n V = (x ,..., x ) ∈ R  x = 0 . 1 n i i =1 Note that L is the subspace consisting of all (x ,..., x ) ∈ R where x = x for all 1 n i j i , j. So in particular, every (x ,..., x ) ∈ R \ L has at least two coordinates that are 1 n different from one another. The subspace V has a natural structure of a cone over the Coxeter complex (Sym ) associated to Sym ,see Remark 3.3. The transposition (i , j ) ∈ Sym acts on V by n n orthogonal reflection along the hyperplane (x ,..., x ) ∈ R x = x , 1 n i j permuting the i-th and j-th coordinates. Let H be the collection of all these hyper- planes, and let S denote the (n − 2)-sphere of radius r > 0 around the origin in V (with respect to the norm induced by the restriction of the standard scalar product on R ), i.e. S ={v ∈ V |v= r }. Lemma 3.1 (Abramenko et al. (2008) [Examples 1.10, 1.4.7 & 1.81)] The hyperplanes H induce a triangulation of S . The resulting simplicial complex  is isomorphic to the Coxeter complex (Sym ) as Sym -spaces. n n 123 B. Brück, A. Garin The set of points x ∈ R such that all coordinates are different is the configuration space Conf (R) ={(x ,..., x ) ∈ R | i = j ⇒ x = x }. n 1 n i j The previous lemma describes how a permutation in Sym can be associated to each point x ∈ Conf (R). To understand why this is true, observe that if C is a connected component of S \ H, then for all (x ,..., x ) ∈ C: r 1 n • If i = j, then x = x , i.e. (x ,..., x ) ∈ Conf (R); i j 1 n n • If (y ,..., y ) ∈ C, then y < y if and only if x < x . 1 n i j i j In particular, there is a unique τ ∈ Sym such that (x ,..., x ) ∈ C ⇐⇒ x < x < ··· < x . (4) 1 n τ(1) τ(2) τ(n) In other words, the order of the elements x ,..., x is given by τ((1,..., n)),see 1 n Fig. 6 above for the case n = 4. The connected components of S \ H are exactly the (interiors of) the maximal simplices of . Sending each such component C to the facet of (Sym ) that corresponds to the permutation τ defined by Eq. 4 gives the desired isomorphism  = (Sym ). Using spherical coordinates, we can express every point v ∈ V in terms of a radial component r > 0 and an angular component, which is equivalent to specifying a point v ∈ S (i.e. a point in the geometric realisation of (Sym )). The upshot of this is θ r that we obtain a new set of coordinates for points in R \ L. Proposition 3.2 Let n ≥ 2. There exist two projection maps p : R −→ R × R : x →,(x¯ , v ), ≥0 x 1/2 n n 1 2 where x¯ = x and v = |x −¯x | , and i x i n i =1 i =1 q : R \ L −→ (Sym ) that define a bijection ( p n , q) : R \ L −→ R × R × (Sym ). >0 R \L n Let Sym act on R by permuting the coordinates (Eq. 3) and on the product R × R × (Sym ) by extending the action on (Sym ) trivially on the first two >0 n n factors. Then the map ( p| , q) is Sym -equivariant. R \L n n n Proof For every x ∈ R , the orthogonal decomposition R = e ⊕ V gives a unique way to write x =¯x · e + v with x¯ ∈ R and v ∈ V , where x x n n e, x 1 x¯ = = x /n = x . i i e, e n i =1 i =1 123 Stratifying the space of barcodes… We can describe the projection v = x −¯x · e ∈ V in spherical coordinates. Its norm (the radius of the sphere) is 1/2 v =x −¯x · e= |x −¯x | , x i i =1 so v is determined by this value together with a point x on the (n − 2)-sphere S , x θ v or equivalently on the geometric realisation of (Sym ). Notice that x ∈ L if and only if v = 0, as the line L intersects V at its origin. We define the map p : R −→ R × R : x → (x¯ , v ) and the map q : ≥0 x n n−2 R \ L −→ S : x → x . The point x is well-defined since x ∈ / L and therefore θ θ there exist i , j such that x = x . It is easy to see that ( p| n , q) is a bijection, i j R \L i.e. that given c ∈ R, c ∈ R and c ∈ (Sym ), there is a unique x ∈ R \ L 1 2 >0 3 such that c =¯x, c =v  and c = x . 1 2 x 3 θ The fact that ( p n , q) is Sym -equivariant follows from Lemma 3.1 and because R \L n permuting the coordinates of x ∈ R changes neither the average x nor the 1/2 standard deviation |x −¯x | . To summarise, every point x = (x ,..., x ) ∈ R \ L determines the following 1 n three things: 1 n 1. Its projection to L, given by x¯ = x ∈ R; i =1 1/2 2. The norm of its projection to V , given by v = |x −¯x | ∈ R ; x i >0 i =1 3. A point x in the geometric realisation of the Coxeter complex (Sym ) associated to Sym . Furthermore, x is uniquely determined by these three coordinates. Remark 3.3 There is an isomorphism R ×(Sym ) cone((Sym ))\{∗}, where >0 n n cone((Sym )) = (Sym ) ×[0, ∞) /(x , 0) ∼ (y, 0) n n n n and ∗ is the cone point, i.e. the equivalence class of (x , 0). Since R = R \ L  L, the above map ( p n , q) gives rise to a decomposition R = cone((Sym )) × R. R \L n n n Indeed, the line L ⊂ R corresponds to points x ∈ R with v = 0, which could be seen as “spheres of radius 0” in the projection q. Example 3.4 We go through the previous construction in detail for the case of R equipped with the natural action of the symmetric group Sym , illustrating the exam- ple in Fig. 7. Consider R = e , e , e . The symmetric group Sym acts on it by 1 2 3 permuting the coordinates of each vector (x , x , x ): 1 2 3 γ · (x , x , x ) = (x −1 , x −1 , x −1 ). 1 2 3 γ (1) γ (2) γ (3) Each γ ∈ Sym can be written as a product of transpositions (i , j ) and its action on R is given by the performing the corresponding sequence of reflections along the 123 B. Brück, A. Garin Fig. 7 Example of the decomposition of R in Coxeter coordinates hyperplanes x = x . The three (2-dimensional) planes corresponding to the equations i j x = x , x = x and x = x are indicated as lines on the left hand side of Fig. 7 to 1 2 2 3 1 3 make the picture clearer. The subspace L that is invariant under this action is spanned by the vector (1, 1, 1) = e, shown in red in Fig. 7. 3 ⊥ We can define new coordinates on R , lying in e = L and e = V,a2- dimensional subspace whose affine shift is depicted in green in Fig. 7, reflecting 3 3 the decomposition of R into a product of e and V . A point x ∈ R can now be written as x¯ · e + v , where x¯ ∈ R and v ∈ V . x x We show on the right hand side of Fig. 7 how V , represented as R , has the structure of a cone over a Coxeter complex. The figure shows the projections of the planes x = x , x = x and x = x and the intersection of V with the subspace e (red 1 2 2 3 1 3 dot). To obtain the cone structure on V , we give it spherical coordinates (i.e. polar coordinates in this case). The first coordinate is the radius r, which determines a 1- sphere centred at the origin (the black circle). On the circle, a point v is determined by an angle x . Intersecting the circle with the hyperplanes, we decompose it into | Sym |= 6 (coloured) strata indexed by the symmetric group and forget about the angle x . For instance, if v = (v ,v ,v ) with v <v <v , the point v lies in θ 1 2 3 2 3 1 the stratum indexed by [231]; this is the unique region that lies on those sides of the hyperplanes that satisfy x > x , x < x and x > x . 1 2 2 3 1 3 Let γ = (12).Itactson v via γ · v = (v −1 ,v −1 ,v −1 ) = (v ,v ,v ).We 2 1 3 γ (1) γ (2) γ (3) γ γ γ γ denote its image by v :=γ · v. The order of the coordinates of v satisfies v ≤ v ≤ 1 3 γ γ v ,so v lies in the stratum indexed by the permutation [132]. The image v of v through the action of γ corresponds to the reflection through the hyperplane x = x . 1 2 Remark 3.5 There are two special cases in Proposition 3.2, when x = x for all i , j, i j i.e. (x ,..., x ) ∈ L and when x = x for all i = j, i.e. (x ,..., x ) ∈ Conf (R). 1 n i j 1 n n For the former, we have p(x ) = (x¯ , v ) = (x , 0) and x is not defined. For the x i θ latter, q(x ) = x lies in the interior of a top-dimensional simplex of (Sym ). Hence, it determines a unique element τ ∈ Sym . In fact, these are just the two extremes of a family of situations that can occur: 123 Stratifying the space of barcodes… If x = x for some i = j, then x lies on the corresponding hyperplane in H and i j θ hence on a lower-dimensional face of (Sym ). There exists a permutation τ ∈ Sym n n such that x ≤ x ≤ ··· ≤ x , τ(1) τ(2) τ(n) but τ is not unique. It is defined only up to multiplication by the subgroup P = γ ∈ Sym x = x . τ(i ) τγ (i ) Note that P is generated by adjacent transpositions (i , i + 1), i.e. it is of the form T , where T ⊂ S is a subset of the set S of simple reflections of Sym . Hence, it is a parabolic subgroup of Sym (see Sect. 2.2). The number of adjacent transpositions in P depends on how many coordinates of (x ,..., x ) agree, or, equivalently, the 1 n number of hyperplanes in H it lies on. Intuitively speaking, one could phrase this as “the more of the x ’s take the same value, the less ‘permutation information’ is left”. The coset τ P ={ρ ∈ Sym | x ≤ ··· ≤ x }, ρ(1) ρ(n) corresponds to the lowest dimensional face of (Sym ) that x lies on. It depends only on the values of the x , not on the choice of τ.If x ∈ L,wehave τ P = Sym . This could be interpreted as the degenerate case where x lies on the unique (−1)- dimensional face of (Sym ) (see Definition 2.11). 4 Coxeter coordinates for the space of barcodes We are finally ready to turn to our main goal, namely to describe a stratification of B . Recall that this will decompose B into different regions, where each region is n n characterised as the set of all barcodes having the same average birth and death, the same standard deviation of births and deaths and the same permutation type. 4.1 Describing B as a quotient 2n In this section, we describe B as a subset of a quotient of R . This will be used in the next section to equip this space with Coxeter complex coordinates. n n Let X := Sym \R × R , where Sym acts diagonally by permuting the coordi- n n nates, i.e. for γ ∈ Sym ,weset γ · (x ,..., x , y ,..., y ) = (x −1 ,..., x −1 , y −1 ,..., y −1 ). 1 n 1 n γ (1) γ (n) γ (1) γ (n) The elements of X are equivalence classes of tuples (x ,..., x , y ,..., y ) ∈ R × 1 n 1 n R , which are denoted by [x ,..., x , y ,..., y ]. 1 n 1 n 123 B. Brück, A. Garin n n Remark 4.1 We write X := Sym \R × R to emphasise that Sym acts from the left n n on this space. The reason we stress this is that later on, we will combine the statements here with descriptions of the Coxeter complex. There, the simplices are given by cosets τ P and the symmetric group acts on them by left multiplication. There is a map φ from the space of barcodes with n bars to X given by n n φ : B → X = Sym \R × R {(b , d )} →[b ,..., b , d ,..., d ]. i i i ∈{1,...,n} 1 n 1 n The image of φ is independent of the choice of indices for the bars of the barcode because the action of Sym is factored out. The map φ is clearly injective, but it is not surjective as the birth time of a homology class is always smaller than its death time. The image of φ is the subspace Y of X given by n n Y := Sym \ (x ,..., x , y ,..., y ) ∈ R × R x < y ∀ i . 1 n 1 n i i For later reference, we note this observation in the following. n n Proposition 4.2 The map φ defines a bijection B → Y ⊂ Sym \R × R . In Sect. 5, we equip B with metrics inspired by the bottleneck and Wasserstein distances. The map φ is an isometry with respect to these metrics. 4.2 Coxeter complexes for birth and death We now introduce the Coxeter complex coordinates for B . These coordinates are obtained by applying the map ( p n , q) of Proposition 3.2 to the two copies of R R \L in Y . Theorem 4.3 Every barcode B = {(b , d )} ∈ B such that at least two of the i i i ∈{1,...,n} n b and two of the d are different from each other determines the following five data: i i 1. Its average birth time b = b /n ∈ R; i =1 2. Its average death time d = d /n ∈ R; i =1 1/2 3. Its birth standard deviation v = |b − b| ∈ R ; b i >0 i =1 1/2 4. Its death standard deviation v = |d − d| ∈ R ; d i >0 i =1 5. An orbit Sym ·(b , d ) ∈ Sym \(Sym ) × (Sym ). θ θ n n n n Furthermore, these five data uniquely determine B. Proof Let B = {(b , d )} be such that at least two b and two d are different. i i i i i ∈{1,...,n} By assumption, both (b ,..., b ) and (d ,..., d ) are points in R \ L. The image 1 n 1 n of B under φ (Proposition 4.2)is n n φ(B) =[b , ..., b , d , ..., d ]∈ Sym \(R \ L × R \ L). 1 n 1 n 123 Stratifying the space of barcodes… Since the map ( p| n , q) is Sym -equivariant (Proposition 3.2), it induces a bijection R \L n n n Sym \ R \ L × R \ L Sym \ (R × R × (Sym )) × (R × R × (Sym )) . >0 >0 n n n The image of [b , ..., b , d , ..., d ] under this bijection is the Sym -orbit of 1 n 1 n ¯ ¯ ( p| n , q) (b , ..., b , d , ..., d ) = (b, v , b , d, v , d ). 1 n 1 n b θ d θ R \L ¯ ¯ The claim now follows since the action of Sym on (b, v , b , d, v , d ) is b θ d θ ¯ ¯ trivial on b, v , d, v  and is given by the action of Sym on the Coxeter complex b d (Sym ) for b , d . θ θ 4.3 A stratification of B In this section, we describe the stratification that we obtain from the description of B in terms of Coxeter complexes. We start by extending Definition 2.8, the permutation assigned to a strict barcode, to the general case of B . For non-strict barcodes, we cannot uniquely assign a permu- tation. However, there is a nice description of the set of all possible such permutations in terms of double cosets of parabolic subgroups: Definition 4.4 For a barcode B = {(b , d )} ∈ B ,let τ and τ be elements i i n b d i ∈{1,...,n} of Sym such that b ≤ ··· ≤ b and d ≤ ··· ≤ d .Let τ (1) τ (n) τ (1) τ (n) n b b d d B B P = γ ∈ Sym b = b , P = γ ∈ Sym d = d . τ (i ) τ γ(i ) τ (i ) τ γ(i ) n n b b b d d d −1 B B The double coset D associated to B is defined as D :=P τ τ P . B B d b b d Remark 4.5 Note that while τ and τ depend on the ordering of the barcode, P and b d B B B P do not. The groups P and P are parabolic subgroups of Sym , as was observed d b d n in Remark 3.5. The cosets τ P ={ρ ∈ Sym | b ≤ ··· ≤ b } b ρ(1) ρ(n) b n and τ P ={ρ ∈ Sym | d ≤ ··· ≤ d }, d ρ(1) ρ(n) d n which are the sets of permutations that preserve the order of the b and d respectively, i i B −1 do not depend on the indexing of B either. Hence, the double coset D = (τ P ) · B b τ P is indeed an invariant of the barcode B. Furthermore, if B is a strict barcode, B B −1 then P = {id} = P ,so D = τ τ = {σ } and we recover the definition of B d B b d b Kanari et al. (2020) as given in Definition 2.8. 123 B. Brück, A. Garin Example 4.6 Let B ={(b , d ) = (1, 10), (b , d ) = (2, 5), (b , d ) = (4, 5), (b , d ) = (4, 7)}∈ B . 1 1 2 2 3 3 4 4 4 One has b < b < b = b and d = d < d < d .Let τ =[1234] and 1 2 3 4 2 3 4 1 b τ =[2341]. They satisfy b ≤ ··· ≤ b and d ≤ ··· ≤ d respectively, d τ (1) τ (4) τ (1) τ (4) b b d d but so do τ =[1243] and τ =[3241]. In this case, one has P ={id,(34)}, b d b B B B P ={id,(12)} and τ P ={[1234], [1243]}, τ P ={[2341], [3241]}. The double b d d b d coset −1 B B D ={γ τ τ γ | γ ∈ P ,γ ∈ P } B b d d b d b d −1 −1 −1  −1 ={τ τ ,τ τ ,τ τ ,τ τ } d d d d b b b b ={[2341], [2431], [3241], [4231]} is the set of all the permutations σ that satisfy that the j-th death (in increasing order) is paired with the σ( j )-th birth. Recall that the Coxeter complex (Sym ) is a simplicial complex with simplices given by cosets of parabolic subgroups τ P. This simplicial decomposition gives it the structure of a stratified space over the poset of cosets of parabolic subgroups equipped with reverse inclusion (see Sect. 2.2). Taking the cone and products of these simplices yields a decomposition of 2n R = cone((Sym )) × R × cone((Sym )) × R (5) n n into strata that are compatible with the action of Sym , i.e. each stratum is sent to another stratum of same dimension by the action of Sym . This follows from Remark 3.3 and the fact that (Sym ) is stratified and the map ( p n , q) of Propo- n R \L sition 3.2 is Sym -equivariant. The strata in Eq. (5) are indexed by pairs of cosets (τ P ,τ P ), where τ ,τ ∈ Sym and P , P ≤ Sym are parabolic subgroups . 1 1 2 2 1 2 1 2 n n The partial ordering on these pairs is given component-wise by reverse inclusion [cf. Eq. (20]. 2n It follows that the quotient X = Sym \R is stratified over the quotient P of this poset by the action of Sym . More concretely, P can be described as follows: The elements of P are orbits of the form Sym ·(τ P ,τ P ), where τ ,τ ∈ Sym and 1 1 2 2 1 2 n n P , P ≤ Sym are parabolic subgroups. The partial ordering is given by 1 2 Sym ·(τ P ,τ P ) ≤ Sym ·(τ P ,τ P ) 1 1 2 2 n n 1 1 2 2 if there is γ ∈ Sym such that τ P ⊇ γτ P and τ P ⊇ γτ P . 1 1 2 2 1 1 2 2 2 n n Note that, following Remark 3.5, the points in Conf (R) × Conf (R) ⊂ R × R are exactly the ones n n n n that belong to the top-dimensional strata. Similarly, the points of L × L ⊂ R × R belong to the lowest dimensional strata, corresponding to the cone points in Eq. (5). 123 Stratifying the space of barcodes… This quotient poset P has a more explicit description in terms of another poset Q, which consists of “marked” double cosets of parabolic subgroups: Definition 4.7 Let Q be the poset consisting of all triples (P , P σ P , P ), where 1 1 2 2 σ ∈ Sym and P , P ≤ Sym are parabolic subgroups and where 1 2 n n (P , P σ P , P ) ≤ (P , P σ P , P ) 1 1 2 2 1 1 2 2 if and only if there is component-wise containment in the reverse direction, P ⊇ P , P ⊇ P and P σ P ⊇ P σ P . 1 2 1 2 1 2 1 2 A very similar poset is also studied as a two-sided version of the Coxeter complex by Hultman Hultman (2007) and Petersen Petersen (2018). We remark that Q is different from the poset of all double cosets of the form P σ P : There can be P = P , P = P 1 2 1 2 1 2 such that P σ P = P σ P (see Petersen (2018)[Remark 4]). 1 2 1 2 Lemma 4.8 The map φ : P → Q −1 Sym ·(τ P ,τ P ) → (P , P τ τ P , P ) 1 1 2 2 1 1 2 2 2 is an isomorphism of posets. Proof To see that φ is a bijection of the underlying sets, consider the following map: ψ : Q → P (P , P σ P , P ) → Sym ·(P ,σ P ). 1 1 2 2 1 2 It is easy to verify that φ and ψ are independent of the choices of representatives and are inverse to one another. That φ is indeed a map of posets, i.e. that it preserves the partial ordering, follows from elementary manipulations of cosets. Theorem 4.9 The set B of barcodes with n bars is stratified over the poset Q. The lowest dimensional stratum containing the barcode B is the stratum corresponding to B B (P , D , P ) ∈ Q.Itisofthe form b d B B (P ,D ,P ) b d B B B = Sym ·(cone(τ P ) × R × cone(τ P ) × R) ∩ Y . n b d n b d 2n Proof Recall that B Y is a subset of X = Sym \R (Proposition 4.2). As observed above, X is stratified over the poset P and, by Lemma 4.8, this poset is isomorphic to Q. It follows that B is also stratified over Q. The strata are obtained by taking the intersection with Y . This stratification is induced by the simplicial structure of the Coxeter complexes in X Sym \ cone((Sym )) × R × cone((Sym )) × R . n n n 123 B. Brück, A. Garin Hence, the strata that contain a barcode B ∈ B only depend on the coordinate Sym ·(b , d ) ∈ Sym \(Sym ) × (Sym ) that B determines by Theorem 4.3. θ θ n n n n As explained in Remark 3.5, the associated points b , d ∈ (Sym ) lie in the interior θ θ B B of the simplices τ P ,τ P . Hence, the lowest dimensional stratum that contains B b d b d B B corresponds to the Sym -orbit of (τ P ,τ P ). b d n b d Let B be a strict barcode, that is, b = b and d = d for i = j. Then B is i j i j contained in the top-dimensional stratum −1 ({id},{id}τ τ {id},{id}) { } { } B = Sym ·(cone(τ id ) × R × cone(τ id ) × R) ∩ Y . n b d Changing the representative of the Sym -orbit, this can be rewritten as ({id},{σ },{id}) B = Sym ·(cone({id}) × R × cone(σ {id}) × R) ∩ Y , n n −1 where σ = τ τ is the permutation associated to B as in Definition 2.8. In partic- B d ular, the strata containing strict barcodes are in one-to-one correspondence with the elements of Sym . When one considers the cone and real line parameters in the stratification of The- orem 4.9, one obtains regions that are determined by the averages and standard deviations of Theorem 4.3 and by parabolic subgroups. Corollary 4.10 The Coxeter coordinates of Theorem 4.3 decompose the space B of barcodes with n bars into disjoint regions. The region containing the barcode B = {(b , d )} ∈ B is defined as the set of all barcodes B such that: i i i ∈{1,...,n} n ¯ ¯ 1. Its average birth time is the same as that of B, i.e. b = b; ¯ ¯ 2. Its average death time is the same as that of B, i.e. d = d; 3. Its birth standard deviation is the same as that of B, i.e. v =v ; b b 4. Its death standard deviation is the same as that of B, i.e. v =v ; d d B B B B 5. P = P ,P = P and D = D . B B b b d d For strict barcodes, the information of the last Item 5 is equivalent to specifying σ , the permutation associated to barcodes in Definition 2.8. 5 A metric on B In this section, we explain how the description of B given in Sect. 4.1 with R equipped with the l -norm gives rise to a naturally defined metric d on B that B n 2 n is closely related to the bottleneck distance. Similarly, the l -norm on R leads to a modified Wasserstein distance d on B . W n 2n ∞ To describe d , we equip R with the metric d induced by the l -norm. This B ∞ metric induces a map X × X → R on the quotient by taking the minimum value over all representatives of the corresponding equivalence classes: 123 Stratifying the space of barcodes… d : X × X → R (6) [x , y], [x , y ] → min d ((x˜ , y ˜), (x˜ , y ˜ )). (x˜,y ˜)∈[x ,y], (x˜ ,y ˜ )∈[x ,y ] We will show that this map restricted to Y agrees with a modified version of the bottleneck distance. Definition 5.1 Let B ={(b , d )} and B ={(b , d )} be two barcodes i i i ∈{1,...,n} i ∈{1,...,n} i i in B .The modified bottleneck distance between B and B is d (B, B ):= min max (b , d ) − (b , d ) . B i i ∞ γ(i ) γ(i ) γ ∈Sym i ∈{1,...,n} ∞ 2 where · is the l -norm on R . Note that the difference between the modified bottleneck distance and the original bottleneck distance as defined in Definition 2.5 is that for the modified version, one does not allow to match points of the barcodes to the diagonal  (see Fig. 8). Furthermore, d (B, B ) is well-defined only if both B and B contain the same number of bars, i.e. if they are both elements of the same B . This is not necessary for the definition of the regular bottleneck distance, cf. Remark 5.3. Proposition 5.2 The map d defines a metric on Y with respect to which φ : (B , d ) −→ (Y , d) is an isometry. n B Proof As observed before in Proposition 4.2, φ maps B bijectively onto Y . Hence, it is sufficient to show that for arbitrary barcodes B and B , d (B, B ) = d(φ (B), φ (B )). This follows from simply spelling out the definitions. For points (x , y) and (x , y ) n n in R × R , d ((x , y), (x , y )) = max |x − x |,..., |x − x |, |y − y |,..., |y − y | ∞ 1 n 1 n 1 n 1 n = max max |x − x |, |y − y | i i i i i =1,...,n = max (x , y ) − (x , y ) , i i ∞ i i i =1,...,n ∞ 2 where · is the l -norm on R . Combining this with the definition of d on X [see Eq. (6)], we obtain d(φ (B), φ (B )) = min d (φ(B), γ · φ(B )) γ ∈Sym = min max (b , d ) − (b , y ) . i i −1 −1 ∞ γ (i ) γ (i ) γ ∈Sym i =1,...,n This is the same as the modified bottleneck distance of Definition 5.1. 123 B. Brück, A. Garin Fig. 8 Two barcodes (red and blue) represented as persistence diagrams in R . A. The matching that minimises the bottleneck or Wasserstein distance matches all the bars to the diagonal, as they are all very close to it. B. If bars are not allowed to be matched with the diagonal, the matching that minimises (b , d ) − (b , y ) for the bottleneck distance or (b , d ) − (b , y ) respectively for i i ∞ i i 2 γ(i ) γ(i ) γ(i ) γ(i ) the Wasserstein distance is different (color figure online) 2n 2 Similarly, starting with R equipped with the l -norm, one can establish an isom- etry between Y and B equipped with a modified Wasserstein distance instead. Remark 5.3 Forgetting about the diagonal as done above opens the door to defining new n n metrics on barcodes by considering distances on R × R and then taking the quotient as was done in this section. It could potentially be extended to barcodes with different number of bars. One could for instance imagine a map that forces matchings between as many bars as possible and then adds a positive weight equal to their distance to the diagonal to the unmatched bars if there are any. This is different from the bottleneck distance (or Wasserstein distance), which allows as many matchings as needed with the diagonal, see Fig. 8. When using barcodes to study data, bars close to the diagonal are usually considered as related to noise. However, there are cases where all the bars matter, for instance when the barcode is the one of a merge tree Kanari et al. (2020); Curry et al. (2021). In such a case, a new metric that does not take the diagonal into account could turn out useful. We leave this for future work. 6 Future directions In this paper, we showed that the space B of barcodes with n bars is stratified over the poset of marked double cosets of parabolic subgroups of Sym . A question that arises is how this could be extended to the whole space of barcodes, i.e. to the union B . An approach here would be to use appropriate inclusions B → B for n m n n∈N m ≤ n. Note that on the group level, there are natural injections Sym → Sym . m n On the level of simplicial complexes, (Sym ) also contains copies of (Sym ) for n m m ≤ n. It was shown in Kanari et al. (2020); Curry et al. (2021) that the permutation σ associated to a strict barcode B gives nice combinatorial insight on the number of merge trees that have the same barcode. This number, called the tree-realisation num- ber (TRN), is derived directly from the permutation. It can also be used to do statistics 123 Stratifying the space of barcodes… on barcodes. Our coordinates (Corollary 4.10) firstly extend this work to any (possibly non-strict) barcode and secondly return a finer invariant than just the permutation. A ¯ ¯ future direction would be to study this finer invariant defined by (b, d, v , v ,σ ). b d B It might be well-suited for studying statistical questions: The first four elements already have descriptions as averages and standard deviations. The behaviour of the permuta- tion σ could be studied using tools from permutation statistics, such as the number of inversions or descents. In a different direction, the description of B in terms of Coxeter complexes allows to rephrase these combinatorial questions in more geometric terms. Using this geometric perspective might give new ways for studying invariants and statistics on barcodes. It would be interesting to see if the geometric and combinatorial tools developed here can help to understand inverse problems in TDA as the ones in Kanari et al. (2020); Curry et al. (2021); Curry (2018); Leygonie et al. (2022). Since the merge tree to barcode problem is related to the symmetric group Kanari et al. (2020); Curry et al. (2021), it is also natural to ask whether the stratification that we obtain in Theorem 4.9 can be extended to the space of merge trees with n leaves. Lastly, the modified bottleneck and Wasserstein distances seem to have a different behaviour than the usual ones. A deeper study of their properties and their potential extension to the space of barcodes (see Remark 5.3) is a natural next step to consider. Acknowledgements This project started from discussions on the space of barcodes with Justin Curry and Brendan Mallery. The authors would also like to thank Jérôme Scherer, Kathryn Hess and Darrick Lee for the fruitful discussions and their useful comments on the manuscript. Funding Open access funding provided by EPFL Lausanne Declarations Conflict of interest On behalf of all authors, the corresponding author states that there is no conflict 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 Abramenko, P., Brown, K.S.: Buildings. Graduate Texts in Mathematics, vol. 248. Springer, New York (2008) Adams, H., Emerson, T., Kirby, M., Neville, R., Peterson, C., Shipman, P., Chepushtanova, S., Hanson, E., Motta, F., Ziegelmeier, L.: Persistence images: a stable vector representation of persistent homology. J. Mach. Learn. Res. 18(8), 1–35 (2017) Adcock, A., Carlsson, E., Carlsson, G.: The ring of algebraic functions on persistence bar codes. Homol. Homot. Appl. 18, 04 (2013) 123 B. Brück, A. Garin Billera, L.J., Holmes, S.P., Vogtmann, K.: Geometry of the space of phylogenetic trees. Adv. Appl. Math. 27(4), 733–767 (2001) Björner, A.: Some combinatorial and algebraic properties of Coxeter complexes and Tits buildings. Adv. Math. 52(3), 173–212 (1984) Björner, A., Brenti, F.: Combinatorics of Coxeter groups. Graduate Texts in Mathematics, vol. 231. Springer, New York (2005) Bridson, M.R., Haefliger, A.: Metric spaces of non-positive curvature. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 319. Springer-Verlag, Berlin (1999) Bubenik, P.: Statistical topological data analysis using persistence landscapes. J. Mach. Learn. Res. 16(01), 77–102 (2015) Byrne, H.M., Harrington, H.A., Muschel, R., Reinert, G., Stolz, B.J., Tillmann, U.: Topological methods for characterising spatial networks: a case study in tumour vasculature (2019) Carlsson, G.: Topology and data. Bull. Am. Math. Soc. (N.S.) 46(2), 255–308 (2009) Carrière, M., Oudot, S., Ovsjanikov, M..: Stable topological signatures for points on 3d shapes. Comput. Graph. Forum 34 (2015). https://doi.org/10.1111/cgf.12692 Crawley-Boevey, W.: Decomposition of pointwise finite-dimensional persistence modules. J. Algebra Appl. 14(05), 1550066 (2015) Curry, J.: The fiber of the persistence map for functions on the interval. J. Appl. Comput. Topol. 2(3), 301–321 (2018) Curry, J., DeSha, J., Garin, A., Hess, K., Kanari, L., Mallery, B.: From Combinatorial and Probabilistic Aspects of a Topological Inverse Problem (2021). https://doi.org/10.48550/ARXIV.2107.11212 Davis, M.W.: The geometry and topology of Coxeter groups. In Introduction to modern mathematics, volume 33 of Adv. Lect. Math. (ALM), pp. 129–142. Int. Press, Somerville (2015) Delgado-Friedrichs, O., Robins, V., Sheppard, A.: Morse theory and persistent homology for topologi- cal analysis of 3D images of complex materials. In 2014 IEEE International Conference on Image Processing (ICIP), vol. 10, pp. 4872–4876 (2014) Di Fabio, B., Ferri, M.: Comparing persistence diagrams through complex vectors. In Murino, V., Puppo, E. (eds) Image Analysis and Processing—ICIAP 2015, pp. 294–305, Springer International Publishing, Cham (2015) Edelsbrunner, H., Harer, J.: Persistent homology—a survey. In Surveys on Discrete and Computational Geometry, volume 453 of Contemp. Math., pp. 257–282. American Mathematical Society, Providence (2008) Gameiro, M., Hiraoka, Y., Izumi, S., Kramár, M., Mischaikow, K., Nanda, V.: A topological measurement of protein compressibility. Jpn. J. Ind. Appl. Math. 32, 1–17 (2015) Ghrist, R.: Barcodes: the persistent topology of data. Bull. Am. Math. Soc. (N.S.) 45(1), 61–75 (2008) Grindstaff, G., Owen, M.: Geometric comparison of phylogenetic trees with different leaf sets (2018). https://doi.org/10.48550/ARXIV.1807.04235 Heydenreich, S., Brück, B., Harnois-Déraps, J.: Persistent homology in cosmic shear: constraining param- eters with topological data analysis. Astron. Astrophys. 648, A74 (2021) Hultman, A.: The combinatorics of twisted involutions in Coxeter groups. Trans. Am. Math. Soc. 359(6), 2787–2798 (2007) Jacquard, E., Nanda, V., Tillmann, U.: The space of barcode bases for persistence modules. J. Appl. Comput. Topol. (2022). https://doi.org/10.1007/s41468-022-00094-6 Kališnik, S.: Tropical coordinates on the space of persistence barcodes. Found. Comput. Math. 19(1), 101–129 (2019) Kanari, L., Dłotko, P., Scolamiero, M., Levi, R., Shillcock, J., Hess, K., Markram, H.: A topological representation of branching neuronal morphologies. Neuroinformatics 16(1), 3–13 (2018) Kanari, L., Garin, A., Hess, K.: From trees to barcodes and back again: theoretical and statistical perspectives. Algorithms 13 (2020). https://doi.org/10.3390/a13120335 Lee, Y., Barthel, S., Dłotko, P., Moosavi, S.M., Hess, K., Smit, B.: High-throughput screening approach for nanoporous materials genome using topological data analysis: Application to zeolites. J. Chem. Theory Comput. 14, 4427–4437 (2018) Leygonie, J., Tillmann, U.: The fiber of persistent homology for simplicial complexes. J Pure Appl Algebra 226 (2022). https://doi.org/10.1016/j.jpaa.2022.107099 123 Stratifying the space of barcodes… Muszynski, G., Kashinath, K., Kurlin, V., Wehner, M.F., Prabhat, M.: Topological data analysis and machine learning for recognizing atmospheric river patterns in large climate datasets. Geosci. Model Dev. 12, 613–628 (2019) Petersen, T.K.: A two-sided analogue of the Coxeter complex. Electr. J. Comb. 25(4), 28 (2018) Postnikov, A.: Permutohedra, associahedra, and beyond. Int. Math. Res. Not. IMRN 6, 1026–1106 (2009) Reimann, M.W., Nolte, M., Scolamiero, M., Turner, K., Perin, R., Chindemi, G., Dlotko, P., Levi, R., Hess, K., Markram, H.: Cliques of neurons bound into cavities provide a missing link between structure and function. Front. Comput. Neurosci. 11 (2017). https://doi.org/10.3389/fncom.2017.00048 Robins, V., Saadatfar, M., Delgado-Friedrichs, O., Sheppard, A.P.: Percolating length scales from topological persistence analysis of micro-CT images of porous materials. Water Resour. Res. 52(1), 315–329 (2016) Xu, C.: A correspondence between schubert cells and persistence diagrams. Master thesis, Kyoto university, Supervisor: Yasuaki Hiraoka (2020) Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Journal

Journal of Applied and Computational Topology – Springer Journals

Published: Jun 1, 2023

Keywords: Barcodes; Topological data analysis; Coxeter complex; Geometric group theory; 51F15; 55N31; 20F55; 57N80

There are no references for this article.