Refinement of Interval Approximations
for Fully Commutative Quivers
Abstract
A fundamental challenge in multiparameter persistent homology is the absence of a complete and discrete invariant. To address this issue, we propose an enhanced framework that realizes a holistic understanding of a fully commutative quiver’s representation via synthesizing interpretations obtained from intervals. Additionally, it provides a mechanism to tune the balance between approximation resolution and computational complexity. This framework is evaluated on commutative ladders of both finite-type and infinite-type. For the former, we discover an efficient method for the indecomposable decomposition leveraging solely one-parameter persistent homology. For the latter, we introduce a new invariant that reveals persistence in the second parameter by connecting two standard persistence diagrams using interval approximations. We subsequently present several models for constructing commutative ladder filtrations, offering fresh insights into random filtrations and demonstrating our toolkit’s effectiveness in analyzing the topology of materials.
Keywords Topological data analysis Multiparameter persistent homology Quiver representation Zigzag persistence Computational topology
1 Introduction
Topological data analysis (TDA) is a rapidly emerging field in applied mathematics that features leveraging algebraic topology tools to solve problems in data science [7]. Persistent homology, a core component of TDA, examines homology modules derived from a filtration of topological spaces constructed based on a given dataset. This filtration provides a multi-scale perspective on the underlying structure of the original data. In this context, the resulting algebraic object can be viewed as a representation of a quiver.
The successes of one-parameter persistent homology, evident in its fruitful applications across diverse domains, such as cosmology [32], medical imaging [30, 9], and material science [16, 20], can be attributed to the structure theorem for finitely generated modules over a principal ideal domain, which lays a solid foundation for utilizing persistence diagrams as a compact descriptor to encode the topological information of a dataset extractable through persistent homology.
Complex topological structures embedded in real-world datasets often require a multiparameter filtration of topological spaces to comprehensively capture and analyze their properties. This led to the development of multiparameter persistent homology, a highly anticipated field promising potential breakthrough in our understanding of complex systems by tracking the evolution of topological features across multiple parameters. However, the non-existence of a discrete and complete invariant [8] in this situation poses a significant challenge, making it crucial to develop new methodologies to advance this field further and enhance its accessibility to a broader spectrum of researchers and data practitioners.
Settings. Our research provides a refined theoretical framework for understanding representations of fully commutative quivers through interval subquivers. The framework builds upon a generalized version of the boundary compression and interval approximation technique proposed in [3]. We validate our new tools on a specific family of fully commutative quivers known as commutative ladders [14], characterized by a two-parameter configuration where the second parameter changes only once (see Figure 1).
Commutative ladders provide a feasible and valuable testbed for our framework. When the ladder length of a commutative ladder is equal to or below four, it possesses a finite representation type, and we can maintain a complete discrete invariant, analogous to the scenario in one-parameter persistent homology. For infinite-type commutative ladders, we introduce a novel invariant based on interval approximations. These two approaches enable the exploration of topological structures in datasets that can be fitted to a commutative ladder filtration.
Related works. The study of multiparameter persistence has made considerable advancements in recent years. Patel’s work generalized persistence diagrams and demonstrated the feasibility of using Möbius inversion to compute them [31]. The concept of interval approximation, introduced by Asashiba et al. [3], serves as a building component for crafting several invariants in multiparameter persistence. Notably, zigzag persistence and Möbius inversion have been explored in the computation of some important invariants. For instance, Kim et al. proposed the generalized rank invariant in [21], and Dey et al. demonstrated that the generalized rank invariant can be computed via boundary caps using zigzag persistence [11]. Kim et al. showed how the bigraded Betti numbers can be calculated from the generalized rank invariants [22]. Botnan et al. proposed a visual representation of the rank invariant in multiparameter persistence modules [6].
Contributions. We present a novel framework for the study of multiparameter persistence modules. Central to our approach is the introduction of “tours” and “courses”, allowing us to track selected compositions of paths satisfying specific properties. Building on this, we enrich the established concept of interval approximation as a linear combination of these courses. This refined notion of interval approximation offers greater flexibility to extract information from a given interval compared with existing methods. As we apply the new framework to two-dimensional commutative grids, a challenge arises: the exponential growth in the number of intervals makes the computation of interval approximations impractical. To address this, we introduce the “partial interval approximation”, an invariant designed to tune the balance between the number of examined intervals and the resolution of the approximation reached.
We then study commutative ladders using the new framework. Starting with finite-type cases, we realize a more streamlined computation of the indecomposable decomposition using only one-parameter zigzag persistence, bypassing the need for 2D representation calculations. This finding helps reveal several new types of courses and paves the way for exploring non-intervals, an aspect of multiparameter persistent homology previously under-investigated. Turning our attention to the infinite-type scenario, we propose a new invariant: the connected persistence diagram. It visualizes persistence in both directions by combining two standard persistence diagrams and then connects homology generators according to their vertical persistence measured by an interval approximation.
To complete the picture and facilitate applicability, we introduce several models tailored for constructing commutative ladder filtrations of simplicial complexes. These models encompass techniques to create filtrations from point cloud data and random simplicial complexes. We then exemplify the versatility of our toolkit through a series of computational demonstrations. Specifically, we study the topological structures of random simplicial complexes and atomic arrangements using commutative ladder configurations. Our computational outcomes highlight the effectiveness of the new framework and commutative ladders as a tool for studying complex data structures. Notably, non-interval components exhibit a markedly lower proportion in configurations derived from point cloud data.
Outline. This paper is organized as follows. In §2, we establish the relevant background and notations used throughout this paper. In §3, we refine interval approximations, propose partial interval approximations, and demonstrate how our framework can be used to construct persistence diagrams of a slice in a 2D persistence module as proposed in RIVET [24]. In §4, we apply our framework to finite-type commutative ladders, yielding an efficient method for computing any indecomposable decomposition, and to infinite-type commutative ladders, yielding a novel diagram to visualize the interval approximations. In §5, we introduce several models for building up commutative ladder filtrations. In §6, we employ the new toolkit to analyze the topological properties of filtrations generated from the aforementioned models. We conclude with an overview of our advancements in §7.
Source code and related data. The source code will be available on this paper’s homepage [17].
2 Preliminaries
This section reviews key concepts in quiver representations and persistent homology and fixes conventions. Details and proofs can be found in [5], [3] and [29]. We adhere to a fixed base field throughout this paper.
2.1 Representations of Quivers with Relations
Definition 2.1.
- •
A quiver is a directed multigraph consisting of a vertex set , an arrow set and two maps assigning the start and target for each arrow in . This quiver is called finite if both and are finite sets.
- •
A vertex is referred to as a source if it has no arrows pointing toward it, and a sink if it has no arrows originating from it.
- •
A path from vertex to vertex is a finite sequence of concatenable arrows in , written as , where , for , and . Following the function composition convention, the arrows are ordered from right to left. If the starting vertex and the target vertex are clear from the context, they are omitted, and the path is written as . The maps and can be extended to the set of paths, by defining and .
- •
A path’s length is the number of arrows it contains.
- •
Paths and are parallel, denoted by , if they share the same starting and target vertices.
- •
Every vertex is associated with a unique length-zero path, called the trivial path, denoted as . Each vertex and its trivial path can be regarded as equivalent.
- •
For a non-negative integer , define as the set of paths in of length , and .
- •
We can construct a unital associative -algebra with the underlying vector space being the free -module generated by , and the product is given by the concatenation of paths. This associative algebra is called the path algebra of . Also, from the concatenation of paths, a quiver can be naturally regarded as a category.
- •
A quiver is said to be acyclic if it does not contain any cycles, i.e., a non-trivial path that starts and ends at the same vertex.
Example 2.2.
A quiver is of type if its underlying graph is a linear graph with vertices. The orientation of arrows in a type quiver is specified by a string consisting of letters and , where stands for a forward arrow and a backward arrow (see Figure 2). We represent a type quiver with its orientation as the pair . When the orientation is implicit, we may simply write . An equi-oriented type quiver has all of its arrows pointing in the same direction, denoted as .
Definition 2.3.
Let be a quiver. A relation in with coefficients in is a linear combination of parallel paths, written as
where , , and for . For a set of relations, the pair is called a quiver with relations.
Given a set of relations , one can generate a two-sided ideal in the path algebra , and also define the quotient algebra .
Remark 2.4.
The relation is regarded as the trivial relation, and it holds that . A relation of the form with is referred to as a zero relation. A relation of the form is called a commutativity relation.
Definition 2.5.
Let be a quiver. Its full commutativity relations is a set defined as:
A quiver with these relations is called a fully commutative quiver.
Remark 2.6.
Throughout this paper, we will focus exclusively on quivers with relations that are finite, acyclic, and fully commutative unless otherwise specified.
Definition 2.7.
Let be a quiver.
- •
A subquiver of is a quiver such that , , and are the restrictions of and to respectively.
- •
A subquiver is full if every arrow with its start and target in also belongs to .
- •
A full subquiver of is said to be convex if, for any path in that starts and ends in , all intermediate vertices also belong to .
- •
The convex hull of a set , denoted by , is the full subquiver of whose vertices are all the vertices that lie on a path starting and ending with vertices in .
- •
A subquiver is said to be connected if its underlying graph is connected.
The notions of convexity and convex hull can be naturally extended to quivers with relations.
Definition 2.8.
Let be a quiver with relations and be a subquiver of . The set of induced relations on consists of elements such that all paths in are in . We say is convex if for any non-zero path in with its start and target in , all vertices of the path are also in . The convex hull of a set is then the full subquiver of whose vertices are all the vertices that lie on a non-zero path in starting and ending with vertices in .
Definition 2.9.
Let be a quiver with relations. An induced subquiver with relations is called an interval subquiver (with relations), or simply an interval of , if is a connected convex subquiver, and does not contain any zero relations. The set of all interval subquivers of is denoted as . It forms a partially ordered set by containment of the corresponding vertex sets. Specifically, for two interval subquivers and , if and only if .
Remark 2.10.
This paper’s definition of an interval differs slightly from [3, Definition 2.4]. The cited paper defines an interval for quivers without relations, requiring only two conditions: convexity and connectedness. However, our research engages with quivers with relations, and we accommodate quivers with zero relations for generality. As a result, a new condition “does not contain any zero relations" is added.
Example 2.11.
Consider a quiver with relations and . Then, the set of all interval subquivers of is . Notice that does not qualify as an interval subquiver as it encompasses the zero relation .
Next, we introduce representations of quivers and quivers with relations. The category of finite-dimensional -vector spaces is denoted as . For brevity, is used since we are working over a fixed field.
Definition 2.12.
Let be a quiver and be a quiver with relations.
- •
A (finite-dimensional) representation of is a functor from to . We denote the associated vector spaces as for , and the morphisms as for .
- •
A representation of is a representation of the underlying quiver satisfying the additional condition that the evaluation of on each relation vanishes.
- •
The category of representations of is denoted as .
- •
The vector is called the dimension vector of
- •
If the associated -algebra is a representation-finite algebra, is said to have a finite type.
Definition 2.13.
Let be a quiver with relations, be a representation in , and be an induced subquiver with relations. A representation in can be derived from by restricting to the vertices and arrows of the induced subquiver. This restricted representation is denoted as .
Definition 2.14.
Consider a quiver with relations and as a representation of . The support of , denoted as , is the full subquiver of consisting of vertices for which .
Definition 2.15.
Given a quiver with relations and an interval subquiver , the associated interval representation is defined as follows:
Example 2.16.
Consider the following fully commutative quiver and interval subquiver:
| . |
The associated interval representation is Notice that a bijective correspondence exists between an interval representation and its dimension vector. Therefore, we can represent by its dimension vector .
Definition 2.17.
Let be a quiver with relations. A representation is said to be interval-decomposable if it is isomorphic to a direct sum of interval representations of .
When we are working with a finite acyclic quiver with a set of relations , both the path algebra and its quotient algebra have finite dimensions. As a result, the representation category of satisfies the unique decomposition theorem, also known as the Krull-Schmidt theorem.
Theorem 2.18.
Let be a complete set of representatives of the isomorphism classes of indecomposable representations of a quiver with relations . For each representation , there exists a unique function such that
| (2.1) |
The function is referred to as the multiplicity function of , and the value is called the multiplicity of the indecomposable in . This isomorphism is referred to as the indecomposable decomposition of . Moreover, is uniquely determined by up to isomorphism.
2.2 Commutative Grids and Commutative Ladders
Definition 2.19.
Let and be two quivers. Their Cartesian product is a quiver defined as follows:
- •
The vertex set is the Cartesian product .
- •
There exists an arrow from to if and only if either:
- –
and there exists an arrow from to , denoted by ;
- –
and there exists an arrow from to , denoted by .
- –
The tensor product of and , denoted by , is the quiver with the following relations:
for all and (see Figure 3).
Definition 2.20.
A two-dimensional fully commutative grid with orientation is the tensor product of quivers and , written as (See Figure 4). We often refer to simply as a commutative grid or a grid. If both and are equi-oriented, we have the equi-oriented commutative grid, represented as .
The vertices of can be depicted as a rectangular lattice with columns and rows, with edges connecting vertically or horizontally adjacent vertices. For equi-oriented grids, we will draw horizontal arrows pointing rightwards and vertical ones upwards without loss of generality.
Intervals in exhibit staircase shapes, and they can be parameterized as discussed above [1, Proposition 21]. To simplify the notation, we use to represent .
| (2.2) |
Definition 2.21.
A commutative ladder is a commutative grid with orientation . We can use just to represent its orientation since the value of is inconsequential in this context. An equi-oriented commutative ladder of length is denoted as .
Commutative ladders are of significant interest in the transition from one-parameter to two-parameter persistence modules. Under specific conditions, these ladders exhibit representation-finiteness, unlocking the possibility of computing all multiplicity functions. On the other hand, they remain representation-infinite in general situations, driving the need for new approaches. A criterion for representation-finiteness of commutative ladders is given in [14].
Theorem 2.22.
For an arbitrary orientation , the commutative ladder is
- 1.
representation-finite if ;
- 2.
representation-infinite if .
2.3 Persistent Homology
Definition 2.23.
A persistence module refers to a representation of a quiver with relations . This corresponds to a module over the quotient algebra . Several common families have established nomenclature as below.
- •
A one-parameter persistence module is a representation of a quiver .
- •
A zigzag persistence module designates a one-parameter persistence module, highlighting that the underlying quiver may not be equi-oriented.
- •
A two-parameter persistence module is a representation of a commutative grid .
- •
A persistent homology is a persistence module obtained by taking a homology functor on a filtration of topological spaces.
In this paper, the terms “persistence module” and “representation” are used interchangeably. Consider a quiver represented as and a persistence module of . According to Gabriel’s theorem, is interval-decomposable [15]. Then by Theorem 2.18, is isomorphic to .
Definition 2.24.
Given a one-parameter persistence module and its associated multiplicity function , the persistence diagram of , denoted as , visualizes as a multiset of points in the two-dimensional integer lattice . Here, the multiplicity for with is .
Remark 2.25.
For any point in the persistence diagram, we adopt the following conventions:
- •
The birth coordinate is inclusive, which means that the generator emerges at value .
- •
The death coordinate is exclusive, indicating that value is the earliest point at which the generator vanishes.
3 Refining Interval Approximations
In the study of multiparameter persistence modules, we aim to obtain the indecomposable decomposition of a given representation , equivalent to the computation of the multiplicity function . However, direct computation is extremely challenging, especially when is not interval-decomposable. To overcome this difficulty, we turn to the interval approximation method, first proposed in [3], which approximates the rank invariant of a representation via those of interval representations.
A crucial quantity in defining the interval approximation is compression. It provides a lossy yet more manageable way to define invariants on . This section presents a new mechanism for handling various types of compressions in a more general and flexible way. We then stratify intervals within a general two-dimensional commutative grid, proposing the partial interval approximation to address the issue of an exponentially growing number of intervals. Moreover, we show how the interactive visualization of a 2-D persistence module [24] can be reformulated using the interval approximation. Throughout this section, we consider a finite fully commutative acyclic quiver .
3.1 Courses and Tours
Definition 3.1 (Course).
A course on is a pair with being a connected quiver and acting as a labeling map, such that for any arrow , there exists a path from to in . The set of all courses on is denoted by .
Example 3.2.
Consider the fully commutative quiver and a connected quiver . We define two labeling maps and as shown in Figure 5.
Definition 3.3 (Essential Vertex).
Let be an interval subquiver of . A vertex is called essential if is either a source or a sink in (see Figure 6). The set of all essential vertices of is denoted by .
Remark 3.4.
We note that the essential vertices defined here are called the “source-sink-essential vertices” in [3, Definition 4.1], and they are the minimal information required to recover an interval subquiver. Specifically, an interval subquiver is the convex hull of .
The concept of essential vertices provides a criterion to determine the containment relations between two intervals in . The following proposition justifies their name as being “essential”.
Proposition 3.5.
Let be intervals of . If is contained in , then .
Proof.
This statement can be proved similarly as in [3, Lemma 4.3]. ∎
Within an interval , courses that visit all are of particular importance.
Definition 3.6 (Essential Course).
Let be a course on . For an interval , the course is said to be:
- •
a course in if the image of is contained in .
- •
an essential course in , or essential in , if it is a course in and all essential vertices of are contained in the image of , i.e., .
Proposition 3.7.
Consider a course on . If there exists an interval for which serves as an essential course, then is unique.
Proof.
Suppose is an essential course in both and . By definition, we have and , thus and . Then it follows from Proposition 3.5 that . ∎
Remark 3.8.
The converse statement is generally not true, as multiple essential courses can be defined within a fixed interval. Figure 11 provides such an example.
Definition 3.9 (Essential Assignment).
An essential assignment is a map that assigns each interval an essential course in . This can be formally expressed as:
Definition 3.10 (Tour).
A tour on a course in is an additive functor that maps a representation to an object in specified as below:
where represents the evaluation of on a path in from to , which is well-defined by the full commutativity of . For a morphism in , a morphism in is given by for each .
Remark 3.11.
Consider a representation . The choice of a quiver and a labeling map can significantly impact the analysis’s feasibility. Using will place the tour defined above in the category , which usually makes the situation more tractable than working directly with a representation in . This process, however, can lead to information loss of . To compensate for it, we employ a set of tours to probe , with each tour offering partial information about from different perspectives. Collectively, they provide a more complete understanding of , where the amount of information loss varies and is based on the particular choice of courses and the method by which the tours are combined. For instance, in the context of , an essential assignment (referred to as a quiver morphism in the cited paper below) that exhibits several appealing properties is demonstrated in [2, Section 5.1], highlighting the value of this approach.
We introduce the Hasse quiver as an analog to the Hasse diagram in quivers, facilitating the characterization of the transitive reduction of paths.
Definition 3.12 (Hasse Quiver).
Let be an acyclic quiver and let be a subset of its vertices. The Hasse quiver is a quiver derived from and as follows:
- •
The vertex set of is .
- •
For each pair of distinct vertices , an arrow is drawn from to if there is a path from to in , and there is no third vertex in any path from to in .
Example 3.13.
We illustrate the concept of the Hasse quiver by capturing the idea of a “compressed category” within the context of , as described in [3]. Given an interval subquiver , the selection of different subsets can lead to a variety of Hasse quivers. Consider the following three possibilities:
- 1.
;
- 2.
;
- 3.
, where is an operation that identifies “corner-complete” vertices. This subset of includes all vertices present in both a row and a column with essential vertices. Note that all essential vertices are corner-complete.
As an example, consider and an interval in Figure 7. The Hasse quivers on and are shown in (b) and (c), respectively. Notice that equals , emphasizing that the Hasse quiver is equal to the original quiver when all vertices are considered.
We now show two examples demonstrating the adaptability and versatility of the concept of essential assignment. These examples highlight how it serves as a unified framework for incorporating related definitions from existing literature.
Example 3.14.
The three types of compressions (ss, cc, and tot) introduced in [3] can be expressed as different essential assignments. Consider and the following maps defined on its set of intervals:
With these constructions, we can verify that for as defined in the reference.
Example 3.15.
We demonstrate how the concept of boundary cap from [11, Definition 19] fits within our framework. Consider the interval depicted in Figure 8. Its boundary cap, denoted by , can be regarded as a type quiver. It is constructed from all vertices in and intermediate vertices on the boundary of to ensure connectivity. Therefore, can be expressed as an essential course in . As a result, we can reproduce it using an essential assignment that follows the same pattern.
3.2 -compressed Multiplicities and Interval Approximations
We are ready to introduce the concept of -compressed multiplicity. This quantity captures the multiplicity of an interval representation within a representation relative to the designated tour .
Definition 3.16 (-compressed Multiplicity).
Let be a representation of and be an essential assignment. For an interval , we define the -compressed multiplicity of on the interval as follows:
where is the multiplicity function as in (2.1).
Remark 3.17.
Consider an with . Using the definition of and noting that is a connected quiver, we can easily verify that is an indecomposable representation. In particular, if is a type quiver, then all indecomposable representations of it are interval representations. The longest one among them can be represented as:
with , which we denote as or .
Example 3.18.
Proposition 3.19.
Let be an essential assignment. For any satisfying , the following holds:
Proof.
This equality is straightforward, as when we compute the value on the left-hand side, any vertices not included within can be ignored. ∎
Proposition 3.20.
Let be an essential assignment and be an interval in . For any , we have:
Proof.
Starting from the definition of the -compressed multiplicity, we obtain
Using the additivity of the functor with respect to direct sums and the additivity of the multiplicity function with respect to direct sums of representations in the subscript, the expression expands to:
substituting back the definition of -compressed multiplicity completes the proof. ∎
Proposition 3.21.
Let be an essential assignment and . The -compressed multiplicity function evaluates as:
Proof.
By definition, .
Case 1: If , then Proposition 3.19 asserts that .
Case 2: Otherwise, there exists an essential vertex of but not in , as guaranteed by Proposition 3.5. This implies that . Given that is an essential course in , is visited by . As a result, the associated vector space of in is zero, but it is nonzero in . This leads to the zero multiplicity for in . ∎
The following lemma is intended to serve as a counterpart to [3, Lemma 4.21].
Lemma 3.22.
Let be an essential assignment and . If is an interval-decomposable representation in , then the following equation holds:
Definition 3.23 (Cover and Join).
Consider as a partially ordered set. The cover of an interval , denoted , is the set of intervals satisfying and there is no interval such that . The join of a subset , denoted , is the supremum of provided that it exists.
When , for each , the join operation is well-defined for every subset , as shown in the discussion above [3, Example 3.7]. Here, equals the minimum interval containing the union of intervals in . For simplicity, we use the convention for .
Theorem 3.24.
Consider an equi-oriented commutative grid . Let be an essential assignment and . If is an interval-decomposable representation of , then
Proof.
This follows directly from the Möbius inversion theorem, as detailed in [3, Section 5]. ∎
The definition of interval approximation below is motivated by the Möbius inversion of the formula above, where we define it for more general quivers and remove the interval-decomposable condition.
Definition 3.25 (Interval Approximation).
Let be a representation of and be an essential assignment on . The interval approximation of by via -compressed multiplicity functions is an integer-valued function that satisfies
| (3.1) |
for any . When the choice of is clear from the context, we refer to as the interval approximation.
Remark 3.26.
A function can always be constructed as follows. First, we define for each maximal in . Then, we iteratively trace down along the cover relations and set . However, if the join operation is well-defined for any subset for all , we can apply the Möbius transform to (3.1) and obtain
To conclude this subsection, we prove a theorem establishing that the interval approximation accurately recovers the rank function, thereby justifying its name as an approximation.
Lemma 3.27.
Let be an essential assignment and be a non-zero path in starting from vertex and ending at vertex . Let denote the convex hull of vertices . If is a representation of , then the following equation holds:
Proof.
For any , the rank of the morphism satisfies
Since the convex hull is the unique minimum interval subquiver that contains each vertex of , we can reformulate the left-hand side as
where the last equality is obtained by Definition 3.25. ∎
Lemma 3.28.
Assume the same conditions as in the previous lemma. Then the following equality holds:
Proof.
Consider the following restrictions:
- •
Restrict to .
- •
Use the symbol when we view as an interval subquiver of .
- •
Restrict to , which equals
- •
Restrict to .
The -compressed multiplicity on the left-hand side can be reformulated as follows:
| (3.2) |
We will show that the right-hand side above is equal to . It is easy to verify that is an indecomposable projective-injective representation. Therefore, the multiplicity of in can be expressed as below.
As a result, can be written as a direct sum , with not having as a direct summand. By applying the additivity (Proposition 3.20) to this decomposition, we have
Next we show the reverse inequality . We break down the proof into the following steps.
- 1.
First we observe that is the only source of . If were not a source, there would be a vertex with an arrow from to . By ’s defining property, there would be a path from to passing through , leading to a cycle containing , contradicting ’s acyclicity. The definition of the convex hull immediately implies its uniqueness. Similarly, is the only sink of .
- 2.
Consider the essential course , where is a connected quiver and is the labeling map. Since this is an essential course in , and are essential vertices of , there exists vertices such that and . As is connected, we can find a subquiver of of type , which starts from and ends at . This subquiver induces a type course in , where denote the restriction of to . Observe that vertices in together with arrows between each adjacent pair can be expressed as
(3.3) where the directions of the first and last arrows are fixed, as shown in the first step above. Since is a subquiver of , the following inequality holds:
Therefore, it suffices to show that . By definition, is a summand of , thereby we have the following section and retraction, where :
We can explicitly represent the sections and retractions between vector spaces using the labels in (3.3) as the two commutative diagrams below, where the orientation of horizontal arrows is identical to those in (3.3):
Since each morphism in the lower row is bijective, we can reorient all arrows to be forward-going. With this adjustment, we formulate the following commutative diagram by selecting sections from to together with retraction , and identity maps are also indexed for clarity:
Let denote the composition of all identity maps in the lower row. If we can prove , then it would follow that .
- 3.
Now we prove the aforementioned equation in the second step. Let , , and , , for easier indexing. By the definition of the convex hull , each vertex in it lies on a path from to . Hence the following commutative diagram exists for :
We follow the procedures below to reduce the map for .
- •
If the arrow from to goes forward, then by the commutative diagram
we have
- •
If the arrow from to goes backward, then by the commutative diagram
we have
Applying this reduction iteratively, we obtain
This concludes the proof.
- •
∎
Theorem 3.29.
Let be an essential assignment on , be a representation in , and be a path in . Then the following equation holds:
Proof.
If is a zero path, then both sides are equal to zero. For non-zero paths, the result follows directly from the two preceding lemmas. ∎
3.3 Approximation Series in 2D Grids
In this subsection, we focus on the computation of interval approximations in a two-dimensional commutative grid . Even though the number of interval representations in is finite, it increases exponentially with the size of . To address this problem, we define a series of partial approximations, each one necessitating more computational demands but also providing incrementally details. Additionally, we demonstrate that the interactive visualization of a 2D persistence module by the barcodes of 1D affine slices in [24] can be reformulated using an approximation in the series developed.
Theorem 3.30.
We can stratify intervals by enumerating the number of essential vertices since an interval is fully determined by its essential vertices. As a result, the number of essential vertices serves as an indicator of the interval’s complexity.
Definition 3.31 (-essential Interval).
Given a positive integer , the set of -essential intervals of is a subset of that includes all intervals with exactly essential vertices, expressed as:
Furthermore, we use to represent the disjoint union of all -essential intervals for :
Example 3.32.
The description and cardinality of for are detailed as follows:
| , | , |
| , | , |
| , | . |
Note that vertices are not considered as line segments or rectangles in . The three terms in the expression for represent the number of horizontal line segments, vertical line segments, and rectangles, respectively. For , we can count the ways of cutting a smaller rectangle from a larger non-degenerate rectangle of size subject to the condition that either the top-right or the bottom-left vertices of both rectangles coincide. This enumeration is formulated by the sum , which then reduces to the expression above.
Recall the definitions of cover and join from Definition 3.23. For a subset of , we define as the cover of induced by the partial order on for each . Likewise, given an interval and a subset , we use to denote the join of under the induced partial order, assuming it exists. We can now generalize the concept of interval approximation from Definition 3.25 by broadening the criteria for intervals to be considered.
Definition 3.33 (Partial Interval Approximation).
Consider a representation , a set , and an essential assignment defined on . A partial interval approximation of by via -compressed multiplicities is defined as an integer-valued function defined on intervals of that satisfies the following equation for any :
Remark 3.34.
In parallel to Remark 3.26, can be built up by firstly setting for each that is a maximal element of , then tracing down along the cover relations in iterative steps by setting . Similarly, if and are well-defined for any and , we can use the Möbius inversion to express the partial interval approximation as:
Remark 3.35.
We refer to the partial interval approximation as the rectangle approximation.
Definition 3.36 (Rank Invariant).
Consider a representation in and a subset of intervals . A partial interval approximation is said to be rank invariant if the rank of over any path in can be expressed as the following weighted sum:
Example 3.37.
Any interval approximation is rank invariant, as shown by Theorem 3.29.
The compressed multiplicity function offers more flexibility compared to the rank function, stemming from the freedom to select and . This flexibility permits the selection of a subset of intervals for approximation, leading to a generalization of the rank invariant property.
Definition 3.38 (-rank Invariant).
Let be a fixed non-negative integer. A partial interval approximation is said to be -rank invariant if the following equation holds for any :
We now establish the equivalence between rank invariance and -rank invariance. Consider a path in and the rectangle interval bounded by vertices and . By invoking Lemma 3.28, we obtain:
Meanwhile, Proposition 3.21 indicates that is equal to . Substituting these two equations back into the defining equation of being -rank invariant completes the statement.
Remark 3.39.
We observe that -rank invariance is equivalent to preserving the dimension vector of the original representation. As discussed above, -rank invariance ensures that the rank of paths is maintained. Furthermore, -rank invariance preserves information about more complex shapes, such as the L-shaped regions depicted in of Example 3.32.
Theorem 3.40.
Let be a representation of . If , then the partial interval approximation is -rank invariant. In particular, the interval approximation is -rank invariant with respect to all non-negative integers .
Proof.
Consider the defining equation . Given that by Proposition 3.21, we can incorporate a multiplier for each summand, and then change the summation range to . This adjusted summation aligns with the definition of being -rank invariant, concluding the proof. ∎
Corollary 3.41.
If , then is rank invariant. As a result, the rectangle approximation as defined in Remark 3.35 is also rank invariant.
Here we show that rectangle approximations of a 2D persistence module are equivalent to 1D affine slices as described in RIVET [24]. We use in to denote the rectangle interval bounded by the two vertices and if there exists a path from to . Consider the slice along the line connecting and in Figure 9, and let denote the type quiver defined by the slice. We denote the interval of connecting and as . The multiplicity of in the compressed representation can be calculated as:
The multiplicity of in the compressed representation is equal to the multiplicity of the interval in the persistence diagram of the slice, thus both the rectangle approximation and RIVET’s persistence diagram are determined by .
Based on these observations, we construct an approximation series on employing the stratification provided by -essential intervals, depicted in Figure 10. The top row displays the order of the interval count for each corresponding set below. The third row lists partial interval approximations, the fourth row shows names for specific invariants, and the bottom row illustrates the change in resolution.
It is worth noting that for any fixed , this approximation series stabilizes because the number of -essential intervals in is finite. The series starts with the dimension vector and ends with the interval approximation. RIVET’s persistence diagram/rectangle approximation is located just to the right of the dimension vector. As the series progresses, the corresponding partial interval approximation provides more information about the morphisms of the representation since more intervals are included, at the cost of higher computational demands.
4 Topological Invariants for Commutative Ladders
In this section, we validate the effectiveness of our theoretical framework by addressing specific challenges associated with commutative ladders. We first devise an algorithm that efficiently computes the indecomposable decomposition of any representation of an equi-oriented finite-type commutative ladder, then extend persistence diagrams to infinite-type cases. While our focus here is primarily on the equi-oriented cases, both approaches can seamlessly extend to an arbitrary orientation .
4.1 Finite-Type Commutative Ladders: Indecomposable Decomposition
Consider a finite-type commutative ladder . Let be a complete set of representatives of the isomorphism classes of indecomposable -modules. Our objective is to compute the persistent homology of a -filtration , represented as . This amounts to determine the multiplicity function for every . While existing theoretical frameworks such as [4, Theorem 3.4] and [14, Section 4] can handle this, they both require the explicit representation of and the determination of a common basis for the hom-sets between multiple vector spaces, which can be computationally intensive.
In contrast, our algorithm circumvents the direct use of and instead utilizes the filtration . This approach transforms the original computation into numerous computations of zigzag persistent homology, a tool where mature and fast algorithms are already available [10]. As a result, we can significantly reduce computational demands and make it more tractable for practical implementations.
Let be a fully commutative quiver and be a finite subset of a complete set of representatives of the isomorphism classes of indecomposables in . We say a representation is if every indecomposable direct summand of is isomorphic to an element in . For any -decomposable representation with , Theorem 2.18 guarantees the following decomposition:
Consider a family of functions on that are compatible with direct sum operations and isomorphism (referred to as the compatibility condition in the subsequent discussion). Applying these functions to the decomposition of yields the following set of equations:
These equations can be summarized into a matrix expression (assuming the column vector convention):
The coefficient matrix has rows and columns, where we can assume 11 1 To solve this linear system, a coefficient matrix of rank is required. If , this system is underdetermined, and we need to add more functions. If , we can remove surplus functions from to equate and . . If its rank is equal to , then there exists a left inverse to it, from which the multiplicity functions can be solved as
Notice that the inverse of the coefficient matrix is independent of the knowledge about . For each new filtration and the associated , we only need to recompute the vector .
Example 4.1.
This example examines the finite-type commutative ladder . Let denote a complete set of representatives of isomorphism classes of , where by [14]. Denoting the vertex set of as , each representation can be formulated as:
Consider the following functions defined on :
- •
for ;
- •
for if there exists a path from to ;
- •
for distinct if there exists a course on such that ;
- •
for distinct if there exists a course on such that ;
- •
for distinct if there exists a course on such that .
All these functions meet the compatibility condition. The linear space spanned by the family of functions of form and on has a dimension of 16. This dimension increases to 26 by including all functions defined by type courses (i.e., functions of the form and ), and further to =29 upon adding three linearly independent functions of the form 22 2 One possible choice is to set as in .. This yields a coefficient matrix that can be used to compute the indecomposable decomposition of any representation of .
Definition 4.2 (Zigzag Course with an Alternating Orientation).
A course is called a zigzag course with an alternating orientation if is a type quiver with orientation . This definition accommodates the general one-parameter cases with any orientation since consecutive arrows pointing in the same direction can be composed together, and if the first arrow points backward, it can be repeated twice. For brevity, we use the term “alternating zigzag course” to refer to such a course.
Example 4.3.
Consider a course with orientation type . To transform it into an alternating zigzag course starting with a forward arrow, we build a type course , with the labeling map below:
This modified course effectively prepends the map to the original course, and it satisfies the definition of an alternating zigzag course. It can be easily verified that all computations using it in the -compressed multiplicity yield the same results as those obtained from the original course based on the definition.
Remark 4.4.
Recall that and assign the start and target of a path. For , a sequence of paths determines an alternating zigzag course of type if it meets one of the following conditions:
- •
If , then the path always determines an alternating zigzag course, which is given by and , .
- •
If , then it determines an alternating zigzag course if and only if the pattern below is satisfied:
where points forwards if is even, and backwards if is odd. This condition can be expressed as:
- –
for odd with ;
- –
for even with .
The alternating zigzag course can be easily read from the graphic pattern above.
- –
Given an alternating zigzag course , recall that denotes the longest interval representation in . We associate this course with the following function on :
| (4.1) |
Notice that it satisfies the compatibility condition. In particular, although the representation appears in the subscript, representation is always of type . Therefore, we do not need to compute the representation in advance, significantly speeding up the computation.
Our current objective is to identify a sufficient number of alternating zigzag courses that can induce linearly independent functions. To achieve this, we need to determine the labeling map
via a sequence of (non-trivial) paths that form an alternating zigzag course for , where is a preset limit. Since is a finite acyclic quiver, the count of alternating zigzag courses (hence labeling maps) is finite for any fixed positive integer . This allows for an exhaustive search for all courses. Appendix A.1 provides an illustrative enumeration algorithm and Appendix A.2 shows a more efficient breadth-first search algorithm.
After gathering all alternating zigzag courses up to length , we associate each course with a function defined by (4.1). Notice that multiple courses can result in the same function, and the generated functions can be linearly dependent (for example, the first path in an alternating zigzag course can be repeated twice, similar to the steps described in Example 4.3). An algorithm of this process is attached in Appendix A.3.
We execute the algorithms on for and successfully find sufficient linearly independent functions to solve their indecomposable decompositions. Specifically, for , choosing serves as an adequate preset limit, and a detailed list of the obtained 76 alternating zigzag courses can be found in [17]. As an illustration, we show five such courses in Figure 11. The vertices in each course are labeled with letters, while those in are labeled with their Cartesian coordinates. Several alternating zigzag courses in this figure do not belong to the three types of compressions defined in [3], demonstrating the capability of our framework to extract deeper insights compared to the existing methods.
| Alternating zigzag course | Type | Labeling map | Graphic diagram |
|---|---|---|---|
4.2 Infinite-Type Commutative Ladders: Connected Persistence Diagram
Our discussion in the previous subsection relies on the -decomposability condition with a predetermined finite set of isomorphism classes , where the finiteness requirement cannot be generalized to representations of a general . To broaden our framework’s applicability, we introduce a novel invariant crafted specifically for general commutative ladders by leveraging their unique two-row structure. This invariant captures the topological information in the two rows extractable via one-parameter persistence in the horizontal direction and measures the vertical persistence of generators along these two rows, using a selected essential assignment.
By setting the parameters in (2.2) to and categorizing intervals into subsets based on their support, we can obtain an indexing for intervals in as below:
| (4.2) | ||||
where contains all intervals entirely supported in the lower row, contains all intervals entirely supported in the upper row, and contains intervals with support that bridges the two rows. An element of form in or has type , and a typical element in is shown below:
where vertices and can share a column, as can and .
Definition 4.5.
Consider an essential assignment on and a persistence module of as:
| (4.3) |
We define an auxiliary function constructed from the interval approximation , as per the steps delineated below.
- •
For intervals in , with fixed indices and , we define
- •
For intervals in , given and , we define
- •
For intervals in , we define
Notice that the original interval approximation can be retrieved from the associated . The following proposition explains the summations involved in the definition. It shows that encodes all the information available in the corresponding multiplicity functions when we only look at the upper or lower row.
Proposition 4.6.
Let be an essential assignment and be a persistence module of . Referring to (4.3), we denote the lower and upper rows of as
respectively. Both and are one-parameter persistence modules over quiver . Define as the function mapping intervals in to representations of :
Then, the following equations hold:
In other words, for any interval , its multiplicity in aligns with its multiplicity in the corresponding one-parameter persistence module, irrespective of the choice of .
Proof.
We here only show the statement for . By padding the persistence module with zero vector spaces on both sides (which ensures that and for or ), rank calculations involving indices outside of the range become well-defined. Consider an interval , the multiplicity of its associated interval module is
By Theorem 3.29, this equation rearranges to:
We define an alternating sum function on the set of intervals :
It is easy to verify the following relations:
The original equation can be further reduced to:
∎
To visualize , we first adopt an approach that retains a clear relationship to standard persistence diagrams by plotting within two complementary isosceles right triangles that together form a square. We introduce the following points and line segments in for upcoming discussions:
- •
, the lower triangular region in the first quadrant;
- •
, the upper triangular region in the first quadrant;
- •
, the set of line segments connecting points from and with slope33 3 This condition on the slope of the line segment results from the index condition of intervals in specified in (4.2). within the range .
Definition 4.7 (Connected Persistence Diagram).
Let be an essential assignment and be a persistence module of . A connected persistence diagram of , denoted as , visualizes the interval approximation via in the two-dimensional integer lattice as a multiset comprising both points and line segments, where the multiplicity of an element can be negative. Represented as a function, elements with a non-trivial multiplicity are given by:
Remark 4.8.
In a connected persistence diagram, multiplicities on and measure the horizontal persistence, and multiplicities on can measure the vertical persistence, which is crucial for revealing information that is not accessible via only one-parameter persistent homology on the two rows. Notice that the two endpoints of a line segment in often coincide with points from both and . However, as illustrated in Figure 12, this overlap is not requisite.
Remark 4.9.
We choose the source-sink essential assignment for our subsequent computations since its simplicity makes it an ideal starting point. We note that other essential assignments could offer more refined or specific insights. A visualization of on representatives of intervals classified by the number of essential vertices is provided in Figure 13.
Example 4.10.
To highlight the effectiveness of connected persistence diagrams, we present two configurations with topological structures that are distinguishable by connected persistence diagrams but not by standard persistence diagrams at any homology dimension. Figure 14 depicts each configuration as a filtration of Čech complexes in the horizontal direction. For clarity, we omit the associated disks and display all simplicial complexes at four critical radii. We also directly use the radius as our parameter instead of indexing them with natural numbers. The symbol denotes a value infinitesimally less than for .
Let the two representations be and , and the connected persistence diagrams be and . In both cases, the only interval in that might yield a non-zero value under the map of or is . It is easy to verify that . Applying the definition of connected persistence diagram yields
The last three terms all vanish in both cases, because either or . Continuing with the computation, we find that . This yields a value of when and when .
Another visualization method to consider is the layered presentation of the connected persistence diagram. This approach overlays the two standard persistence diagrams, and line segments are also drawn in the upper triangular region. Although superimposed generators become less discernible, this method offers a clearer insight into how specific generators persist in the vertical direction in certain contexts. We further illustrate this method in Section 6.2.1.
Remark 4.11.
The extended diagram presented in [12] also utilizes two triangular regions. Although visually similar, this structure differs from the connected persistence diagram, and they are not directly related.
5 Models for Commutative Ladder Filtrations of Simplicial Complexes
In this part, we introduce models to construct commutative ladder filtrations at the simplicial complex level, enhancing the applicability of the topological invariants discussed in the prior section.
5.1 A General Model
A filtered simplicial complex is a pair , where is a simplicial complex and is a filter satisfying:
Every number can be associated with a simplicial complex through the preimage . For a strictly increasing sequence in , this yields a sequence of simplicial complexes:
which forms a filtration of sublevel sets.
We now consider a simplicial complex equipped with two filters and , subject to the condition for any . Given a sequence , the pair with yields a sequence as above by defining . They play the role of the lower and upper rows in a -filtration, respectively. The condition ensures the vertical inclusions and the commutativity can also be verified. Finally, the -filtration specified by the triplet can be formulated as
| (5.1) |
5.2 Thinning Models for Point Cloud Data
Let be a point cloud and be a subset of . Let denote the Čech complex constructed on the point cloud with ball radius . For a sequence in , we have the following filtration:
| (5.2) |
where the definition of the Čech complex guarantees the commutativity. To incorporate this construction into the general model introduced above, we set the simplicial complex to be , and define the induced filter for as:
Given that each simplex can be expressed in the form with each , the filter on can be defined as:
The filtration (5.2) can then be retrieved from the triplet following the steps in Section 5.1.
Remark 5.1.
Thinning in topological data analysis, introduced in [18], can incorporate a variety of patterns, such as removing points forming certain shapes or employing a density function. An example can be found in Section 6.2.2. Besides what is described here, there exist other methods for creating a filtration from a point cloud , including non-constant point removal or removing higher-dimensional simplices. The multi-cover method described in [28] can also generate a -filtration consistent with our general model.
5.3 Two Models from Random Simplicial Complexes
5.3.1 Clique Complex Model
Our first random model employs the Erdős-Rényi random graph process for generating commutative ladders. Consider the complete graph with vertices, denoted by , where is the set of vertices and is the set of edges. We associate each edge with two independent random variables and , both follow the standard uniform distribution . Given , we define the following two increasing stochastic processes of subgraphs of :
The stochastic process is called the Erdős-Rényi random graph process [13]. Recall that the clique complex of a graph is the abstract simplicial complex that includes all cliques (i.e. complete subgraphs) of . The two stochastic processes defined above induce two increasing stochastic processes of simplicial complexes and . Notice that the condition holds for any , as ensured by the multiplication in ’s definition. By selecting values and setting , we obtain a random -filtration.
To fit it into (5.1) in the general model, we set to be . For , each filter on is defined as below for :
In this formulation, the subscript represents the edge incident to vertices and . The terms and are realizations of and , respectively.
5.3.2 -Linial-Meshulam Model
We introduce another model adapted from the -Linial-Meshulam process [19, 25]. This stochastic process can be seen as a generalization of the Erdős-Rényi random graph process. It begins with a skeleton of a simplicial complex and then progressively adds simplices that are one-dimensional higher than the initial skeleton. We outline the components required for this model as follows.
- •
A vertex set .
- •
The largest abstract simplicial complex over , denoted as , which has dimension .
- •
A chosen dimension where .
- •
The -skeleton of , denoted as , comprising all simplices in having a dimension no greater than .
- •
The set of all -simplices in , represented as .
- •
Each is associated with two independent random variables and that follow the standard uniform distribution .
- •
Two increasing stochastic processes of simplicial complexes:
For both , we have at the start of each filtration almost surely and at the end. Analogous to the previous model, selecting values in and setting yields a random -filtration. A realization of this random -filtration can be established using the triplet as outlined in the general model similarly.
6 Experiments and Analysis
In this section, we discuss computational results about the newly introduced invariants. We begin by analyzing the occurrence of non-intervals in the three different models outlined in the previous section, then show the findings by applying our tools to material structures.
6.1 Non-intervals in Three Different Models
This subsection explores the under-investigated realm of non-interval representations within multiparameter persistence. We use the toolkit in Section 4 to analyze the models in Section 5.2 and 5.3. We will explore persistence modules of both finite-type and infinite-type commutative ladders.
Finite-type Commutative Ladders
Recall from Theorem 2.22 that the representation type of is finite when . We will focus on because any representation of or is interval-decomposable, and the non-interval representations of can be embedded into .
Let be a complete set of representatives of the isomorphism classes of indecomposables in . The Auslander-Reiten quiver 44 4 The Auslander-Reiten quiver of consists of elements in as vertices and irreducible morphisms among them as arrows. We use it to represent elements in here. See [5, Chapter 4] for details. reveals that there are 21 non-intervals and 55 intervals in [14, Fig. 17]. Non-intervals and some intervals are indexed as shown in Figure 15 for easier reference in subsequent discussions, where each class is represented by its dimension vector.
Remark 6.1.
There are two non-interval representatives of isomorphism classes in , represented by dimension vectors and . They can be embedded into either and or and in , as shown in Figure 15.
Infinite-type Commutative Ladders
Unlike the scenario in the finite-type cases, our understanding of non-intervals in infinite-type cases is limited. Despite this, the connected persistence diagrams still provide some clues about them. The property below establishes a negative multiplicity as an indicator of the presence of non-interval summands.
Proposition 6.2.
Let be a representation of . If there exists an essential assignment and an interval of such that , then has an indecomposable non-interval direct summand.
6.1.1 On Point Cloud Model and Clique Complex Model
We demonstrate a comparative analysis of the results from the Point Cloud Model in Section 5.2 and the Clique Complex Model in Section 5.3.1. Throughout this discussion, we maintain the notations established in the individual model’s specification. Implementation details for building filtrations are listed below. Point Cloud Model Clique Complex Model • Construct a set comprising uniformly randomly distributed points confined in the unit cube of or , where the number of points ranges from to . Subsequently, create a point cloud by randomly choosing a non-empty proper subset of . • Construct a complete graph with vertices where . Subsequently, generate samples of the random variables and for . • Set the homology dimension as if . Otherwise, assign as either or . Apply one-parameter persistent homology functor on and to get their critical filtration values. Collect these values and denote their disjoint union with duplicates removed as . Discard this configuration if . • Assign the homology dimension to be or . Apply one-parameter persistent homology functor on and to get their critical filtration values. Collect these values and denote their disjoint union with duplicates removed as . Discard this configuration if . • For the finite-type cases, choose four radii randomly from . For the infinite-type cases, select an integer such that , and build a -filtration by choosing radii randomly. • As detailed in the corresponding entry in the left column.
We begin by examining the interval-decomposability of non-trivial representations. For a representation of , we compute its indecomposable decomposition to identify the presence of any non-interval components. This allows us to determine the proportion of the number of representations that are not interval-decomposable compared to the total number of non-trivial representations. For a general representation of , we turn to its connected persistence diagram and look for the presence of negative multiplicities, providing a lower-bound estimate of the aforementioned proportion. Table 6 presents the proportions obtained from various settings, using either (for indecomposable decomposition) or cPD (for connected persistence diagram) as specified above.
| Point Cloud Model: | Point Cloud Model: | Clique Complex Model | ||||
|---|---|---|---|---|---|---|
| cPD | cPD | cPD | ||||
| 0.034% | 3.38% | 0.097% | 8.83% | 1.727% | 34.74% | |
| N/A | N/A | 0.042% | 1.25% | 0.001% | 0.037% | |
Upon comparing the data from both models in homology dimension one using , it is evident that the Point Cloud Model exhibits a significantly lower proportion of non-interval-decomposable representations compared to the Clique Complex Model. This relatively infrequent occurrence of non-intervals in the Point Cloud Model can be primarily attributed to the geometry of Čech complexes, as illustrated in Figure 16. Additionally, it is worth noting that the proportion of non-interval-decomposable representations in is higher than that in , which is likely due to increased tolerance for perturbations in owing to its additional degree of freedom.
Besides the differences in interval-decomposability, non-intervals also exhibit an uneven distribution across the set of all 21 representatives in different models. Figure 8 illustrates the proportion of each representative’s sum of multiplicities, normalized against the total multiplicity of all the non-intervals.
In the Point Cloud Model, only eight distinct representatives appear among all representatives. Non-intervals predominantly concentrate on , which has one of the lowest 1-norms of the dimension vector among all representatives. In contrast, in the Clique Complex Model, the diversity of non-intervals increases, and they are also less concentrated. All 21 representatives are observed, with no apparent preference towards representatives possessing the lowest 1-norms of dimension vectors.
Next, we look at the effect of ladder length on the detectability of a non-interval component. Figure 10 shows the ratios of the connected persistence diagrams with a negative multiplicity.
With shorter ladder lengths, many details in the original representation are lost, leading to a lower proportion of the occurrence of negative multiplicities. On the other hand, as we increase the length, more topological information is being scrutinized, increasing the likelihood of finding a negative multiplicity. We also see that the Clique Complex Model demonstrates a much higher proportion than the Point Cloud Model, aligning with the observation obtained using indecomposable decomposition.
6.1.2 On -Linial-Meshulam Model
This part analyzes the -Linial-Meshulam Model outlined in Section 5.3.2, with the homology dimension fixed at . Our numerical computations focus on cases where and , with the number of vertices varying between and . The methodology for creating a commutative ladder filtration is similar to the approaches used in the prior two models. Figure 12 summarizes the proportions of each representative’s sum of multiplicities within the indecomposable decomposition obtained using .
Two immediate observations from the computational outcomes are:
- 1.
There exist only interval indecomposable components.
- 2.
All present intervals are anchored at the bottom-left vertex of (refer to Figure 15 for details).
This is not merely a coincidence but an inherent characteristic of the -Linial-Meshulam Model. In the construction process, we always start with a skeleton , this implies that all the -homologous cycles of are present at critical value . Throughout the stochastic process, -simplices from are being incorporated, which only serves to fill -cycles without introducing new ones. It is easy to see that homologous cycles neither merge nor split during this process. Consequently, all representations created from this process are interval-decomposable and, in particular, pivoted at the bottom left vertex. Therefore, the inherent structure of the -Linial-Meshulam Model makes it a systematic approach to generate interval-decomposable representations pivoted at the left bottom vertex.
6.2 On Exploring Material Structures
This subsection uses connected persistence diagrams to uncover the topological properties inherent in amorphous and crystalline structures. Our analysis offers a unique perspective on the topological characteristics of material structures, highlighting features invisible to one-parameter persistent homology.
6.2.1 Silica Thinning Analysis
In this example, we examine the atomic arrangement of amorphous silica using the layered presentation of connected persistence diagrams. Our dataset is a point cloud representing silicon and oxygen atoms in silica [23], as depicted in Figure 20(a). The ring formations in this structure [16] motivate us to apply the constant thinning model from Section 5.2. Specifically, we selectively remove atoms to perturb the structured arrangement and then employ connected persistence diagrams to evaluate the structural changes. We work in homology dimension one throughout this example.
Let be a persistence module of obtained from a thinning model. Recall that a connected persistence diagram directly visualizes (where the superscript for the essential assignment is omitted). Each layered presentation in Figure 20 is plotted following the rules below:
- •
: corresponds to the standard persistence diagram of the post-thinning point cloud, visualized with the middle color bar where color saturation indicates multiplicity values.
- •
: corresponds to the standard persistence diagram of the original silica molecules, visualized with the left color bar.
- •
: corresponds to vertical persistence between generators, visualized with the right color bar, with dashed lines implying negative multiplicity and the color saturation signifying the absolute value of multiplicity.
Although generators near the diagonal line overlap, the main features in the diagrams remain clear.
Case 1: Removing All Silicon Atoms
This scenario assesses topological changes when all silicon atoms are removed while oxygen atoms are left intact. The most prominent features before and after the thinning are labeled as Feature 1 and 2 in Figure 20(b). These two features appear to persist through the thinning process, but that cannot be justified using the standard persistence diagrams alone. This observation is confirmed here by the numerous horizontal green connecting lines between the two features. Therefore, we conclude that the main feature’s birth is delayed, with its basic structure maintained.
Case 2: Thinning Out Oxygen Atoms at a 50% Rate
Half of the oxygen atoms are removed in this case, while silicon atoms are untouched. This amounts to a similar number of atoms being removed compared with Case 1. Contrary to the first case, the primary topological feature shows significant deformation, as can be seen by many more line segments emanating from Feature 1 but not terminating within Feature 3. For those line segments connecting Feature 1 and Feature 3, we observe that the transition distance is much longer, and the angles are steeper, reflecting delayed birth and death, exhibiting a more substantial structural disruption.
This comparative analysis demonstrates that the connected persistence diagrams effectively reveal how different thinning strategies affect the structure.
6.2.2 Face-Centered Cubic and Hexagonal Close Packing
Face-centered cubic (FCC) and hexagonal close packing (HCP) are two packings of equal spheres in three-dimensional space, seen in various materials. These two packings share many common properties and cannot be distinguished using standard persistence diagrams in any dimension. This challenge has sparked numerous research efforts within the community. Hiraoka et al. [18] demonstrated that the persistence diagrams of the two structures after a thinning process are topologically distinct. Meanwhile, Osang et al. [28] proposed -fold covers, which modify the growing-radius ball model typically used to obtain a filtration of simplicial complexes from a given point cloud, to distinguish these two structures.
Figure 21(a) illustrates one layer of a packing. If this layer serves as the base 2D plane, the relative position of any succeeding layer is determined by projecting the center of any sphere from that layer onto this base. We label potential projection points as A, B, and C. If the next layer projects at B, then the third layer could be A or C. Maintaining a periodic packing pattern up until now across all layers, a choice of C for the third layer results in a layer sequence ABCABC, characteristic of FCC packing. Conversely, choosing position A for the third layer yields a layer sequence ABABAB, referred to as HCP. For the subsequent discussion, we assume spheres with a radius of one and a homology dimension of two.
The standard persistence diagrams of FCC and HCP are identical to the upper half triangular region of Figure 22(a) and 22(b) respectively. The generator closer to the diagonal line arises from tetrahedron structures formed by four neighboring atoms, as illustrated in Figure 21(b). Another generator corresponds to the octahedron shown in Figure 21(c). We utilize a patterned thinning model as discussed in Section 5.2 to discern the subtle topological differences between these two packings. Specific to this context, we remove tetrahedral structures randomly to create a -filtration, and we restrict to removing only one such structure to make the explanation more intuitive.
Figure 22 shows the resulting connected persistence diagrams and the homology generators post-thinning obtained via inverse analysis [27]. Notice that the deaths of the two labeled generators in the diagrams are different 1313 13 We record the numerical values of birth and death obtained in the experiment, but their analytical values are also computable. The one for FCC is , and for HCP it is .. We represent each such generator as a brown cage in Figure 22(c) and 22(d), where faces are omitted for visual clarity. The red points within each cage represent the tetrahedron structure removed during the thinning, and we depict how each large cage can contain one original octahedron generator once embedded back into the upper row in the -filtration. This relation is reflected in the connected persistence diagram via the connecting line between the octahedron generator and the cage generator.
7 Concluding Remarks
Refining interval approximations has led to notable advancements and extended developments. The novel framework has broadened the scope of defining invariants on a given interval via accommodating courses of diverse and valid shapes. This discovery reveals that numerous ranks can be defined on a given interval, expanding the previously understood fact. Furthermore, the partial interval approximation offers a practical invariant for general commutative grids.
When applied to the commutative ladders, our framework soon leads to an efficient solution for the indecomposable decomposition of finite-type commutative ladders. The algorithm, explained in Section 4.1, can potentially be instrumental in computing the decomposition of broader cases beyond its current application. This indicates a vast horizon of unexplored courses, hinting at the potential discovery of more intricate non-interval structures. For general commutative ladders, we introduced the connected persistence diagrams. These diagrams allow for the simultaneous visualization of both horizontal and vertical persistence, bridging a crucial gap in the field. Based on the new toolkit and proposed models for the construction of commutative ladder filtrations, we provided insights that stand among the early works analyzing the behavior of non-intervals, and employed connected persistence diagrams to unveil hidden topological information in material structures.
Acknowledgements
The authors would like to thank Prof. Asashiba for valuable discussions and Prof. Ochiai for his helpful feedback. Y.H. was supported by JSPS Grant-in-Aid for Transformative Research Areas (A) (22H05107), Grant-in-Aid for Scientific Research (A) (JP20H00119), and JST MIRAI Program (JPMJMI22G1). K.N. was supported by JSPS Grant-in-Aid for Transformative Research Areas (A) (20H05884) and JSPS KAKENHI JP (19H00834). I.O. was supported by JSPS Grants-in-Aid for Transformative Research Areas (A) (20H05884), JSPS KAKENHI JP (19H00834), and JST PRESTO (JPMJPR1923). C.X. was supported by JST SPRING (JPMJSP2110) and RIKEN Junior Research Associate Program.
Statements and Declarations
The authors declare no competing financial or non-financial interests related to this work.
Appendix A Appendix
A.1 Enumeration Algorithm for Finding Alternating Zigzag Courses
Algorithm 1 is an enumeration algorithm that illustrates the procedures for discovering alternating zigzag courses. This approach involves examining all type courses with an increasing number of paths up to a predetermined threshold value .
A.2 BFS Algorithm for Finding Alternating Zigzag Courses
Algorithm 2 provides a more efficient algorithm to find alternating zigzag courses using a breadth-first search (BFS) approach.
A.3 Algorithm for Extracting Linearly Independent Functions
Algorithm 3 obtains a linearly independent set from the associated functions of a set of alternating zigzag courses. When a function is evaluated on the pre-determined set , it provides a new row for our coefficient matrix. Each entry in this row is the multiplicity of the longest interval in a zigzag persistence module, which can be calculated using existing software packages such as [10] and [26]. This algorithm then iteratively appends rows to the coefficient matrix until the matrix’s rank reaches or all potential candidates have been considered.
References
- [1] Hideto Asashiba, Mickaël Buchet, Emerson. Escolar, Ken Nakashima and Michio Yoshiwaki “On interval decomposability of 2D persistence modules” In Computational Geometry 105/106, 2022, pp. Paper No. 10187933 DOI: 10.1016/j.comgeo.2022.101879
- [2] Hideto Asashiba, Emerson. Escolar, Ken Nakashima and Michio Yoshiwaki “Approximation by interval-decomposables and interval resolutions of persistence modules” In Journal of Pure and Applied Algebra 227.10, 2023, pp. Paper No. 10739720 DOI: 10.1016/j.jpaa.2023.107397
- [3] Hideto Asashiba, Emerson. Escolar, Ken Nakashima and Michio Yoshiwaki “On approximation of 2D persistence modules by interval-decomposables” In Journal of Computational Algebra 6-7, 2023, pp. 100007 DOI: 10.1016/j.jaca.2023.100007
- [4] Hideto Asashiba, Ken Nakashima and Michio Yoshiwaki “Decomposition theory of modules: the case of Kronecker algebra” In Japan Journal of Industrial and Applied Mathematics 34.2, 2017, pp. 489–507 DOI: 10.1007/s13160-017-0247-y
- [5] Ibrahim Assem, Andrzej Skowronski and Daniel Simson “Elements of the Representation Theory of Associative Algebras: Techniques of Representation Theory” Cambridge: Cambridge University Press, 2006 DOI: 10.1017/CBO9780511614309
- [6] Magnus Botnan, Steffen Oppermann and Steve Oudot “Signed Barcodes for Multi-Parameter Persistence via Rank Decompositions” In 38th International Symposium on Computational Geometry (2022) 224 Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 19:1–19:18 DOI: 10.4230/LIPIcs.SoCG.2022.19
- [7] Gunnar Carlsson “Topology and data” In Bulletin of the American Mathematical Society 46.2, 2009, pp. 255–308 DOI: 10.1090/S0273-0979-09-01249-X
- [8] Gunnar Carlsson and Afra Zomorodian “The theory of multidimensional persistence” In Discrete & Computational Geometry 42.1, 2009, pp. 71–93 DOI: 10.1007/s00454-009-9176-0
- [9] Moo. Chung, Peter Bubenik and Peter. Kim “Persistence Diagrams of Cortical Surface Data” In Information Processing in Medical Imaging, 2009 DOI: 10.1007/978-3-642-02498-6_32
- [10] Tamal. Dey and Tao Hou “Fast Computation of Zigzag Persistence” In 30th Annual European Symposium on Algorithms (2022) 244, Leibniz International Proceedings in Informatics (LIPIcs), pp. 43:1–43:15 DOI: 10.4230/LIPIcs.ESA.2022.43
- [11] Tamal. Dey, Woojin Kim and Facundo Mémoli “Computing Generalized Rank Invariant for 2-Parameter Persistence Modules via Zigzag Persistence and Its Applications” In 38th International Symposium on Computational Geometry (2022) 224, pp. 34:1–34:17 DOI: 10.4230/LIPIcs.SoCG.2022.34
- [12] Herbert Edelsbrunner and John Harer “Computational Topology: An Introduction” Providence: American Mathematical Society, 2010 DOI: 10.1090/mbk/069
- [13] P. Erdős and A. Rényi “On the evolution of random graphs” In A Magyar Tudományos Akadémia. Matematikai Kutató Intézetének Közleményei 5, 1960, pp. 17–61 URL: https://static.renyi.hu/~p_erdos/1960-10.pdf
- [14] Emerson. Escolar and Yasuaki Hiraoka “Persistence modules on commutative ladders of finite type” In Discrete & Computational Geometry 55.1, 2016, pp. 100–157 DOI: 10.1007/s00454-015-9746-2
- [15] Peter Gabriel “Unzerlegbare Darstellungen I” In manuscripta mathematica 6.1, 1972, pp. 71–103 DOI: 10.1007/BF01298413
- [16] Yasuaki Hiraoka, Takenobu Nakamura, Akihiko Hirata, Emerson. Escolar, Kaname Matsue and Yasumasa Nishiura “Hierarchical structures of amorphous solids characterized by persistent homology” In Proceedings of the National Academy of Science 113.26, 2016, pp. 7035–7040 DOI: 10.1073/pnas.1520877113
- [17] Yasuaki Hiraoka, Ken Nakashima, Ippei Obayashi and Chenguang Xu “Online Supplement for “Refinement of Interval Approximations for Fully Commutative Quivers”” Accessed 06 October 2023, 2023 URL: https://ladder-invariants.netlify.app
- [18] Yasuaki Hiraoka, Ippei Obayashi and Kazuto Akagi “Persistent Homology and Structural Analysis in Materials Science” In Journal of the Japanese Society for Artificial Intelligence 34.3, 2019, pp. 330–338 DOI: 10.11517/jjsai.34.3_330
- [19] Yasuaki Hiraoka and Tomoyuki Shirai “Minimum spanning acycle and lifetime of persistent homology in the Linial-Meshulam process” In Random Structures & Algorithms 51.2, 2017, pp. 315–340 DOI: 10.1002/rsa.20718
- [20] Sungyeon Hong and Donghun Kim “Medium-range order in amorphous ices revealed by persistent homology” In Journal of Physics: Condensed Matter 31.45 IOP Publishing, 2019, pp. 455403 DOI: 10.1088/1361-648X/ab3820
- [21] Woojin Kim and Facundo Mémoli “Generalized persistence diagrams for persistence modules over posets” In Journal of Applied and Computational Topology 5.4, 2021, pp. 533–581 DOI: 10.1007/s41468-021-00075-1
- [22] Woojin Kim and Samantha Moore “Bigraded Betti numbers and Generalized Persistence Diagrams” In arXiv e-prints, 2021, pp. arXiv:2111.02551 DOI: 10.48550/arXiv.2111.02551
- [23] Sébastien Le and Valeri Petkov “ISAACS – interactive structure analysis of amorphous and crystalline systems” In Journal of Applied Crystallography 43.1, 2010, pp. 181–185 DOI: 10.1107/S0021889809051929
- [24] Michael Lesnick and Matthew Wright “Interactive Visualization of 2-D Persistence Modules” In arXiv e-prints, 2015, pp. arXiv:1512.00180 DOI: 10.48550/arXiv.1512.00180
- [25] Nathan Linial and Roy Meshulam “Homological connectivity of random 2-complexes” In Combinatorica 26.4, 2006, pp. 475–487 DOI: 10.1007/s00493-006-0027-9
- [26] Dmitriy Morozov “Dionysus 2, a library for computing persistent homology” Accessed 06 October 2023, 2023 URL: https://www.mrzv.org/software/dionysus2
- [27] Ippei Obayashi, Takenobu Nakamura and Yasuaki Hiraoka “Persistent Homology Analysis for Materials Research and Persistent Homology Software: HomCloud” In Journal of the Physical Society of Japan 91.9, 2022, pp. 091013 DOI: 10.7566/JPSJ.91.091013
- [28] Georg Osang, Herbert Edelsbrunner and Mohammad Saadatfar “Topological signatures and stability of hexagonal close packing and Barlow stackings” In Soft Matter 17 The Royal Society of Chemistry, 2021, pp. 9107–9115 DOI: 10.1039/D1SM00774B
- [29] Steve. Oudot “Persistence Theory - From Quiver Representations to Data Analysis.” 209, Mathematical surveys and monographs Providence: American Mathematical Society, 2015, pp. 1–218 URL: https://bookstore.ams.org/surv-209
- [30] Asuka Oyama, Yasuaki Hiraoka, Ippei Obayashi, Yusuke Saikawa, Shigeru Furui, Kenshiro Shiraishi, Shinobu Kumagai, Tatsuya Hayashi and Jun’ichi Kotoku “Hepatic tumor classification using texture and topology analysis of non-contrast-enhanced three-dimensional T1-weighted MR images with a radiomics approach” In Scientific Reports 9, 2019, pp. 8764 DOI: 10.1038/s41598-019-45283-z
- [31] Amit Patel “Generalized persistence diagrams” In Journal of Applied and Computational Topology 1.3-4, 2018, pp. 397–419 DOI: 10.1007/s41468-018-0012-6
- [32] X. Xu, J. Cisewski-Kehe, S.. Green and D. Nagai “Finding cosmic voids and filament loops using topological data analysis” In Astronomy and Computing 27, 2019, pp. 34 DOI: 10.1016/j.ascom.2019.02.003