The seminar usually takes place on Tuesday 10-12 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 Fabian Roll.



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.

We introduce a cohomological algorithm for computing minimal free resolutions of two-parameter ph that allows for clearing. To derive our algorithm, we extend the duality principles which underlie the one-parameter approach to the two-parameter setting. We provide an implementation and report experimental run times for function-Rips filtrations. Our method is faster than the current state-of-the-art by a factor of up to 20.


Ripser: efficient computation of Vietoris-Rips persistence barcodes

Ulrich Bauer

Continuation of the talk from 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.


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

10:00 CEST

Applications of Topological Data Analysis in Mesoscale Eddy tracking

Jacob Skarby


Interval decomposition and coarse graining

Rojyar Rajabpour


9:15 CET

The spectrum of the real line

Jan-Paul Lerch

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.2022Intersection homology and singularities in data

Julius von Rohrscheidt

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 14:00 CETGet-together: Discussing ATMCS10



Categorification of Extended Persistence Diagrams



Benedikt Fluhr

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. 


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 10:00 CET

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.


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.
Generalizing persistent homology to a multivariate setting allows for the extraction of finer information from data, but its algebraic properties are more subtle. In this talk, I discuss the shift-dimension, a stable invariant of multipersistence modules which is obtained as the hierarchical stabilization of a classical invariant. This talk is based on recent work with Wojciech Chachólski and René Corbet.


Master 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.


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.

Thu 23.12.2021
14:00 CET

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.


The degree-Rips complexes of an annulus with outliers

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.


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.


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.2021Output-sensitive algorithms for computing persistenceAbhishek RathodIt 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.2021Master's thesis: An explicit Construction for Derived Persistence Anton Loumakos

Relative interlevel set homology with respect to a piecewise linear function was
proposed as an extension to the prior constructions
of extended persistence homology and the Mayer-Vietoris Pyramid, along with an
adjusted definition of the extended persistence diagram. The dual construction
that is relative interlevel set cohomology is introduced by the same authors, now
for any continuous function, however under certain finiteness conditions. In this
thesis, we imitate these structures to build a parametrization on a subposet of
the real plane for a filtration of the cone of a simplicial complex and then
proceed to showcase an explicit construction of a complex of sheaves with finite derived
persistence diagram.

04.10.2021Discrete Morse theory and Vietoris-Rips complexes of metric gluingsFabian 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.

[1] M. Adamaszek, H. Adams, E. Gasparovic, M. Gommel, E. Purvine, R. Sazdanovic, B. Wang, Y. Wang, L. Ziegelmeier, On homotopy types of Vietoris–Rips complexes of metric gluings, J Appl. and Comput. Topology. 4 (2020) 425–454.

[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.

19.08.21The Shape of Vision Decoding: the Primary Visual Cortex with HomologyLoek van Rossem

We study the topology of the primary visual cortex’s
neuronal code in response to image gratings, which are given by
sinusoidal functions. To do so, we apply topological data analysis, a
technique for which we give a brief conceptual overview. Topologies of
different grating image subspaces are investigated, which allows for
predictions on their respective neural codes. A simulation of simple
cells is performed to verify these results. Using information gained
about the topology, decodings are found without the use of image
labelings. In particular, we introduce a novel technique to decode the
orientation/phase subspace, which has the topology of a Klein bottle.


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.
Several concepts introduced by Morse in this context can be seen as early precursors to the theory of persistent homology, which by now has established itself as a popular tool in applied and theoretical mathematics.
We provide a modern redevelopment of the homological aspects of Morse's functional topology from the perspective of persistence theory. We adjust several key definitions and prove stronger statements, including a generalized version of the Morse inequalities, in order to allow for novel uses of persistence techniques in functional analysis and symplectic geometry.
As an application, we identify and correct a mistake in the proof of the Unstable Minimal Surface Theorem by Morse and Tompkins.

11.08.21Bachelor's thesis: Homological Algebra in Puppe-exact CategoriesMarkus 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.


The fiber of Persistent Homology for Simplicial Complexes

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.


L²-Betti numbers and profinite completions of groups , notes

Nico Stucki


12.04.21Power Operations in Higher Semiadditive CategoriesJan 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, 21:00 CET
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.
This is joint work with Abraham Smith and John Harer.

08.03.21Introduction to Spectral SequencesFabian RollThis 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.21Computing persistent homology: A Morse theory updateAbhishek 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.21Topological Expressive Power of Neural NetworksAntónio LeitãoIn 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 disksHannah AlpertConfiguration 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.21A Topological Approach to Inferring the Intrinsic Dimension of Convex Sensing DataMin-Chun WuWe 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.21Topology of Nerves, Formal Concepts and Their ApplicationsZelong 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.21Monge-Ampère equations and inverse problems in opticsBoris Thibert, Université Grenoble AlpesNon-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.20Amenable Category and ComplexityPietro CapovillaAmenable 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.

Video session:

Studying the space of persistence diagrams using optimal partial transport

First talk, Second talk

Théo Lacombe, Vincent Divol

First talk: Introduction and theoretical background

Despite the obvious similarities between the metrics used in topological data analysis and those of optimal transport, an explicit optimal transport based formalism to study persistence diagrams and similar topological descriptors has yet to come. By considering the space of persistence diagrams as a measure space, and by observing that its metrics can be expressed as optimal partial transport problems, we introduce a generalization of persistence diagrams, namely Radon measures supported on the upper half plane. Such measures naturally appear in topological data analysis when considering continuous representations of persistence diagrams (e.g. persistence surfaces) but also as expectations of probability distributions on the persistence diagrams space. This formalism allows us to prove topological properties of this new space, which will also hold for the closed subspace of persistence diagrams.

Second talk: Applications

This bridge between optimal transport and persistence diagram metrics allows us to address various problems that naturally arise when dealing with persistence diagrams, both in theory and in applications. First, we provide a characterization of convergence in the space of persistence diagrams (with respect to their standard metrics) in terms of vague convergence of measures. This result provides a powerful tool to study convergence and continuity properties in the space of persistence diagrams; in particular it allows us to give an exhaustive characterization of continuous linear representations of persistence diagrams, a common tool used when incorporating persistence diagrams in machine learning pipeline. Second, this formalism allows us to prove new results regarding persistence diagrams in a random setting, as it enables to manipulate some limit objects such as expected persistence diagrams (that are not standard persistence diagrams) and to prove convergence rates and stability results in this context.


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.20A probabilistic approach to rigidity of the curve complex

Noé Bárcenas

UNAM/Universität des Saarlandes

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.

Video session:

COVID 19, Viruses, Recombnation and Topology

Raul RabadanCOVID-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.

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.20A Short Introduction to Gröbner BasesTim ReinhardtWe 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.20k-decomposable and shellable complexesRuss 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.20Categories of fractionsAbhishek RathodIn 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.

Paramaterized inapproximability of discrete Morse theory


(Updated) Slides

Abhishek RathodIn 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.

The relative Interlevel Set Homology II

Benedikt FluhrIn 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.

The relative Interlevel Set Homology I



Benedikt Fluhr

AATRN practice talk: The fundamental group of 2-dimensional random cubical complexes


Erika Roldan RoaWe 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.

Introduction to operads II

Slides (also for talk I)

Fabian LenzenOperads 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.

Introduction to operads I

Slides (also for talk II)

Fabian Lenzen
18.06.20SoCG practice talk: Fast Algorithms for Minimum Cycle Basis and Minimum Homology BasisAbhishek RathodWe 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.20SoCG practice talk: The Reeb Graph Edit Distance Is Universal

Ulrich BauerWe 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.



The Exhaustive Reduction and Discrete Morse TheoryFabian RollIn 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.



Evolution of the homology and related geometric properties of the Eden Growth Model .Erika Roldan RoaIn 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.



Shellings from relative shellings: A simpler proof for hardness of shellabilityAbhishek RathodShellings 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.



Combinatorial models of global dynamics: learning cycling motion from dataDavid HienConley'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.



Persistent Homology and Morse’s Functional TopologyMaximilian 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.



Evolution of the homology and related geometric properties of the Eden Growth ModelErika Roldan RoaThe 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.20The chromatic number of random Borsuk graphsMatthew 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.19Double complexes as sums of indecomposablesJonas 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.19Decomposition of Algebra-modules over finite fieldsFabian LenzenLux 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.19UMAP: Uniform Manifold Approximation and ProjectionFabian 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.19An introduction to (∞,1)-categories via Segal spaces, and cobordisms

Claudia Scheimbauer

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.19Gromov-Wasserstein distances and distributional invariants of datasetsFacundo 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.19Fast 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.19Parametrized Complexity of Expansion HeightAbhishek RathodDeciding 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.

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.

Reference: Dlab, Gabriel: Representation Theory I


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.19Simple 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.

The principal question that interests us is: 'Is every homotopy equivalence between finite CW complexes simple?'
The answer turns out to be no, but in a very non-trivial way as part of a beautiful theory by Whitehead.

There is a single algebraic invariant, called the Whitehead torsion, which decides whether a homotopy equivalence is simple. The Whitehead torsion of a homotopy equivalence is an element of an abelian group, called the Whitehead group, which depends only on the fundamental group. This algebraic invariant leads to a complete answer of the question and it establishes a connection between topology and algebra.

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.2019Homotopy fiber sequences in model categoriesJohannes LuffIn 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.19Multiparameter 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.19Practical 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.19Evolution of the homology and related geometric properties of the Eden Growth Model.Erika Berenice Roldan RoaIn 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.

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.19Nerve Theorem for Closed Balls. Part II Fabian Roll Continuation of the talk given on 11.01.19.
15.02.19The 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.19Nerve 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.18Hardness 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.18Decomposition 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.


Decomposition of Persistence Modules. Part II Fabian Lenzen
30.11.18Decomposition of Persistence Modules. Part I Fabian Lenzen
23.11.18Computation and Clearing Maximilian Schmahl Continuation of the talk give on 26.10.18.

Reconstructing metric graphs from trajectories

Erik Rybakken--
26.10.18Computing Image Persistent (Co)homologyMaximilian SchmahlGiven 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.

Object Pose Estimation with PointNet

Michael HaberlWhat 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.

  • No labels