This is the research seminar of the Applied and Computational Topology group.
The seminar usually takes place on Tuesday 14–16 o'clock in the SFB room (02.06.011) unless indicated otherwise. Future appointments will be announced on the mailing list of the seminar.
In case you have questions or suggestions please contact Alexander Rolle.
| Date | Title | Speaker | Abstract |
|---|---|---|---|
t.b.a | t.b.a | Kristóf Huszár | t.b.a |
19.07.2024 | Topology-Preserving Data Compression | Bei Wang | Existing error-bounded lossy compression techniques control the pointwise error during compression to guarantee the integrity of the decompressed data. However, they typically do not explicitly preserve the topological features in data. When performing post hoc analysis with decompressed data using topological methods, preserving topology in the compression process to obtain topologically consistent and correct scientific insights is desirable. In this talk, we will discuss lossy compression methods that preserve the topological features in 2D and 3D scalar fields. Specifically, we aim to preserve the types and locations of local extrema as well as the level set relations among critical points captured by contour trees in the decompressed data. This talk is based on joint works with Lin Yan, Xin Liang, and Hanqi Guo. |
18.07.2024 | On the contractibility of the Rips complexes of $\mathbb{Z}^n$. | Ziga Virk | We will prove that the Rips complexes of $\mathbb{Z}^n$ are contractible for large parameters $r$ when using the word metric (i.e., as the Cayley graphs). The current bounds for the relevant scale parameters are derived from the Jung constants. We will explain the conjecture on how to obtain the optimal bounds for the scale parameters. The result is motivated by the geometric group theory, by the reconstruction results in topology, and by the stability theorems for persistent homology. Our approach is based on a novel concept of combinatorial topology: the local domination of a vertex in a simplicial complex. |
10.07.2024 | The Universal Coefficient Theorem for Homology - a more computational version | Lewis Ngo | The Universal Coefficient Theorem is a well-known theorem that relates the computation of homology with arbitrary coefficients to the calculation of integral homology groups. For example, homology with coefficients in $\mathbb{Z}/2\mathbb{Z}$ is a key tool for many questions about non-orientable manifolds; their top integral homology vanishes, while their top $\mathbb{Z}/2\mathbb{Z}$-homology is $\mathbb{Z}/2\mathbb{Z}$. In this talk, we discuss a more explicit approach to the statement and proof of the theorem. After introducing the necessary prerequisites, we will delve into the core concepts of the Smith normal form, which will be essential for the structure theorem of free chain complexes of finite rank. The aim is to present the methods in concrete computations of examples, including the real projective plane, and investigate the non-naturality of the splitting of the short exact sequence in the universal coefficient theorem more thoroughly. |
07.05.2024 | Cup Product Persistence and Its Efficient Computation | Abhishek Rathod | It is well-known that the cohomology ring has a richer structure than homology groups. However, until recently, the use of cohomology in the persistence setting has been limited to speeding up barcode computations. Some of the recently introduced invariants, namely, persistent cup-length, persistent cup modules and persistent Steenrod modules, to some extent, fill this gap. When added to the standard persistence barcode, they lead to invariants that are more discriminative than the standard persistence barcode. In this work, we devise an O(dn^4) algorithm for computing the persistent k-cup modules for all k∈{2,…,d}, where d denotes the dimension of the filtered complex, and n denotes its size. Moreover, we note that since the persistent cup length can be obtained as a byproduct of our computations, this leads to a faster algorithm for computing it for d ≥ 3. Finally, we introduce a new stable invariant called partition modules of cup product that is more discriminative than persistent k-cup modules and devise an O(c(d)n^4) algorithm for computing it, where c(d) is subexponential in d. The talk is based on joint work with Tamal Dey. |
19.03.2024 | Highly Symmetric Point Clouds | Mikael Vejdemo-Johansson | Point clouds with high degrees of symmetry have additional structure that may allow us to significantly speed up topological computations. In this talk I will report on work in progress on studying the persistent (co)homology pipeline on point clouds with a known (and large) group acting on them. I will describe the setup, the amount of information about the group action needed for improvements, a (partially) failed conjecture, and a 10x speedup in generating and traversing 60k simplices in the Vietoris-Rips complex of the 4-dimensional hypercube. |
12.12.2023 | What do we want from invariants of multiparameter persistence modules? | Luis Scoccola | Various constructions relevant to practical problems such as clustering and graph classification give rise to multiparameter persistence modules (MPPM), that is, linear representations of non-totally ordered sets. Much of the mathematical interest in multiparameter persistence comes from the fact that there exists no tractable classification of MPPM up to isomorphism, meaning that there is a lot of room for devising invariants of MPPM that strike a good balance between discriminating power and complexity of their computation. However, there is no consensus on what type of information we want these invariants to provide us with, and, in particular, there seems to be no good notion of “global” or “high persistence” features of MPPM. With the goal of substantiating these claims, as well as making them more precise, I will give an overview of the theory of multiparameter persistence, including joint works with Bauer and Oudot. I will mention no-go results for invariants of MPPM as well as recent work of Bjerkevik, which contains relevant open questions regarding the global structure of MPPM. |
05.12.2023 | Computation of projected barcodes for multiparameter persistence | Alex Fernandes | The projected barcode was recently introduced as an alternative to the well-known fibered barcode for multiparameter persistence. In this talk, I will explain a method that compute the projected barcode along linear forms for modules given via a finite free resolution. This analysis combines sheaf-theoretic and module-theoretic techniques, showing that multiparameter persistence modules can be converted into a special type of complexes of sheaves called conic-complexes, whose derived pushforwards by linear forms have predictable barcodes. This talk is based on a joint work with Steve Oudot and François Petit. |
14.11.2023 | Computational methods for multi-parameter persistence | Fabian Lenzen | Thesis defense prep talk. |
07.11.2023 | Topology-Driven Goodness-of-Fit Tests in Arbitrary Dimensions | Niklas Hellmer | In this talk, I will explain how to adopt the Euler characteristic curve (ECC) of a sample to perform one- and two-sample goodness of fit tests. Classical tools for this problem, like the Kolmogorov-Smirnov test, work well in one but not in higher dimensions . Our procedure, which we call TopoTests, works for samples of arbitrary dimension, having comparable power to the state-of-the-art tests in the one-dimensional case. It is demonstrated that the type I error of TopoTests can be controlled and their type II error vanishes exponentially with increasing sample size. Extensive numerical simulations of TopoTests are conducted to demonstrate their power for samples of various sizes. |
24.10.2023 | Obstructions to metric embeddings in computational topology | Nicolò Zava | Maps and embeddings of metric spaces are widely employed in computational mathematics. Examples are vectorisation methods (e.g., kernel methods to vectorise persistence diagrams) or invariants used to approximate hard-to-compute distances (e.g., the Gromov-Hausdorff distance, a known NP-hard problem). In this talk, I will recall techniques to detect obstructions to the existence of certain classes of metric embeddings, such as bi-Lipschitz and coarse embeddings. Then, several applications of these techniques in computational topology will be provided. More precisely, I will focus on the Gromov-Hausdorff space, spaces of persistence diagrams and spaces of lattices and periodic point sets. This talk is partially based on a joint work with Alexey Garber and Žiga Virk. |
26.09.2023 14:00 CEST | Master's thesis: Robust and Efficient Computation of Čech Persistence Barcodes | Sönke Clausen | We present an algorithm for the computation of Čech persistence barcodes, describe its implementation in C++ code and evaluate its performance. The persistence algorithm is developed as an adaptation of the Ripser software, known for its efficient computation of Vietoris-Rips persistence barcodes. This thesis features two major advancements to counteract the fact that Čech persistence is notoriously difficult to construct. We develop a generalized discrete Morse function as a perturbation to the Čech function, which can be constructed symbolically. This allows for a substantial shortcut to the computation of zero-apparent pairs (a large subset of persistence pairs). Additionally, we develop a minimal enclosing sphere algorithm specifically designed to be efficient within the persistence algorithm and high ambient dimension. The implementation of the persistence algorithm achieves to be significantly more efficient than previous software, especially in high ambient dimension. |
21.08.2023 | Bachelor's thesis: Computation of Reidemeister Torsion: A Numerical Algorithm for a Topological Invariant | Kai Fabio Neugebauer | The Reidemeister torsion stands as a well-known invariant within the realm of algebraic topology. For example, Reidemeister torsion is the key tool to classify lens spaces. However, its computation has proven to be a difficult endeavor in practice. In this talk, we discuss the intricacies of devising an implementable algorithm for computing Reidemeister torsions. After introducing the necessary prerequisites, we will delve into the core concepts of our newly developed algorithm. Our method enables the numerical calculation of Reidemeister torsion for the geometric realization of a simplicial set. We have successfully implemented our algorithm in SageMath and we look forward to presenting computed Reidemeister torsions for diverse examples, including the Poincaré homology 3-sphere, various lens spaces, and specific products of low-dimensional manifolds. |
20.07.2023 | Homological approximations in persistence theory | Thomas Brüstle | Multiparameter persistence modules appear in topological data analysis when dealing with noisy data. They defined over a wild algebra and therefore they do not admit a complete discrete invariant. One thus tries to “approximate” such a module by a more manageable class of modules. Using that approach we define a class of invariants for persistence modules based on ideas from homological algebra. This is a report on joint work with Claire Amiot, Benjamin Blanchette and Eric Hanson. |
18.07.2023 | Chromatic Alpha Complexes | Ondřej Draganov | Motivated by the need to analize vast amount of newly accessible data in the growing field of spatial biology, we study a generalization of the standard persistent homology pipeline for point sets. The input is a point set in Euclidean space together with an assignement of a color (category) to each point. The output is a "six-pack" of various different kinds of persistent diagrams that quantify features like "loops formed by blue points that are filled by orange points" or "blue components that are not yet connected by blue-orange paths". In this talk I will recall definitions for kernel, image and cokernel persistent homology, and introduce a discrete model we use to compute it – chromatic alpha complex. I will discuss relations between the different kinds of persistent homology, and give insights into the structure of the chromatic alpha complex, which proves to be an interesting object of study in its own right. The talk is based on the paper https://arxiv.org/abs/2212.03128. |
04.07.2023 | Sparse Higher Order Čech Filtrations | Bianca Dornelas | For a finite set of balls of radius r, the k-fold cover is the space covered by at least k balls. Fixing the ball centers and varying the radius, we obtain a nested sequence of spaces that is called the k-fold filtration of the centers. For k = 1, the construction is the union-of-balls filtration that is popular in topological data analysis. For larger k, it yields a cleaner shape reconstruction in the presence of outliers. We contribute a sparsification algorithm to approximate the topology of the k-fold filtration. Our method is a combination and adaptation of several techniques from the well-studied case k = 1, resulting in a sparsification of linear size that can be computed in expected near-linear time with respect to the number of input points. The talk is based on the paper https://drops.dagstuhl.de/opus/volltexte/2023/17870/. |
27.06.2023 | Ripser: efficient computation of Vietoris-Rips persistence barcodes | Ulrich Bauer | Continuation of the talk from 06.06.2023. |
20.06.2023 | Stabilizing decomposition of multiparameter persistence modules | Håvard Bakke Bjerkevik | While decomposition of one-parameter persistence modules behaves nicely, as demonstrated by the algebraic stability theorem, decomposition of multiparameter modules is well known to be unstable in a certain precise sense. I will explain why naive attempts to build a meaningful stability theory for multiparameter module decomposition tend to fail, and then present recent work showing that decomposition stability theorems can be proved despite these difficulties. I will also talk about a conjecture that would strengthen the main stability result for staircase decomposable modules, is relevant for applications of relative homological algebra to multipersistence, and can be understood without knowing anything about persistence. The talk is based on the arXiv preprint https://arxiv.org/abs/2305.15550. |
09.06.2023 | Efficient Two-Parameter Persistence Computation via Cohomology | Fabian Lenzen | Clearing is a simple but effective optimization for the standard algorithm of persistent homology (ph), which dramatically improves the speed and scalability of ph computations for Vietoris-Rips filtrations. Due to the quick growth of the boundary matrices of a Vietoris-Rips filtration with increasing dimension, clearing is only effective when used in conjunction with a dual (cohomological) variant of the standard algorithm. This approach has not previously been applied successfully to the computation of two-parameter ph. The talk is based on the paper https://drops.dagstuhl.de/opus/volltexte/2023/17865/. |
06.06.2023 | Ripser: efficient computation of Vietoris-Rips persistence barcodes | Ulrich Bauer | Continuation of the talk from 23.05.2023. |
23.05.2023 | Ripser: efficient computation of Vietoris-Rips persistence barcodes | Ulrich Bauer | We will discuss implementation details and address questions regarding similar and related computations in settings beyond Vietoris–Rips complexes. https://link.springer.com/article/10.1007/s41468-021-00071-5, https://github.com/Ripser/ripser |
25.04.2023 | The Localized Union-of-Balls Bifiltration | Matthias Söls | We propose an extension of the classical union-of-balls filtration of persistent homology: fixing a point q, we focus our attention to a ball centered at q whose radius is controlled by a second scale parameter. We discuss an absolute variant, where the union is just restricted to the q-ball, and a relative variant where the homology of the q-ball relative to its boundary is considered. Interestingly, these natural constructions lead to bifiltered simplicial complexes which are not k-critical for any finite k. We also argue that some of the recent algorithmic advances for 2-parameter persistence (which usually assume k-criticality for some finite k) carry over to the ∞-critical case. Slides |
19.04.2023 | Applications of Topological Data Analysis in Mesoscale Eddy tracking | Jacob Skarby | |
08.02.2023 | Interval decomposition and coarse graining | Rojyar Rajabpour | |
13.07.2022 | The spectrum of the real line | Motivated by the study of persistence modules we investigate the linear representation of the real line and, more generally, of totally ordered sets. We provide a classification of isoclasses of indecomposable injective representations. The set of these forms a topological space called the spectrum, which refines the topology induced by the interleaving distance. | |
| 06.07.2022 | Intersection homology and singularities in data | The homology of manifolds enjoys a remarkable symmetry: Poincaré duality. For example, in the classification of high-dimensional manifolds Poincaré duality plays a crucial role as it serves as a gateway for constructing a fundamental bordism invariant, the signature. Classifying manifolds via surgery theory relies on modifying a manifold by performing geometric surgeries that do not affect the bordism type of the manifold. Since the signature is a bordism invariant, it does not change under surgery and thus serves as a basic obstruction to performing surgery. However, Poincaré duality already fails at the very beginning of allowing singularities in the underlying space. Goresky and MacPherson therefore developed intersection homology groups, which restore Poincaré duality also for certain singular spaces. In this talk, we will introduce the basic notions and give some of the results that were originally published in the first article on intersection homology by Goresky and MacPherson. Subsequently, we discuss how intersection homology and local homology might be useful in the presence of singularities in datasets. | |
| 05.07.2022 | Get-together: Discussing ATMCS10 | everyone | |
| 25.05.2022 | The extended persistence diagram introduced by Cohen-Steiner, Edelsbrunner, and Harer is an invariant of real-valued continuous functions, which are 𝔽-tame in the sense that all open interlevel sets have degree-wise finite-dimensional cohomology with coefficients in a fixed field 𝔽. We show that relative interlevel set cohomology (RISC), which is based on the Mayer--Vietoris pyramid by Carlsson, de Silva, and Morozov, categorifies this invariant in some sense. More specifically, we define an abelian Frobenius category pres(𝐽) of presheaves, which are presentable in some sense, such that for an 𝔽-tame function f : X → ℝ its RISC h(f) is an object of pres(𝐽) and moreover, the extended persistence diagram Dgm(f) uniquely determines - and is determined by - the corresponding element [h(f)] ∈ K₀(pres(𝐽)) in the Grothendieck group K₀(pres(𝐽)) of the abelian category pres(𝐽). This is in close analogy to the following categorification of the Euler characteristic: Given a topological space X the Euler characteristic χ(X) ∈ ℤ uniquely determines [Δ(X)] ∈ K₀(Ab), which is the element in the Grothendieck group K₀(Ab) of the category of abelian groups Ab corresponding to the singular chain complex Δ(X). As an intermediate step we show that pres(𝐽) is the Abelianization of the (localized) category of complexes of 𝔽-linear sheaves on ℝ, which are tame in the sense that sheaf cohomology of any open interval is finite-dimensional in each degree. This yields a close link between derived level set persistence by Curry, Kashiwara, and Schapira and the categorification of extended persistence diagrams. This is joint work with Ulrich Bauer. | ||
18.05.2022 | Efficient computation of 2-parameter persistent cohomology | Fabian Lenzen | Two central optimisation schemes in one-parameter persistence rely on the fact that the computation of persistent cohomology, albeit yielding equivalent results, can be carried out far more efficiently; namely, clearing and implicit matrix representations. In two-parameter persistence, however, optimisations using cohomology cannot be applied straightforwardly anymore, due to the fact that, unlike the one-parameter case, cochain modules are not free anymore. Consequently, performance of existing implementations for two-parameter persistent homology lags behind that of software for one-parameter persistence. I will show how cohomology can be used to develop efficient algorithms for two-parameter persistence nevertheless by considering free resolutions of cochain modules instead, using a result that links free resolutions of persistent homology and cohomology. |
11.05.2022 | Master's thesis: Efficient Topological Data Analysis Using Persistent Relative Homology | Sebastian Kreisel | We start with a brief review of persistent homology that is geared towards computation and the dualities in persistent (co)homology. Motivated by the large GISAID SARS-CoV-2 virus genome data set, we then investigate the computation of persistent relative homology as an alternative to the well-established absolute counterpart. Implemented as part of the software Ripser, we analyze and compare various runtime characteristics for relative subcomplexes of differing size. After this, we present another, more direct approach to deriving homology representatives from a computation in the cohomological setting that is based on a dual basis calculation. The last part of this talk is a practical introduction to modifying and extending Ripser and showcases various small features developed as part of this thesis project. |
04.05.2022 | The Shift-Dimension: An Algebraic Invariant of Multiparameter Persistence Modules | Anna-Laura Sattelberger (MPI for Mathematics in the Sciences, Leipzig) | In the one-parameter case, persistence modules naturally are graded modules over the univariate polynomial ring and hence perfectly understood from an algebraic point of view. By a classical structure theorem, one associates the so-called “barcode”, from which one reads topological features of the data. |
20.04.2022 | Master's thesis: From Morse to Floer Homology with a View towards Arnold's Conjecture | David Lanners | The Arnold conjecture (AC) states that the number of periodic orbits of a Hamiltonian system can be bounded from below by the sum of the Betti numbers. People familiar with Morse theory might recognise a certain similarity to the so-called "Morse inequalities" which roughly state that the number of critical points of a Morse function on a compact manifold can be bounded from below in the same way. This connection is by no means a coincidence, and we will follow Floer's construction of an "infinite-dimensional Morse theory" in order to prove the AC. If time permits, I will then showcase how these, at the time, goundbreaking novel ideas of Floer are used in modern symplectic geometry. |
09.03.2022 | Parity Property of Hexagonal Sliding Puzzles | Erika Roldan | We study the puzzle graphs of hexagonal sliding puzzles of various shapes and with various numbers of holes. The puzzle graph is a combinatorial model which captures the solvability and the complexity of sequential mechanical puzzles. Questions relating to the puzzle graph have been previously studied and resolved for the 15 Puzzle which is the most famous, and unsolvable, square sliding puzzle of all times. The puzzle graph is also a discrete model for the configuration space of hard tiles (hexagons or squares) moving on different tessellation-based domains. Understanding the combinatorics of the puzzle graph leads to understanding some aspects of the topology of these configuration spaces. |
23.12.2021 | Algorithms in Discrete Morse Theory and Combinatorial Topology | Abhishek Rathod | This dissertation is a complexity theoretic study of well-known problems in combinatorial topology. In the first part, an open question concerning the (in)approximability of Morse matching is resolved, and existing results concerning the parameterized complexity of Morse matching are improved upon. In the second part, certain natural problems in simple homotopy theory are shown to be hard from the point of view of parameterized complexity. The third part describes asymptotically fastest known algorithms for computing minimum $1$-homology bases of simplicial complexes by exploiting the matroid structure of homology bases. In the fourth and the final part, the notion of cuts is generalized from graphs to simplicial complexes, and the parameterized complexity of these high-dimensional cuts is studied. The final part also provides a polynomial time algorithm for a high-dimensional cut problem in the special case of surfaces. The unifying theme across the four parts is the value of complexity theory in the study of problems in combinatorial topology. |
| 15.12.2021 | Alexander Rolle | The degree-Rips bifiltration is the most computable of the parameter-free, density-sensitive bifiltrations in topological data analysis. It is known that this construction is stable to small perturbations of the input data, but its robustness to outliers is not well understood. In recent work, Blumberg--Lesnick prove a result in this direction using the Prokhorov distance and homotopy interleavings. Based on experimental evaluation, they argue that a more refined approach is desirable, and suggest the framework of homology inference. Motivated by these experiments, we consider a probability measure that is uniform with high density on an annulus, and uniform with low density on the disc inside the annulus. We compute the degree-Rips complexes of this probability space up to homotopy type, using the Adamaszek--Adams computation of the Vietoris--Rips complexes of the circle. These degree-Rips complexes are the limit objects for the Blumberg--Lesnick experiments. We argue that the homology inference approach has strong explanatory power in this case, and suggest studying the limit objects directly as a strategy for further work. | |
| 08.12.2021 | Realising persistent homology by subcomplexes | Pepijn Roos Hoefgeest | While a given persistence module is, up to isomorphism, completely determined by its barcode, it is not always clear what geometrical or topological information is conveyed by the elements of a barcode. One way to address this, which has received a lot of attention in the literature, is to look for representative cycles for a bar, which are of minimum weight. We propose a novel approach, in which the bars are represented by subcomplexes, rather than by cycles, which are minimal in a topological sense. After giving further motivation and a precise definition, we discuss results on the computational complexity of finding such subcomplexes. |
| 24.11.2021 | Effective constructions in algebraic topology with applications to machine learning and condensed matter physics | Anibal M. Medina-Mardones (MPIM) | It has long been envisioned that the strength of the barcode invariant could be increased using cohomology operations. Leveraging recent advances in the computation of Steenrod squares, we introduce a new family of computable invariants on mod 2 persistent cohomology termed $Sq^k$-barcodes. We present a complete algorithmic pipeline for their computation and illustrate their real-world applicability using the space of conformations of the cyclo-octane molecule. Time permitting, we will discuss further cochain level structures relevant to the classification of topological phases of matter. |
| 27.10.2021 | Output-sensitive algorithms for computing persistence | Abhishek Rathod | It is well-known that the persistent homology of a filtered simplicial complex can be computed in matrix multiplication time in the worst case. Additionally, Chen and Kerber devised algorithms for computing persistence with output-sensitive complexity bounds. In this talk, we will introduce two output-sensitive algorithms for computing persistence with bounds that are more refined compared to bounds given by Chen and Kerber. Time permitting, we will discuss how the new algorithms can be viewed in the light of algebraic Morse theory. |
| 20.10.2021 | Master's thesis: An explicit Construction for Derived Persistence | Anton Loumakos | Relative interlevel set homology with respect to a piecewise linear function was |
| 04.10.2021 | Discrete Morse theory and Vietoris-Rips complexes of metric gluings | Fabian Roll | How is the Vietoris-Rips complex of the union of two metric spaces related to the union of the Vietoris-Rips complexes? This question has been addressed in [1] and [2], where they show, by using very different approaches, that under suitable assumptions both complexes are homotopy equivalent. While [1] uses simplicial collapses, [2] relies on more abstract techniques including homotopy fibers. In this talk, I will illustrate how discrete Morse theory can be used to give an answer to this question. This approach is naturally closely related to the techniques in [1], but we will make use of the obstruction complex as defined in [2]. Moreover, I will also point out how to prove some more refined theorems in [2] and conjecture a generalization.
[2] W. Chachólski, A. Jin, M. Scolamiero, F. Tombari, Homotopical decompositions of simplicial and Vietoris Rips complexes, J Appl. and Comput. Topology. 5 (2021) 215–248. https://doi.org/10.1007/s41468-021-00066-2. |
| 19.08.21 | The Shape of Vision Decoding: the Primary Visual Cortex with Homology | Loek van Rossem | We study the topology of the primary visual cortex’s |
| 13.08.21 | Persistence in functional topology and a correction to a theorem of Morse | Ulrich Bauer | During the 1930s, Marston Morse developed a vast generalization of what is commonly known as Morse theory relating the critical points of a semi-continuous functional with the topology of its sublevel sets. Morse and Tompkins applied this body of work, referred to as functional topology, to prove the Unstable Minimal Surface Theorem in the setting defined by Douglas' solution to Plateau's Problem. |
| 11.08.21 | Bachelor's thesis: Homological Algebra in Puppe-exact Categories | Markus R. | A category is called Puppe-exact or p-exact if it has a zero object, it has all kernels and cokernels, every mono is a kernel and every epi is a cokernel, and every morphism has an epi-mono-factorization. Put informally, a Puppe-exact category is an abelian category that need not have (co)products. Put formally, a category is abelian if and only if it is additive and p-exact. Also, the p-exact category of matchings only has trivial products. The product lemma as stated by Johann B. Leicht in 1964 is a stepping-stone for many homological theorems as the snake lemma. We sketch an alternative proof. |
| 26.07.21 | Jacob Leygonie | We study the inverse problem for persistent homology: For a fixed simplicial complex, we analyse the fiber of the continuous map PH on the space of filters that assigns to a filter the barcode of its associated sublevel set filtration. We find that PH is best understood as a map of stratified spaces. Over each stratum of the barcode space the map PH restricts to a fiber bundle with fiber a polyhedral complex. We illustrate the theory on the example of the triangle, which is rich enough to have a Möbius band as one of its fibers. | |
| 12.07.21 | L²-Betti numbers and profinite completions of groups , notes | Nico Stucki | |
| 12.04.21 | Power Operations in Higher Semiadditive Categories | Jan Jendrysiak | In a 2013 paper, J. Lurie and M. Hopkins introduced the notion of ambidexterity, a kind of higher semiadditivity, and showed that it applies to certain categories of spectra arising in chromatic homotopy theory. Specifically the limit and colimit over a \pi-finite space in this category both exist and are actually equivalent. This is as a homotopy theoretic generalisation of the classical notion of a semiadditive category, where all finite products and coproducts - i.e. limit and colimit over a set - exist and agree. In the classical case this implies that there is an addition on the morphism sets, whereas higher semiadditivity lets us add morphisms "over spaces". Building on this framework, S. Carmeli, M. Schlank and L. Yanovski in 2018 proved that when a morphism space in such a category is a (homotopy theoretic) ring, then the interplay between the multiplication of the ring and the addition over a classifying space generates a p-derviation: a kind of power operation, which they successfully used to prove new properties about the aforementioned categories of spectra. We plan to construct a whole system of power-operations on these rings which we suspect gives them the structure of beta-rings. |
| 15.03.21 | Persistent obstruction theory for a model category of measures with applications to data merging | Paul Bendich (Geometric Data Analytics and Duke University) | Collections of measures on compact metric spaces form a model category (“datacomplexes”), whose morphisms are marginalization integrals. The fibrant objects in this category represent collections of measures in which there is a measure on a product space that marginalizes to any measures on pairs of its factors. The homotopy and homology for this category allow measurement of obstructions to finding measures on larger and larger product spaces. The obstruction theory is compatible with a fibrant filtration built from the Wasserstein distance on measures. Despite the abstract tools, this is motivated by a widespread problem in data science. Datacomplexes provide a mathematical foundation for semi-automated data-alignment tools that are common in commercial database software. Practically speaking, the theory shows that database JOIN operations are subject to genuine topological obstructions. Those obstructions can be detected by an obstruction cocycle and can be resolved by moving through a filtration. Thus, any collection of databases has a persistence level, which measures the difficulty of JOINing those databases. Because of its general formulation, this persistent obstruction theory also encompasses multi-modal data fusion problems, some forms of Bayesian inference, and probability couplings. |
| 08.03.21 | Introduction to Spectral Sequences | Fabian Roll | This is an expository talk on spectral sequences. First, we will discuss their history and give the abstract definition. Then, we will see how they arise from filtrations of chain complexes, apply this to an easy example and discuss the relation to persistent homology. Further, we apply spectral sequences to prove the symmetry of the Tor functor and to deduce a homological nerve theorem (Mayer-Vietoris spectral sequence). If time permits, we will also shortly revisit Dress' construction of the Serre spectral sequence for fibrations. |
| 01.03.21 | Computing persistent homology: A Morse theory update | Abhishek Rathod | In this talk, we discuss an algorithm for computing persistent homology with novel output sensitive complexity bounds. The talk is based on joint work with Ulrich Bauer and Talha bin Masood. |
| 15.02.21 | Topological Expressive Power of Neural Networks | António Leitão | In this talk I propose a topological description of neural network expressive power. I will present the space of persistence diagrams corresponding to decision boundaries realized by a neural architecture as a measure of its intrinsic expressive power. By sampling a large number of neural architectures with different sizes and design, I will show how such measure of expressive power depends on the properties of the architectures, like depth, width and other related quantities. |
| Tue 09.02.21, 17:00 CET | Homology crowding in configuration spaces of disks | Hannah Alpert | Configuration spaces of disks in a region of the plane vary according to the radius of the disks, and their topological invariants such as homology also vary. Realizing a given homology class means coordinating the motion of several disks, and if there is not enough space for the disks to move, the homology class vanishes. We explore how clusters of orbiting disks can get too crowded, some topological conjectures that describe this behavior, and some progress toward those conjectures. |
| 26.01.21 | A Topological Approach to Inferring the Intrinsic Dimension of Convex Sensing Data | Min-Chun Wu | We consider a common measurement paradigm, where an unknown subset of an affine space is measured by unknown continuous quasi-convex functions. Given the measurement data, can one determine the dimension of this space? In this paper, we develop a method for inferring the intrinsic dimension of the data from measurements by quasi-convex functions, under natural generic assumptions. The dimension inference problem depends only on discrete data of the ordering of the measured points of space, induced by the sensor functions. We introduce a construction of a filtration of Dowker complexes, associated with measurements by quasi-convex functions. Topological features of these complexes are then used to infer the intrinsic dimension. We prove convergence theorems that guarantee to obtain the correct intrinsic dimension in the limit of large data, under natural generic assumptions. We also illustrate the usability of this method in simulations. |
| 18.01.21 | Topology of Nerves, Formal Concepts and Their Applications | Zelong Li | In this expository talk, we will go over the notion of poset, its geometric realization and two simplification methods. Moreover, Galois connection plays a central role to describe the homotopy theory of posets. On the nerves of a topological space one can characterize not only homotopic but combinatorial information of the covering via the lattices of Formal Concepts. Finally, we briefly introduce their recent practices in neuroscience. Our general goal is to gather these various tools to consider the further applications in homotopy-theoretic TDA. |
| 12.01.21 | Monge-Ampère equations and inverse problems in optics | Boris Thibert, Université Grenoble Alpes | Non-imaging optics is a field of optics which is interested in designing optical components, such as mirrors or lenses, that transfer a given source light to a prescribed target. The goal is not to simulate the trajectory of the light through an optical component, which would be the direct problem, but instead to build the shape of a mirror or a lens that transfers a source light to a given target light. This inverse problem amounts in different settings to solving Monge-Ampère type equations. In this talk, I will show how these equations are connected to optimal transport and can be solved using a geometric discretization called semi-discrete. I will also present the design of different kinds of mirrors or lenses that allow to transfer any point or parallel source light to any target. This work is in collaboration with Quentin Mérigot and involves Jocelyn Meyron. |
| 07.12.20 | Amenable Category and Complexity | Pietro Capovilla | Amenable category is a variant of the Lusternik-Schnirelman category, based on covers by amenable open subsets. We study the relation between amenable category and Farber's topological complexity. |
| 30.11.20 | Video session: Studying the space of persistence diagrams using optimal partial transport | Théo Lacombe, Vincent Divol | First talk: Introduction and theoretical background
Second talk: Applications
|
| 25.11.20 | Injective presentation computation for 2D-persistent cohomology | Fabian Lenzen | This will be a rather informal presentation of the present state of our work on this project. Let X be a 1-critical bi-filtered simplicial complex, i.e., every simplex σ ∈ X has a unique lowest degree in 𝐙² at which it enters the filtration of X. Cycles Z⁎(X) are a free 2D persistence module, and Lesnick and Wright have presented an algorithm that computes Z⁎(X), which is the key ingredient in their computation of a free presentation of the persistent homology H⁎(X). In contrast, we are interested in the persistent cohomology H*(X) of X, of which, due to duality, we want to compute an injective rather than a free resolution. Since cocycles Z*(X) are neither free nor injective, a presentation of H*(X) cannot be computed as easily as a presentation of H⁎(X), and our goal is to devise a method for the computation of the former, based on what we know about the latter. |
| 12.11.20 | A probabilistic approach to rigidity of the curve complex | We describe the use of the multiparametric model for random simplicial complexes by Costa and Farber to give probabilistic evidence to Ivanov's Metaconjecture on actions of the Mapping class group on simplicial complexes associated to a surface. | |
| 29.10.20 | Video session: | Raul Rabadan | COVID-19 is a disease caused by a coronavirus named SARS-CoV-2. As the virus has been spreading around the world, hundred of thousands of viral genomes have been sequenced. Genomes provide an accurate record of variation and evolution and can inform how these viruses emerge and evolve. In this talk I will discuss how mutations and recombinations shape SARS-CoV-2 evolution, and how topological data analysis techniques can help to understand the role of these processes in the emergence of this and other potential future viruses. |
| 17.09.20 | Video session: | Wojciech Chachólski | Data analysis is a balancing act of simplification and ignoring most of the information available on the one hand, and retaining what might be meaningful for the particular task on the other. The same balancing act of extracting simplifying summaries is also at the core of homotopy theory. The main goal of this first of the two seminars (second given by Barbara Giunti) is to explain how to use (co)localisation techniques from homotopy theory to extract simplifying invariants. In this case, the simplification is achieved by approximating arbitrary objects by other objects that are simpler and more manageable, such as the class of cofibrant objects in a model category. Our work (with B. Giunti and C. Landi) is based on the realisation that the category of tame persistent chain complexes over a field admits a model structure for which there is a surprisingly simple decomposition theorem describing all indecomposable cofibrant objects. The aim of this lecture is to introduce these techniques to a general audience. How to use them is the subject of the second seminar. |
| 03.09.20 | A Short Introduction to Gröbner Bases | Tim Reinhardt | We generalize univariate polynomial division to multiple variables. For that, we define monomial orderings and establish a division algorithm on K[x_1, …, x_n]. To obtain unique remainders and to solve the ideal-membership problem, we introduce Gröbner bases and prove their most important properties. We briefly also discuss their construction and applications. |
| 28.08.20 | k-decomposable and shellable complexes | Russ Woodroofe | Shellability is a topological and combinatorial tool, useful for computing homotopy and homeomorphism type of a simplicial complex, simultaneously with several related combinatorial/topological invariants. A drawback is that shellings are relatively difficult to find. One obstruction is that the definition of a shelling builds up (or tears down) a complex in a facet by facet manner. The framework of k-decomposability simplifies by grouping facets together. I'll show how I used this framework to shell the independence complexes of chordal clutters, and discuss relationships with other problems. |
| 06.08.20 | Categories of fractions | Abhishek Rathod | In this talk we will go through two papers: 1. Abstract homotopy theory and generalized sheaf cohomology - Kenneth Brown 2. Categories of fractions revisited - Tobias Fritz The plan for the talk is to say a bit more on categories of fractions and then see why categories with all objects fibrant (or all objects cofibrant) admit a 2-arrow calculus. |
| 24.07.20 | Paramaterized inapproximability of discrete Morse theory | Abhishek Rathod | In this talk, we will study a natural optimization problem in discrete Morse theory, namely, the problem of minimizing the number of critical simplices from the point of view of inapproximability and parameterized complexity. This talk is based on joint work with Ulrich Bauer. |
| 23.07.20 | Benedikt Fluhr | In these two talks, we discuss the relative interlevel set homology associated to a continuous function. This invariant is a continuously indexed version of the Mayer–Vietoris pyramid introduced by Carlsson, de Silva, and Morozov. We will discuss how the extended persistence diagram can be obtained from relative interlevel set homology and show that the isomorphism class of relative interlevel set homology is uniquely determined by the extended persistence diagram, due to Cohen-Steiner, Edelsbrunner, and Harer. To this end, we will discuss a decomposition theorem for relative interlevel set homology. The results presented are joint work with Ulrich Bauer and Magnus Botnan and are closely related to two articles by Bendich, Edelsbrunner, Morozov, and Patel as well as Berkouk, Ginot, and Oudot. | |
| 16.07.20 | Benedikt Fluhr | ||
| 09.07.20 | AATRN practice talk: The fundamental group of 2-dimensional random cubical complexes | Erika Roldan Roa | We study the fundamental group of certain random 2-dimensional cubical complexes which contain the complete 1-skeleton of the d-dimensional cube, and where every 2-dimensional square face is added independently with probability p. These are cubical analogues of Linial–Meshulam random simplicial complexes, and also simultaneously are 2-dimensional versions of bond percolation on the hypercube. Our main result is that if p ≤ 1/2, then with high probability the fundamental group of a random cubical complex is nontrivial, and if p > 1/2 then with high probability it is trivial. As a corollary, we get the same result for homology with any coefficient ring. We also study the structure of the fundamental group below the transition point, especially its free factorization. |
| 02.07.20 | Fabian Lenzen | Operads are a tool that formalise the definitions of algebras of different kinds. They allow to define associative, commutative, dg-, Lie and other algebras uniformly as algebras over certain operads. Some earliest instances of explicitly defined operads occurred in topology, where they have been introduced to describe the algebraic structure of iterated loop spaces elegantly. The relations these adhere to have led to the construction of A∞-algebras, E∞-algebras and the like. We shall see that instances of these naturally arise in topological and algebraic contexts and that they nicely complement the theory of dga-algebras. | |
| 25.06.20 | Fabian Lenzen | ||
| 18.06.20 | SoCG practice talk: Fast Algorithms for Minimum Cycle Basis and Minimum Homology Basis | Abhishek Rathod | We study the problem of finding a minimum homology basis, that is, a shortest set of cycles that generates the 1-dimensional homology classes with ℤ₂ coefficients in a given simplicial complex K. This problem has been extensively studied in the last few years. For general complexes, the current best deterministic algorithm, by Dey et al. [Dey et al., 2018], runs in O(N^ω + N² g) time, where N denotes the number of simplices in K, g denotes the rank of the 1-homology group of K, and ω denotes the exponent of matrix multiplication. In this paper, we present two conceptually simple randomized algorithms that compute a minimum homology basis of a general simplicial complex K. The first algorithm runs in Õ(m^ω) time, where m denotes the number of edges in K, whereas the second algorithm runs in O(m^ω + N m^{ω-1}) time. |
| 18.06.20 | SoCG practice talk: The Reeb Graph Edit Distance Is Universal | Ulrich Bauer | We consider the setting of Reeb graphs of piecewise linear functions and study distances between them that are stable, meaning that functions which are similar in the supremum norm ought to have similar Reeb graphs. We define an edit distance for Reeb graphs and prove that it is stable and universal, meaning that it provides an upper bound to any other stable distance. In contrast, via a specific construction, we show that the interleaving distance and the functional distortion distance on Reeb graphs are not universal. |
04.06.20 (10:00AM) | The Exhaustive Reduction and Discrete Morse Theory | Fabian Roll | In this talk, we will first recap the definition of the exhaustive reduction and the basics of discrete morse theory. Then, we will discuss results that connect these concepts. We will also see experiments that hint towards applications to surface reconstruction problems. |
28.05.20 (10:00AM) | Evolution of the homology and related geometric properties of the Eden Growth Model . | Erika Roldan Roa | 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. This process has been used as a model for the growth of aggregations, tumors, and bacterial colonies and the healing of wounds, among other natural processes. In this talk, we study the natural higher-dimensional generalization of the EGM, and we analyze the topology and local geometry of the resulting structure, establishing asymptotic bounds for Betti numbers. Our main result is that the Betti numbers grow at a rate between the conjectured rate of growth of the site perimeter and the actual rate of growth of the site perimeter. We also present the results of computational experiments on finer aspects of the geometry and topology, such as persistent homology and the distribution of shapes of holes. |
14.05.20 (10:00AM) | Shellings from relative shellings: A simpler proof for hardness of shellability | Abhishek Rathod | Shellings of simplicial complexes have long been a useful tool in topological and algebraic combinatorics. Shellings of a complex expose a large amount of information in a helpful way, but are not easy to construct, often requiring deep information about the structure of the complex. It is natural to ask whether shellings may be efficiently found computationally. The complexity of shellability was a long-standing open problem in combinatorial topology. This was settled by Goaoc, Paták, Patáková, Tancer and Wagner who established the NP-completeness of shellability. More recently, Santamaria-Galvis and Woodroofe provided a simpler proof. In this talk, we will give an overview of how their gadget works. |
07.05.20 (2:15PM) | Combinatorial models of global dynamics: learning cycling motion from data | David Hien | Conley's fundamental theorem for dynamical system states that every dynamical system on a compact set decomposes into a gradient-like and a recurrent part. In this talk we present a computational procedure for modeling the dynamics inside a recurrent set. Since this method only requires a time series as input, is can also be used for detection and modeling of quasi-periodic dynamics in time series. We will also discuss a construction of circle-valued coordinates on simplicial complexes which is the main topological tool for our procedure. |
09.03.20 (2:00PM) | Persistent Homology and Morse’s Functional Topology | Maximilian Schmahl | In the 1930s, Marston Morse developed a very general version of his famous work on critical points to study minimal surfaces. We show how what he calls Funtional Topology encodes essentially the same information as the modern theory of persistence diagrams. While doing so, we present a counterexample to one of Morse’s ”theorems”, discuss topological conditions for q-tameness of sublevel set persistence and develop some general machinery for working with persistence modules. |
05.03.20 (01:00PM) | Evolution of the homology and related geometric properties of the Eden Growth Model | Erika Roldan Roa | The Eden growth model (EGM) is a discrete stochastic model of cell or bacterial growth: in the d-dimensional cubical lattice, start with one cell at the origin; then at each time step, add one cell at the perimeter uniformly at random. We study the homology of the resulting cluster and its evolution in time. Using a characterization of how the homology evolves step by step, we performed computational experiments to establish conjectures related to the geometry and topology of the 2- and 3-dimensional EGM. We also prove, conditioning on a long-standing conjecture about the growth of the perimeter, that in the d-dimensional EGM, the rank of the (d-1)th homology group grows linearly with respect to the site perimeter. The EGM can be seen as a First Passage Percolation model after a proper time-scaling. With this work, we introduce tools and techniques from stochastic topology and topological data analysis to measure the evolution of the topology of the EGM and, in general, in FPP models. Joint work with Benjamin Schweinhart. |
| 12.02.20 | The chromatic number of random Borsuk graphs | Matthew Kahle (Ohio State University) | We introduce a new model of random graph. Take for vertices n random points on a d-dimensional sphere, and connect vertices by an edge whenever they are nearly antipodal. We are interested in the chromatic number of this graph. We are able to in many cases to determine it exactly, with high probability, using topological methods. This gives easy examples families of graphs which are locally bipartite but globally have arbitrarily large chromatic number. |
| 20.12.19 | Double complexes as sums of indecomposables | Jonas Stelzig (LMU) | Every (bounded) double complex is the direct sum of indecomposable double complexes and the indecomposable ones are 'squares' and 'zigzags'. I will prove this statement and sketch some algebraic and geometric applications. |
| 19.12.19 | Decomposition of Algebra-modules over finite fields | Fabian Lenzen | Lux and Szőke have presented [1] an algorithm which computes the direct sum decomposition of a finite dimensional module M of an algebra A over a finite field k into its indecomposable summands, together with an explicit isomorphism between M and this direct sum. They do so by decomposing the head of the regular End M-module and lifting suitable basis elements to deduce the decomposition of the regular End M-module itself. In the talk, we shall understand how this algorithm computes the decomposition. |
| 06.12.19 | UMAP: Uniform Manifold Approximation and Projection | Fabian Roll | In this talk we will discuss the theoretical part of the paper mentioned in the title. We will discuss the main ideas including the relation between fuzzy simplicial sets and extended pseudometric spaces. |
| 29.11.19 | An introduction to (∞,1)-categories via Segal spaces, and cobordisms | This talk will give an introduction to the ideas of higher category theory. We will mainly discuss the model of complete Segal spaces and discuss how to understand and use them as an end user. The category of cobordisms will serve as a running example. Many questions and discussions are welcome! | |
| 05.11.19 | Gromov-Wasserstein distances and distributional invariants of datasets | Facundo Memoli (Ohio State University) | The Gromov-Wasserstein (GW) distance is a generalization of the standard Wasserstein distance between two probability measures on a given ambient metric space. The GW distance assumes that these two probability measures might live on different ambient spaces and therefore implements an actual comparison of pairs of metric measure spaces. Metric-measure spaces are triples (X,dX,muX) where (X,dX) is a metric space and muX is a Borel probability measure over X and serve as a model for datasets. In practical applications, this distance is estimated either directly via gradient based optimization approaches, or through the computation of lower bounds which arise from distributional invariants of metric-measure spaces. One particular such invariant is the so called ‘global distance distribution’ of pairwise distances. This talk will overview the construction of the GW distance, the stability of distribution based invariants, and will discuss some recent results regarding the injectivity of the global distribution of distances for smooth planar curves, hypersurfaces, and metric trees. |
| 13.09.19 | Fast and Simple Algorithms for Minimum Cycle Basis and Minimum Homology Basis. | Abhishek Rathod | We study the problem of finding a minimum homology basis, that is, a shortest set of cycles that generates the 1-dimensional homology classes with Z_2 coefficients in a given simplicial complex K. This problem has been extensively studied in the last few years. For general complexes, the current best deterministic algorithm, by Dey et al., runs in O(N^\omega + N^2 g) time, where N denotes the number of simplices in K, g denotes the rank of the 1 homology group of K, and \omega denotes the exponent of matrix multiplication. Dey et al. also designed a randomized 2-approximation algorithm for the same problem that runs in O(N^\omega \sqrt{N \log N}) expected time. In this paper, we present two simple randomized algorithms that computes the minimum homology basis of a general simplicial complex K. The first algorithm runs in \tilde{O (m^\omega) time, where m denotes the number of edges in K, whereas the second algorithm runs in O(N m^{\omega-1}) time. We also study the problem of finding a minimum cycle bases in an undirected graph G with n vertices and m edges. The best known algorithm for this problem runs in O(m^\omega) time. Our algorithm, which is much simpler, but slightly more expensive, runs in \tilde{O}(m^\omega) time. |
| 02.09.19 | Parametrized Complexity of Expansion Height | Abhishek Rathod | Deciding whether two simplicial complexes are homotopy equivalent is a fundamental problem in topology, which is famously undecidable. There exists a combinatorial refinement of this concept, called simple-homotopy: two simplicial complexes are of the same simple-homotopy type if they can be transformed into each other by a sequence of two basic homotopy equivalences, an elementary collapse and its inverse, an elementary expansion. In this article we consider the following related problem: given a 2-dimensional simplicial complex, is there a simple-homotopy equivalence to a 1 dimensional simplicial complex using at most p expansions? We show that the problem, which we call the erasability expansion height, is WP-complete in the natural parameter p. |
| 01.07.19 | Counting the multiplicity of an indecomposable summand | Fabian Lenzen | For a k-Algebra A, an A-module M and an indecomposable A-module L, how can we determine how often L occurs as a direct summand of M? At least if L is neither projective nor injective, this question can be answered by computing dimensions of certain Hom-spaces. We'll see how to find an explicit formula and how the objects involved are obtained. |
28.06.19 | Simple homotopy theory and the Whitehead group. Part II | Abhishek Rathod | Continuation of the talk given on 21.06.19. Plan for the talk: Define the Whitehead group of a CW complex and prove that it is indeed a well–defined abelian group. Explain the inductive procedure for simplifying a homotopically trivial CW pair to a ‘normal/simplified form’: a pair which has relative cells only in two consecutive dimensions. |
| 21.06.19 | Simple homotopy theory and the Whitehead group. Part I | Abhishek Rathod | The notion of homotopy equivalence is one of the key notions of algebraic topology. In this seminar, we will look at a combinatorial refinement of homotopy equivalence namely simple homotopy equivalence. We will ask the following fundamental question: For CW complexes, is there is a collection of elementary geometrically defined homotopy equivalences from which every homotopy equivalence is generated? The definition of simple homotopy equivalence is based on such elementary homotopy equivalences, which act as building blocks. Plan for the talk: Introduce the definitions for CW complexes, mapping cylinder, elementary expansion, elementary collapse, and simple homotopy equivalence. Give some examples and explain some basic properties of the simple-homotopy equivalence relation. |
| 11.6.2019 | Master's thesis: Homotopy fiber sequences in model categories | Johannes Luff | In this thesis we study how long exact sequences in abstract homotopy theory (including classical algebraic topology as well as homological algebra) arise from the study of homotopy pullback squares in Quillen model categories. We shall see how stable homotopy theory arises naturally from this perspective. |
| 10.04.19 | Multiparameter interleaving distance is NP-hard | Håvard Bakke Bjerkevik | 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. |
| 03.04.19 | Practical sparsification of Rips complexes | Bernhard Brehm | Persistent homology of the Rips filtration allows to track topological features of a point cloud over scales, and is a foundational tool of topological data analysis. Unfortunately, the Rips-filtration is exponentially sized, when considered as a filtered simplicial complex. Hence, the computation of full persistence modules is impossible for all but the tiniest of datasets; when truncating the dimension of topological features, the situation becomes slightly less intractable, but still daunting for medium-sized datasets. It is possible to approximate the Rips-filtration by a much smaller and sparser simplicial complex (linear-sized for intrinsically low dimensional spaces). However, possibly due to the complexity of existing approaches, this has not yet become part of the standard toolbox of practitioners. We propose a different sparsification scheme, based on cover-trees, that is easy to implement, while giving similar guarantees on the computational scaling. We further propose a visualization that is adapted to approximate persistence diagrams, by incorporating a variant of error bars and keeping track of all approximation guarantees, explicitly. Numerical tests indicate that the new approach outperforms the previous one, both in achieved sparsification rate, and in runtime of compared implementations. |
| 02.04.19 | Evolution of the homology and related geometric properties of the Eden Growth Model. | Erika Berenice Roldan Roa | 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. |
| 22.03.19 | Filtered Chain Complexes: Decomposition and Algorithm | Barbara Giunti | 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. |
| 22.03.19 | Nerve Theorem for Closed Balls. Part II | Fabian Roll | Continuation of the talk given on 11.01.19. |
| 15.02.19 | The evolution of random simplicial complexes | Andrew Newman | 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. |
| 11.01.19 | Nerve Theorem for Closed Balls. Part I | Fabian Roll | 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. |
| 21.12.18 | Hardness of Approximation for Morse Matching | Abhishek Rathod | 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. |
| 07.12.18 | Decomposition of Persistence Modules. Part III | Fabian Lenzen | 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. |
06.12.18 | Decomposition of Persistence Modules. Part II | Fabian Lenzen | |
| 30.11.18 | Decomposition of Persistence Modules. Part I | Fabian Lenzen | |
| 23.11.18 | Computation and Clearing | Maximilian Schmahl | Continuation of the talk give on 26.10.18. |
| 16.11.18 | Reconstructing metric graphs from trajectories | Erik Rybakken | -- |
| 26.10.18 | Computing Image Persistent (Co)homology | Maximilian Schmahl | 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. |
| 5.10.18 | Object Pose Estimation with PointNet | Michael Haberl | 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. |
| 30.5.18 | Audio fingerprinting: the mathematics of Shazam | Magdalena Reich (TUM) | |
| 15.5.18 14:15 | Solving x’=?. | Konstantin Mischaikow (Rutgers University) | 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. |
| 27.4.18 13:05 | Decomposition of persistence modules: A fast approach | Magnus Botnan (TUM) | 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. |
| 23.4.18 14:15 | Decoding of neural data using cohomological learning | Erik Rybakken (NTNU Norway) | 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. |
| 20.4.18 | Magnitude meets persistence. Homology theories for filtered simplicial sets | Nina Otter (Oxford University) | 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 https://arxiv.org/abs/1711.00802. |
29.3.18 11:00 | The Higher-Dimensional Skeletonization Problem | Sara Kalisnik (MPI Leipzig) | 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. |
| 15.2.18 14:15 | The Matroid of Barcodes: Combinatorial Foundations in TDA | Greg Henselman (Princeton University) | 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. |
| 15.12.17 | Hardness of approximation for Morse matching | Abhishek Rathod (TU Munich) | 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. |
| 30.11.17 | Computational Complexity of the Interleaving Distance | Magnus Bakke Botnan (TUM) | The interleaving distance is arguably the most prominent distance measure in topological data analysis. In this paper, we provide bounds on the computational complexity of determining the interleaving distance in several settings. We show that the interleaving distance is NP-hard to compute for persistence modules valued in the category of vector spaces. In the specific setting of multidimensional persistent homology we show that the problem is at least as hard as a matrix invertibility problem. Furthermore, this allows us to conclude that the interleaving distance of interval decomposable modules depends on the characteristic of the field. Persistence modules valued in the category of sets are also studied. As a corollary, we obtain that the isomorphism problem for Reeb graphs is graph isomorphism complete. |
| 23.11.17 | From Reeb graphs to merge trees and back to contour trees (part 2) | Benedikt Fluhr (TUM) | 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. |
| 16.11.17 13:00 | From Reeb graphs to merge trees and back to contour trees (part 1) | Benedikt Fluhr (TUM) | |
| 27.7.17 | Filtered Covers | Morten Brun (University of Bergen): | 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. |
| 6.7.17 11:00 | The Reeb graph edit distance is universal | Ulrich Bauer (TU Munich) | 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. |
| 19.6.17 | A brief summary of my research | Magnus Bakke Botnan (TU Munich) | |
| 8.6.17 | An output sensitive algorithm for computing persistent homology using Discrete Morse theory (part 2) | Abhishek Rathod (TU Munich) | |
| 1.6.17 | An output sensitive algorithm for computing persistent homology using Discrete Morse theory (part 1) | Abhishek Rathod (TU Munich) | |
| 23.5.17 | A theoretical framework for the analysis of Mapper | Mathieu Carrière (INRIA, France) | 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. |
| 18.5.17 | Persistent Betti Numbers of Random Simplicial Complexes | Florian Pausinger (TU Munich) | Some recent results on persistent Betti numbers. |
| 9.2.17 | Vision-based approaches for robust real-time tracking via energy minimization | Benjamin Busam (TUM/Framos) | |
| 7.2.17 | Persistent homology for data: stability and statistical properties | Frederic Chazal (INRIA, France) | 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. |
| 3.2.17 | Generalized interleaving on posets | Magnus Botnan | 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). |
| 9.1.17 16:00 | Tenure track status talk | Ulrich Bauer | I'll give a survey about my recent research at TUM. |
| 15.12.16 | Interval Decomposition of Infinite Zigzag Persistence Modules | Magnus Botnan | I'll give an elementary introduction to the decomposition of representations of (infinite) linear quivers. |
| 8.12.16 | An introduction to the representation theory of Lie-type groups | Frank Himstedt (TUM) | |
| 10.11.16 | On the Connectivity Threshold of Achlioptas Processes | Konstantinos Panagiotou (LMU) | |
| 3.11.16 | Approximation Algorithms for Morse Matching | Abhishek Rathod | |
| 27.10.16 | Implementing Vietoris–Rips cohomology | Ulrich Bauer | |
| 7.10.16 | Persistent connections | Ulrich Bauer | 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. |
| 5.7.16 | Reducing Complexes in Multidimensional Persistence | Claudia Landi (University of Modena and Reggio Emilia) | 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. |
| 21.6.16 | Alexandrov spaces and topological data analysis | Fernando Galaz-Garcia (Karlsruhe Institute of Technology) | 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. |
| 31.5.16 | Simply connected 2-stratifolds | José Carlos Gómez Larrañaga (CIMAT) | 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. |
| 18.5.16 12:45–14:00 | Auslander–Reiten Theory | Johan Steen (NTNU / U Stuttgart) | 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. |
| 10.5.16 | Persistent Betti Numbers of Random Simplicial Complexes | Florian Pausinger (TU Munich) | Some recent results on persistent Betti numbers. |
| 3.5.16 | Morse Theory of Geometric Filtrations | Ulrich Bauer (TU Munich) | A summary of http://arxiv.org/abs/1312.1231 |
| 29.4.16 14:15 | The Geodesic Flow on Hadamard Spaces and CAT(0) Spaces | Andreas Sühling (U Münster) | 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. |