Research seminar Applied and Computational Topology

This seminar will normally take place on Thursdays 10:15–12:00 in room 02.12.020. For questions contact Abhishek Rathod

List of upcoming seminars

Past seminars

The interleaving distance is arguably the most important distance used for comparing persistence modules. In one-parameter persistence, there exist efficient algorithms for computing the interleaving distance. In the multiparameter case, however, one has suspected for a while that the problem is NP-hard, in part due to the lack of a nice decomposition theorem for these modules. In a joint work with Magnus Botnan and Michael Kerber, we show that deciding whether two two-parameter modules are 1-interleaved is NP-complete even if we assume that the modules decompose into summands of a particularly nice form. I will present the proof along with some related hardness results proved by similar methods.

In this talk, we study the persistent homology and related geometric properties of the evolution in time of a discrete-time stochastic process defined on the 2-dimensional regular square lattice. This process corresponds to a cell growth model called the Eden Growth Model (EGM). It can be described as follows: start with the cell square of the 2-dimensional regular square lattice of the plane that contains the origin; then make the cell structure grow by adding one cell at each time uniformly random to the perimeter. We give a characterization of the possible change in the rank of the first homology group of this process (the "number of holes"). Based on this result we have designed and implemented a new algorithm that computes the persistent homology associated to this stochastic process and that also keeps track of geometric features related to the homology. Also, we present obtained results of computational experiments performed with this algorithm, and we establish conjectures about the asymptotic behavior of the homology and other related geometric random variables. The EGM can be seen as a First Passage Percolation model after a proper time-scaling. This is the first time that tools and techniques from stochastic topology and topological data analysis are used to measure the evolution of the topology of the EGM and in general in FPP models.

Persistent homology has proven to be a useful tool to extract information from data sets. Homology, however, is a drastic simplification and in certain situations might remove too much information. This prompts us to study filtered chain complexes. We prove a structure theorem for filtered chain complexes and list all possible indecomposables. We call these indecomposables interval spheres and classify them into three types. Two types correspond respectively to finite and infinite interval modules, while the third type is unseen by homology. The structure theorem states that any filtered chain complex can be written as the unique sum of interval spheres, up to isomorphism and permutation. The proof is based on a hierarchy of full subcategories of the category of filtered chain complexes. Such hierarchy suggests an algorithm for decomposing filtered chain complexes, which also retrieves the usual persistent barcodes.

It is well known that the nerve of a good and open cover U of a space X is homotopy equivalent to X. We prove the analogous statement in the case that U is a finite collection of closed balls in R^d.

In 2003, Linial and Meshulam introduced their model of random simplicial complexes generalizing the Erdős--Rényi random graph model to higher dimensions. In this talk I will discuss the evolution of the homology groups of random simplicial complexes in the Linial--Meshulam model. Along the way, we will see how the story in d ≥ 2 dimensions parallels the story in the random graph setting, but with some unexpected differences.

It is well known that the nerve of a good and open cover U of a space X is homotopy equivalent to X. We prove the analogous statement in the case that U is a finite collection of closed balls in R^d.

Discrete Morse theory has emerged as a powerful tool for a wide range of problems, including the computation of (persistent) homology. In this context, discrete Morse theory is used to reduce the problem of computing a topological invariant of an input simplicial complex to computing the same topological invariant of a (significantly smaller) collapsed cell or chain complex. Consequently, devising methods for obtaining gradient vector fields on complexes to reduce the size of the problem instance has become an emerging theme over the last decade. While computing the optimal gradient vector field on a simplicial complex is NP-hard, several heuristics have been observed to compute near-optimal gradient vector fields on a wide variety of datasets. Understanding the theoretical limits of these strategies is therefore a fundamental problem in computational topology. In this paper, we consider the approximability of maximization and minimization variants of the Morse matching problem. We establish hardness results for Max-Morse matching and Min-Morse matching, settling an open problem posed by Joswig and Pfetsch. In particular, we show that, for a simplicial complex of dimension d ≥ 3 with n simplices, it is NP-hard to approximate Min-Morse matching within a factor of O(n^(1-ε)), for any ε>0. Moreover, we establish hardness of approximation results for Max-Morse matching for simplicial complexes of dimension d ≥ 2, using an L-reduction from Degree 3 Max-Acyclic Subgraph to Max-Morse matching.

A continuation of the talk given on 30/11/18.

A pointwise finite dimensional persistence module assigns to each integer t a finite dimensional vector space V(t) and to each s≤t a map V(s≤t): V(s)→V(t) of vector spaces. It from the classification of finitely generated modules over PIDs that every such V can be written as a direct sum of so-called interval modules k(I) for I some interval, which assign the one-dimensional space to every t∈I and the zero-space to every t∉I. Things get more involved if we replace "integer" by "real number". As proven by W. Crawley-Boevey, the statement still holds true, and the goal of the talk is to get the idea behind his proof.

Given a filtration and a subfiltration of simplicial complexes, the inclusion of the subfiltration into the filtration induces a morphism between their persistent homologies. We discuss how to efficiently compute the barcode of the image of this morphism. While doing so, we establish correspondence results between the images for persistent absolute and relative (co)homology and investigate certain endofunctors on the category of persistence modules as technical tools.

What does it take for a computer to detect the location and orientation of objects? The aim of this thesis is to try to answer this question using neural networks to evaluate point clouds of the objects.

With the advent of every improving information technologies, science and engineering is being being evermore guided by data-driven models and large-scale computations. In this setting, one often is forced to work with models for which the nonlinearities are not derived from first principles and quantitative values for parameters are not known. With this in mind, I will describe an alternative approach formulated in the language of combinatorics and algebraic topology that is inherently multiscale, amenable to mathematically rigorous results based on discrete descriptions of dynamics, computable, and capable of recovering robust dynamic structures. To keep the talk grounded, I will discuss the ideas in the context of modeling of gene regulatory networks.

Let P be a poset, and let vec denote the category of finite dimensional vector spaces over a field k. First I will show that any functor F: P->vec decomposes as a direct sum of indecomposables (with local endomorphism ring). Then I will apply this result in the specific setting of P = R, in order to to provide a new, simple, proof that any functor F: R->Vec decomposes as a direct sum of interval modules (== thin modules). This is joint work with Bill Crawley-Boevey.

We introduce a novel data-driven approach to discover and decode features in the neural code coming from large population neural recordings with minimal assumptions, using cohomological learning. We apply our approach to neural recordings of mice moving freely in a box, where we find a circular feature. We then observe that the decoded value corresponds well to the head direction of the mouse. Thus we capture head direction cells and decode the head direction from the neural population activity without having to process the behaviour of the mouse.

The Euler characteristic is an invariant of a topological space that in a precise sense captures its canonical notion of size, akin to the cardinality of a set. The Euler characteristic is closely related to the homology of a space, as it can be expressed as the alternating sum of its betti numbers, whenever the sum is well-defined. Thus, one says that homology categorifies the Euler characteristic. In his work on the generalisation of cardinality-like invariants, Leinster introduced the magnitude of a metric space, a real number that gives the “effective number of points” of the space. Recently, Leinster and Shulman introduced a homology theory for metric spaces, called magnitude homology, which categorifies the magnitude of a space. In their paper Leinster and Shulman list a series of open questions, two of which are as follows: In this talk I will introduce magnitude and magnitude homology, give an answer to these questions and show that they are intertwined: it is the blurred version of magnitude homology that is related to persistent homology. Leinster and Shulman's paper can be found at

Real data is often given as a point cloud, i.e. a finite set of points with pairwise distances between them. An important problem is to detect the topological shape of data --- for example, to approximate a point cloud by a low-dimensional non-linear subspace such as an embedded graph or a simplicial complex. Classical clustering methods and principal component analysis work well when given data points split into well-separated clusters or lie near linear subspaces of a Euclidean space. Methods from topological data analysis in general metric spaces detect more complicated patterns such as holes and voids that persist for a long time in a 1-parameter family of shapes associated to a cloud. These features can be visualized in the form of a 1-dimensional homologically persistent skeleton, which optimally extends a minimal spanning tree of a point cloud to a graph with cycles. We generalize this skeleton to higher dimensions and prove its optimality among all complexes that preserve topological features of data at any scale.

Topological data analysis (TDA) is a robust field of mathematical data science specializing in complex, noisy, and high-dimensional data. While the elements of modern TDA have existed since the mid-1980’s, applications over the past decade have seen a dramatic increase in systems analysis, engineering, medicine, and the sciences. Two of the primary challenges in this field regard modeling and computation: what do topological features mean, and are they computable? While these questions remain open for some of the simplest structures considered in TDA — homological persistence modules and their indecomposable submodules — in the past two decades researchers have made great progress in algorithms, modeling, and mathematical foundations through diverse connections with other fields of mathematics. This talk will give a first perspective on the idea of matroid theory as a framework for unifying and relating some of these seemingly disparate connections (e.g. with quiver theory, classification, and algebraic stability), and some questions that the fields of matroid theory and TDA may mutually pose to one another. No expertise in homological persistence or general matroid theory will be assumed, though prior exposure to the definition of a matroid and/or persistence module may be helpful.

We consider the approximability of maximization and minimization variants of the Morse matching problem, posed as open problems by Joswig and Pfetsch. We establish hardness results for Max-Morse matching and Min-Morse matching. In particular, we show that, for a simplicial complex with n simplices and dimension d ≥ 3, it is NP-hard to approximate Min-Morse matching within a factor of O(n1−ε), for any ε > 0. Moreover, using an L-reduction from Degree 3 Max-Acyclic Subgraph to Max-Morse matching, we show that it is both NP-hard and UGC-hard to approximate Max-Morse matching for simplicial complexes of dimension d ≥ 2 within certain explicit constant factors.

We start with a concrete version of the interleaving distance of Reeb graphs. Then we connect this approach to the interleaving distance of merge trees. Afterwards we discuss Reeb graphs and merge trees coming from Morse functions in more detail. Then we talk about some ideas for using branch decomposition trees to "approximate" the interleaving distance of merge trees. Afterwards we discuss how this might help with contour trees and some problems with that.

We start with a concrete version of the interleaving distance of Reeb graphs. Then we connect this approach to the interleaving distance of merge trees. Afterwards we discuss Reeb graphs and merge trees coming from Morse functions in more detail. Then we talk about some ideas for using branch decomposition trees to "approximate" the interleaving distance of merge trees. Afterwards we discuss how this might help with contour trees and some problems with that.

I will introduce the concept of filtered covers. I show that the persistent homology of a bounded metric space obtained from the Cech complex is the persistent homology of what I call the filtered nerve of the filtered Cech cover. Given a parameter δ with 0<δ≤1 I introduce the concept of a δ-filtered cover and show that its filtered nerve is interleaved with the Cech complex. Finally, I introduce a particular δ-filtered cover, the divisive cover. The special feature of the divisive cover is that it is constructed top-down. If we disregard fine scale structure and X is a finite subspace of euclidean space, then we obtain a filtered simplicial complex whose size is bounded by an upper bound independent of the cardinality of X. The time needed to compute this filtered simplicial complex depends linearly on the cardinality of X.

We consider Reeb graphs in a general topological setting, and the construction of distances between Reeb graphs that are stable, meaning that similar functions in the supremum norm have similar Reeb graphs. We define a graph edit distance and show that it is universal, providing an upper bound to any other stable distance.

Mapper is probably the most widely used TDA (Topological Data Analysis) tool in the applied sciences and industry. Its main application is in exploratory analysis, where it provides novel data representations that allow for a higher-level understanding of the geometric structures underlying the data. The output of Mapper takes the form of a graph, whose vertices represent homogeneous subpopulations of the data, and whose edges represent certain types of proximity relations. Nevertheless, the inherent instability of the output and the difficult parameter tuning make the method rather difficult to use in practice. This talk will focus on the study of the structural properties of the graphs produced by Mapper, together with their partial stability properties, with a view towards the design of new tools to help users set up the parameters and interpret the outputs.

Some recent results on persistent Betti numbers.

Computational topology has recently seen an important development toward data analysis, giving birth to Topological Data Analysis. Persistent homology appears as a fundamental tool in this field. It is usually computed from filtrations built on top of data sets sampled from some unknown (metric) space, providing "topological signatures" revealing the structure of the underlying space. When the size of the sample is large, direct computation of persistent homology often suffers two issues. First, it becomes prohibitive due to the combinatorial size of the considered filtrations and, second, it appears to be very sensitive to noise and outliers. The goal of the talk is twofold. First, we will briefly introduce the notion of persistent homology and show how it can be used to infer relevant topological information from metric data through stability properties. Second, we will present a method to overcome the above mentioned computational and noise issues by computing persistent diagrams from several subsamples and combining them in order to efficiently infer robust and relevant topological information.

The theory of interleavings lies at the very core of the theoretical foundations of persistent homology. With rising interest in more generalized indexing categories (zigzag, commutative ladders, circle valued maps, etc. ) comes the desire to extend this theory. In the first part of the talk I will survey interleavings in ordinary persistent homology, and, in particular, the celebrated algebraic stability theorem. Then I will report on recent work with Michael Lesnick (Princeton U.) where we extend this to zigzag persistence. Lastly I will show how the notion of interleavings can be generalized to general posets by means of cosheaves. The last part is joint work with Justin Curry (Duke) and Elizabeth Munch (U Albany).

I'll give a survey about my recent research at TUM.

I'll give an elementary introduction to the decomposition of representations of (infinite) linear quivers.

During this talk I will look into two different problems related to data analysis. The first one is the denoising of the data. Usual methods rely either on a precise knowledge of the noise model or several choices of parameter. I will present a new parameter free methods to denoise data assuming some minimal assumption. On a second, I will look into a difficult problem from the user point of view when working with persistence diagram. What does the persistence diagram means in the data? I will present new work on how to build good representatives for one-dimensional homology features and associate them with barcodes.

I will outline a novel computational method for persistent homology of finite metric spaces, which outperforms the previous state of the art by an order of magnitude. After that, I will survey several surprising connections and applications of persistent homology to various areas relevant to our collaborative research center.

Summer 2016

An algorithm is presented that constructs an acyclic partial matching on the cells of a simplicial complex from a vector-valued function defined on the vertices. The resulting acyclic partial matching is used to construct a reduced complex with the same multidimensional persistent homology as the original complex filtered by sublevel sets of the function. Numerical tests on triangle meshes show that the achieved rate of reduction is substantial.

Alexandrov spaces (with curvature bounded below) are a synthetic generalization of Riemannian manifolds with sectional curvature bounded below. In this talk I will discuss the geometric and topological properties of these metric spaces and how they arise in the context of topological data analysis.

2-stratifolds are the simplest 2-complexes which can be good models for topological data analysis. A 2-stratifold X contains a collection X1 of finitely many simple closed curves such that X –X1 is a 2-manifold and a neighborhood of each component C of X1 consists of sheets intersecting in C. In contrast to 2-manifolds there is no known classification of 2-stratifolds in terms of algebraic invariants. In this talk we will describe 2-stratifolds and their graphs and present efficient algorithms that detect whether certain 2-stratifolds have trivial first homology, whether they are simply connected, or whether they have the same homotopy type as a 2-sphere. This is joint work with F. González-Acuña, UNAM, Mexico and W. Heil, Florida State University.

An introduction to Auslander-Reiten Theory. This theory deals with the problem of understanding all indecomposable representations of a quiver with relations (or equivalently the indecomposable modules of certain algebras), as well as the "minimal" morphisms. In general, writing down all indecomposable modules turns out to be an impossible task, but one of the things AR-theory provides us is a way to find new indecomposable modules from old ones. In particular, AR-theory provides theoretical justification for topological data analysis.

Some recent results on persistent Betti numbers.

A summary of

We examine the flow space of proper CAT(0)-spaces and warped products of Riemannian manifolds and intrinsic metric spaces. Then we construct some embeddings of the flow space of non-constant generalized geodesics on Hadamard manifolds and proper CAT(0)-spaces using warped products.