Applied and Combinatorial Topology

I will discuss the interplay between geometry and topology, and between Morse theory and persistent homology, in the setting of geometric complexes. This concerns constructions like Rips, Čech, Delaunay, and Wrap complexes, which are fundamental construction in topological data analysis. The tandem of Morse theory and homology shows the topological equivalence of several of these constructions, helps in speeding up their computation by a huge factor (in the software Ripser), reveals thresholds at which homology necessarily vanishes (with links to a classical result by Rips and Gromov), and relates optimal representative cycles for persistent homology to the industry-tested Wrap reconstruction algorithm.

Morse theory and its discrete version are well established toolboxes in pure topology. They both serve a similar purpose: use the combinatorics of the real numbers via well-behaved real-valued functions to compute topological invariants of geometric objects. In some instances, certain collections of topological invariants allow for a complete classification of the given class of spaces, which in turn might allow for a reconstruction of the original objects from the computed collection of invariants, most time up to some suitable notion of equivalence. In this talk, I will give a brief overview over smooth and discrete Morse theory and mention some classification results in topology as well as solutions to inverse problems in TDA.

Multiparameter persistent homology is a generalization of persistent homology that allows for more than a single filtration function. Such constructions arise naturally when considering data with outliers or variations in density, time-varying data, or functional data. Even though its algebraic roots are substantially more complicated, several new invariants have been proposed recently. In this talk, I will go over such invariants, as well as their stability, vectorizations and implementations in statistical machine learning.

In topological data analysis, zigzag persistence has become an important component because it enhances the applicability of persistence theory by allowing both insertions and deletions of simplices in a simplicial filtration. Such filtrations occur in applications where a space or a function on it changes over time. For example, in network analysis, new connections appear and existing connections disappear over time. The standard persistence algorithm for non-zigzag filtrations does not work for the zigzag case. After laying out the background and earlier work on computations of zigzag persistence, we present a new algorithm FastZigzag for computing zigzag persistence from an input filtration. We follow it with the discussion of the well known vineyard problem in the zigzag case. We present a recent efficient algorithm for computing the zigzag vineyard. Akin to the non-zigzag case, the special but important case of graphs allow certain optimizations that make the computations of zigzag barcode and their vineyards more efficient. We go over some of these developments. Finally, we indicate some of the applications of zigzag persistence, in particular to data analysis in TDA with multiparameter persistence.

Hypergraphs are a natural data structure to consider when studying networks with multiway connections. One approach to characterizing the features of these networks involves defining a form of hypergraph homology and then leveraging these homological traits to delineate the hypergraphs. There are many different ways however to define hypergraph homology and different approaches yield different types of features. In this talk I will present two different approaches to this problem and then connect them by presenting a persistence module they both live inside of.

Periodic data is abundant in material science, for example the atoms of a crystalline material repeat periodically. Additionally, periodic boundary conditions are used in many further applications, for example in cosmology, to remove boundary effects. It is unclear how to deal with the periodicity of the data when computing topological descriptors, like the merge tree or persistent homology. A classical approach is to compute the respective descriptor simply on the torus. However, this does not give the information needed for many applications and is in some sense even unstable under noise. Therefore, we suggest decorating the periodic merge tree gained from the torus with additional information, describing for each connected component how many components of the infinite periodic covering space map to it. The resulting periodic merge tree carries the desired information and fulfills all the desired properties, in particular: stability and efficient computability.

Given a probability distribution $F$ on ${ℝ}^d$ with density $f$, consider a sample $X_n$ of $n$ points sampled from $F$ i.i.d.. We study the Euler characteristic curve (ECC) of the union of balls $\bigcup _{x\in X_n}{\overline{B}}_{r_n}(x)$ in the thermodynamic limit. That is, as $n\to \mathrm{\infty }$, we let $r_n\to 0$ such that $n{r}_n^d$ approaches a finite, non-zero limit. It turns out that two distributions yield the same expected ECC in this setting if and only if they have the same excess mass. Whether this condition is also necessary for the distributions of the ECCs to coincide in the limit remains an open question.

In this talk, I will present some of our ongoing work on visual analysis and comparison of electronic structures in molecules or crystals based on topological analysis. The application context is to develop novel materials with some desired properties by simulating material configurations from a large number of possible candidates. Our aim is to characterize such materials based on their electronic structure, represented by their electron density fields. Therefore, we have experimented with various multiscale descriptors that support quantitative and visual comparative analysis to help scientists better understand the differences in their structures through visual exploration guided by automatic analyzes such as outlier detection, clustering, and similar structure searches.

Magnitude is an isometric invariant for metric spaces that was introduced by Leinster around 2010, and is currently the object of intense research, since it has been shown to encode many known invariants of metric spaces. In recent work, Govc and Hepworth introduced persistent magnitude, a numerical invariant of a filtered simplicial complex associated to a metric space. Inspired by Govc and Hepworth’s definition, we introduced alpha magnitude. Alpha magnitude presents computational advantages over both magnitude as well as Rips magnitude, and is thus an easily computable new measure for the estimation of fractal dimensions of real-world data sets.

We introduce graphcodes, a novel multi-scale summary of the topological properties of a data set that is based on the well-established theory of persistent homology. Graphcodes handle data sets that are filtered along two real-valued scale parameters. Such multi-parameter topological summaries are usually based on complicated theoretical foundations and difficult to compute; in contrast, graphcodes yield an informative and interpretable summary and can be computed as efficient as one-parameter summaries. Moreover, a graphcode is simply an embedded graph and can therefore be readily integrated in machine learning pipelines using graph neural networks. We describe such a pipeline and demonstrate that on data sets with rich topological features, graphcodes achieve better classification accuracy than state-of-the-art approaches.

In topological data analysis, the rank invariant is one of the best known invariants of persistence modules over posets. The rank invariant of a persistence module M over a given poset P is defined as the map that sends each comparable pair $p\le q$ in P to the rank of the linear map $M(p\le q)$. The recently introduced notion of generalized rank invariant acquires more discriminating power than the rank invariant at the expense of enlarging the domain of rank invariant to a collection I of intervals of $P$ that contains all segments of $P$. In this talk, we discuss the tension that exists between computational efficiency and the discriminating power of the generalized rank invariant, depending on its domain $I$. The Möbius inversion formula will assume a significant role in clarifying the discriminating power, even in cases where the domain $I$ is not locally finite. Along the way, we show that the possibility of encoding the generalized rank invariant of $M$ over a non-locally-finite $I$ into a multiset of signed intervals of $P$ depends on how “tame” $M$ is. Such a multiset, if it exists, is obtained via Möbius inversion of the generalized rank invariant over a suitable locally finite subset of $I$.

Intending to introduce a method for the topological analysis of fields, we present a pipeline that takes as an input a weighted and based chain complex, produces a tame epimorphic parametrized chain complex, and encodes it as a barcode of tagged intervals. We show how to apply this pipeline to the weighted and based chain complex of a gradient-like Morse-Smale vector field on a compact Riemannian manifold in both the smooth and discrete settings. Interestingly for computations, it turns out that there is an isometry between tame epimorphic parametrized chain complexes endowed with the interleaving distance and barcodes of tagged intervals endowed with the bottleneck distance. Concerning stability, we show that the map taking a generic enough gradient-like vector field to its barcode of tagged intervals is continuous. Finally, we prove that the barcode of any such vector field can be approximated by the barcode of a combinatorial version of it with arbitrary precision.

In the last years, research in persistent homology has started to focus on multi-parameter persistent homology, which studies the homology of a space filtered by multiple parameters independently. For example, this can be used to overcome the notorious susceptibility of persistent homology to outliers, to deal with data sats of inhomogeneous density, or to study filtration types that rely on more than one parameter.

Computing multi-parameter persistent homology is challenging, both algebraically and algorithmically. In particular, current software is orders of magnitudes slower than common software for one-parameter persistence.

We will discover why persistent cohomology – a key ingredient in the efficiency of one-parameter persistence software – is inherently more difficult in multi-parameter persistence, how this is dealt with in the software package 2pac, and what problems still remain.

We study the size of Sheehy’s subdivision bifiltrations, up to homotopy. We focus in particular on the subdivision-Rips bifiltration $𝒮ℛ$, the only density-sensitive bifiltration on metric spaces known to satisfy a strong robustness property. Given a simplicial filtration $ℱ$ with a total of $m$ maximal simplices across all indices, we introduce a simplicial model for its subdivision bifiltration $𝒮ℱ$ whose $k$-skeleton has size $O(m^{k+1})$. We also show that the $0$-skeleton of any simplicial model of $𝒮ℱ$ has size at least $m$. We give several applications: For arbitrary metric spaces, we introduce a $\sqrt{2}$-approximation to $𝒮ℛ$ with poly-size skeleta, improving on the previous best approximation bound of $\sqrt{3}$. Moreover, we show that the approximation factor of $\sqrt{2}$ is tight; in particular, there exists no exact model of $𝒮ℛ$ with poly-size skeleta. On the other hand, we show that for data in a fixed-dimensional Euclidean space with the ${\mathrm{\ell }}_p$-metric, there exists an exact model of $𝒮ℛ$ with poly-size skeleta for $p\in \{1,\mathrm{\infty }\}$, as well as a $(1+ϵ)$-approximation to $𝒮ℛ$ with poly-size skeleta for any $p\in (1,\mathrm{\infty })$ and fixed $ϵ>0$.

Let $G=(V,E)$ be a finite simple graph. A classical result of Erdos and Gallai asserts that if $|E|>\frac{k(|V|-1)}{2}$, then $G$ contains a simple cycle of length $>k$. We study the analogous question for higher dimensional simplicial complexes. A set $\{{\sigma }_1,\mathrm{\dots },{\sigma }_k\}$ of $d$-dimensional simplices in a simplicial complex $X$ is a simple $d$-cycle over a field $F$ if $\{\partial {\sigma }_1,\mathrm{\dots },\partial {\sigma }_k\}$ is a minimal linearly dependent set in the space of $d$-chains $C_d(X;F)$. Let $f_i(X)$ denote the number of $i$-dimensional simplices in $X$. It is shown that any $d$-dimensional $X$ contains a simple $d$-cycle of size

Data consisting of a graph with a function to ${ℝ}^d$ arise in many data applications, encompassing structures such as Reeb graphs, geometric graphs, and knot embeddings. As such, the ability to compare and cluster such objects is required in a data analysis pipeline, leading to a need for distances or metrics between them. In this work, we study the interleaving distance on discretizations of these objects, ${ℝ}^d$-mapper graphs, where functor representations of the data can be compared by finding pairs of natural transformations between them. However, in many cases, computation of the interleaving distance is NP-hard. For this reason, we take inspiration from the work of Robinson to find quality measures for families of maps that do not rise to the level of a natural transformation, called assignments. We then endow the functor images with the extra structure of a metric space and define a loss function which measures how far an assignment is from making the required diagrams of an interleaving commute. Finally we show that the computation of the loss function is polynomial. We believe this idea is both powerful and translatable, with the potential to be used for approximation and bounds on interleavings in a broad array of contexts.

I will describe recent work with Curry, Mio, Okutan and Russold which fuses graphical and persistence invariants of datasets. The basic idea is to attribute the nodes of a Reeb or Mapper graph of a dataset with persistence diagrams, which encode localized, higher-dimensional homological features of the data. These enriched graphical summaries can be used, for example, as inputs to a graph neural network for shape classification tasks. I will also discuss the (fairly subtle) theoretical stability properties of these invariants.

An important class of Higher Dimensional Automata (HDA) in concurrency theory arises from semaphore protocols or PV-programs originally described by Dijkstra. In order to understand their behaviour, one must analyse the space of all schedules (directed paths) between (any) start and end state. How can one translate the orders of lock and unlock commands into a recipe describing this space?

By definition, the space of allowed directed paths is an intersection (limit) of elementary spaces – each having the homotopy type of a sphere – in the infinite-dimensional space of all directed paths. There is a homotopy equivalence embedding the (allowed) paths as a configuration space into a finite-dimensional sphere. The complement of this configuration space in that sphere is a union (colimit) of elementary spaces. Its topology can therefore be described as the homotopy colimit of certain spaces for which we have a “low-dimensional” description arising directly from the PV-encoding. In favourable cases, this homotopy colimit can be described explicitly. Alexander duality allows then to determine the homology of the complement, and hence of the space of all allowed directed paths.

A large driver contributing to the success of deep learning models is their ability to synthesise task-specific features from data. For a long time, the predominant belief was that ‘given enough data, all features can be learned.’ However, it turns out that certain tasks require imbuing models with inductive biases such as invariances that cannot be readily gleaned from the data! This is particularly true for data sets that model real-world phenomena, creating a crucial need for different approaches. This talk will present novel advances in harnessing multi-scale geometrical and topological characteristics of data. I will particularly focus on how geometry and topology can improve (un)supervised representation learning tasks. Underscoring the generality of a hybrid geometrical-topological perspective, I will furthermore showcase applications from a diverse set of data domains, including point clouds, graphs, and higher-order combinatorial complexes.

This Overview of Discrete Morse Theory is two-fold.

In the first part, we give an introduction to the basic concepts of Discrete Morse Theory. In particular, we discuss the equivalence of simplicial collapses, acyclic matchings, and poset maps with small fibers. We then define the Morse complex that computes simplicial homology and consider examples.

In the second part, we discuss open problems as well as newer directions of research. We will look at open problems in both random Discrete Morse Theory and the complex of discrete Morse functions. We will then survey several variations of Discrete Morse Theory, inluding stratified and Bestvina-Brady, which may prove useful in simplifying a complex.

Phylogenetic networks are vital for understanding complex evolutionary processes, where traditional tree-like structures fall short. The application of topological data analysis (TDA) has emerged as a powerful approach for exploring such networks, revealing underlying geometric and topological structures. This talk focuses on a lattice theoretical approach of representing such networks and relating them to TDA. We will discuss the applications of TDA techniques in analyzing phylogenetic networks, aiming to uncover hidden patterns and gain deeper insights into their evolutionary dynamics. Additionally, we introduce the facegram, a simplicial lattice model that generalizes the dendrogram model for phylogenetic trees, which enables an alternative way to visualize filtrations of complexes, and show some more recent applications of these ideas and connections.

A Reeb graph is a graphical representation of a scalar function on a topological space that encodes the topology of the level sets. Reeb graphs and their variants are popular tools in topological data analysis and visualization. As an overview talk for TDA+statistics, I will review theoretical advances in studying Reeb graphs and their variants, as well as their applications in data mining and machine learning.

From a theoretical perspective, the questions surrounding Reeb graphs are as follows.

• $\mathrm{■}$

  Comparative analysis: What is a reasonable distance or similarity measure between a pair of Reeb graphs? Desirable properties of a distance/measure is for it to be a metric or pseudometric, discriminative, and easy to compute (both in terms of computational complexity and practical implementation). See Yan et al. (2021) [35] and Bollen et al. (2022) [9] for surveys.

• $\mathrm{■}$

  Stability: How stable is a Reeb graph w.r.t. simplification or perturbation of the underlying function?

• $\mathrm{■}$

  Information content: What information is encoded by the Reeb graph? How much information can we recover about the original data from the Reeb graph by solving an inverse problem?

The questions surrounding mapper graphs (discrete approximations of Reeb graphs) include comparative analysis, information content, and additionally:

• $\mathrm{■}$

  Stability: What is the structural stability of the mapper with respect to perturbations of its function, domain and cover?

• $\mathrm{■}$

  Convergence: What is an appropriate metric under which the mapper converges to the Reeb graph as the number of sampled points goes to infinity and the granularity of the cover goes to zero?

• $\mathrm{■}$

  Parameter tuning: How to effectively and automatically tune the parameters that best capture the topology of the underlying data?

Reeb graphs have many variants, including:

• $\mathrm{■}$

  Mapper construction/mapper graph: Singh et al. (2007) [33].

• $\mathrm{■}$

  $\alpha$-Reeb graph that considers the cover of range space with open intervals of length at most $\alpha$, see Chazal and Sun (2014) [17].

• $\mathrm{■}$

  Multiscale mapper considers a hierarchical family of covers and the maps between them, see Dey et al. (2016) [18].

• $\mathrm{■}$

  Multinerve mapper computes the multinerve of a connected cover, see Carriere and Oudot (2018) [15].

• $\mathrm{■}$

  Joint Contour Net (JCN) works with a piecewise linear (PL) mapping over a simplicial mesh with multiple real-valued functions, see Carr and Duke (2013) [14] and Geng et al. (2014) [22].

• $\mathrm{■}$

  Extended Reeb graph uses cover elements from a partition of the domain without overlaps, see Barral and Biasotti (2014) [4].

• $\mathrm{■}$

  Enhanced mapper graph considers additionally the inverse map of intersections among cover elements, see Brown et al. (2021) [10].

• $\mathrm{■}$

  Ball mapper that may not require a filter function, see Dłotko (2019) [20].

Reeb graphs and their variants, in particular, mapper graphs, have seen many applications in topological data analysis and visualization. They have been used for shape skeletonization (Pascucci et al., 2007) [29] and symmetry detection (Thomas and Natarajan 2011) [34]. They have recently been utilized to study artificial neuron activations in deep learning, see the works by Purvine et al. (2023) [30], and Rathore et al. (2021, 2023) [31, 32]. For applications in visualization, see Yan et al. (2021) [35] for a survey.

One-dimensional persistent homology is arguably the most important and heavily used computational tool in topological data analysis. Additional information can be extracted from datasets by studying multi-dimensional persistence modules and by utilizing cohomological ideas, e.g. the cohomological cup product. In this work, given a single parameter filtration, we investigate a certain 2-dimensional persistence module structure associated with persistent cohomology, where one parameter is the cup-length and the other is the filtration parameter. This new persistence structure, called the persistent cup module, is induced by the cohomological cup product and adapted to the persistence setting. Furthermore, we show that this persistence structure is stable. By fixing the cup-length parameter, we obtain a 1-dimensional persistence module and again show it is stable in the interleaving distance sense, and study their associated generalized persistence diagrams.

In this example of a reduced matrix, $\sigma$ is a negative simplex, because it kills the cycle $({\tau }_1+{\tau }_2+{\tau }_3)$. The representative of a bar can be read off from the column of the corresponding negative simplex: In this case it would be $({\tau }_1+{\tau }_2+{\tau }_3)$. Similarly, the representatives of infinite bars can be read off from the columns of the matrix $V$. The reduced matrix $R$ and the matrix $V$, and hence the representatives, can be computed in $𝒪(m^3)$ time. On the other hand, the persistence pairing (in other words, the pivot positions of the reduced matrix) can be computed even in matrix multiplication time $𝒪(m^{\omega })$, with , for classical persistent homology and even for zigzag persistent homology. The question is whether this holds only for the computation of the persistence pairs, or also for the computations of their representatives.

Questions:

1. 1.

   Compute homological representative cycles for all bars in time where $m$ is the size of the input filtration?

2. 2.

   Zigzag in or $𝒪(m^3)$ or even time?

Reference to “Zigzag Persistent Homology in Matrix Multiplication Time”, Milosavljević, Nikola and Morozov, Dmitriy and Skraba, Primoz, Proceedings of the twenty-seventh Annual Symposium on Computational Geometry, 216–225, 2011. https://www.mrzv.org/publications/zzph-mmt/socg11/

During this Dagstuhl Seminar, this question has been investigated by the working group on algorithms.

Tamal’s comment: The above problem is not open anymore. It turns out that the algorithm in the paper mentioned above can be utilized to compute a representative for standard persistence in $O(m^{\omega })$ time. The authors of the paper exchanged notes through email which have convinced us that indeed the algorithm can be adapted to compute the representatives in the stated time. For zigzag, it is not clear if the algorithm can be adapted straightforwardly to do the same. However, the proposer of the problem with his students has gotten an algorithm which can compute the representatives in $O(m^3)$ time. Interested people may contact the proposer to have a preprint. The paper is currently under some revision which is planned to be submitted for publication in a near future. The question of computing the representatives for zigzag in less than cubic time remains open. It is not entirely clear if it can be done at all because there is no bound better than cubic known for the output size in this case.

Base DM (Discrete Morse) Graph Reconstruction algorithm (see e.g., [19])
Input: Triangulation $K$ of domain $I\subset {ℝ}^d$, function $f:K\to ℝ$, threshold $\delta$

• $\mathrm{■}$

  Step 1: persistence computation

• $\mathrm{■}$

  Step 2: persistence-guided Morse simplification.

  • –

    Spanning forest construction based on persistence output

  • –

    retrieval of 1-stable manifold based on spanning forest for critical edges with persistence larger than $\delta$

The above algorithm is already known. However, in practical applications, we often need to have additional constraints as input to the above graph reconstruction algorithm. For example, in neural bundle reconstruction from 3D images, we may want to add constraints that there are desired “flow directions” at certain locations. These flow directions could have been computed locally based on computer vision-based approaches. Hence, the high level problem we aim to solve is a discrete Morse based graph reconstruction with additional constraints. As a first step, we encode the “flow direction” constraints simply as a set of discrete gradient vectors. More precise, see the following description:

Input:

• $\mathrm{■}$

  a simplicial complex $K$ with vertices $V=V(K)$

• $\mathrm{■}$

  a function $f:V\to ℝ$

• $\mathrm{■}$

  collection of pairs $P=\{(\sigma ,\tau )|\sigma \subset \tau ,|\tau |=|\sigma |+1\}$, indicating desirable “gradient vectors”

Goal:

1. 1.

   What would be a good way to define an “optimal” discrete gradient vector field (or a (generalized) discrete Morse function) that combine both types of input

2. 2.

   In particular, what theoretical properties can we provide (including properties of the graph reconstructed using the earlier algorithms)

Idea:
convex polytope solution (together with Linear / Quadratic Programming); space of morse functions and hyperplanes

During this Dagstuhl Seminar, this question has been investigated by the working group on algorithms.

Algorithm:

Let $P$ and $Q$ be permutations such that $PM$ and $QM$ have rows in lexicographic and colexicographic order w.r.t. $\mathrm{\ell }$.

1. 1.

   Compute $V^{\prime }$ such that $PM{V}^{\prime }$ is reduced

2. 2.

   Order columns of $PM{V}^{\prime }$ by pivot

3. 3.

   Compute upper triangular $V^{\prime \prime }$ such that $QM{V}^{\prime }{V}^{\prime \prime }$ is reduced.

With $V=V^{\prime }{V}^{\prime \prime }$, the ordering of the columns in step 2 ensures that afterwards, both $PMV$ and $QMV$ are reduced. See the paper for a proof that this minimizes all $\mathrm{\ell }(M{V}_j)$.

Problem:

If $M$ is a coboundary matrix of a two-parameter function-Rips filtration, the algorithm produces tremendous fill-in in step 3: Out of millions of columns, there are often 1–10 columns that for which 50–90% of the entries are non-zero.

Question:

Can we devise an algorithm that (in most cases) does not produce fill-in?

Motivation:

Fill-in in only a few columns is currently a central bottleneck in computing Vietoris–Rips persistent cohomology. The above task can be seen as a two-parameter generalization of the clearing-idea. Experiments show that fill-in is an even worse problem in two-parameter persistence. Solving this problem would be a major step towards efficient algorithms for multi-parameter persistence.

Besides, Uli also mentioned that matrix fill-in is a central bottleneck in computing image persistence.

Manifold reconstruction guarantees for the method described in the talk (exhaustive reduction method for most persistent top dimensional cycle). Note that the exhaustive reduction algorithm gives the lexicographically minimal cycle representative.

• $\mathrm{■}$

  As a motivation, we considered a visualization of the exhaustive reduction method (eliminate all entries that can be eliminated, not only the lowest ones).

• $\mathrm{■}$

  The reduction starts with one $d$-simplex (in ${ℝ}^d$) and its boundary, and you add more until you reach the reduced cycle.

Under which sampling conditions can we guarantee that this lexicographically minimal cycle reconstructs the manifold? And does it always make sense to take the most persistent top-dimensional cycle? If the manifold has multiple components, we would need one cycle for each component.

As a first step, we would need to investigate: What methods do people use to prove such results?

Let $X$ be a topological space equipped with a pair of functions, $f,g:X\to ℝ$. We first utilize the function $f$ (resp., $g$) to obtain a 1-parameter topological descriptor, denoted as $P(X,f)$ (resp., $P(X,g)$). We then use both $f$ and $g$ to construct a 2-parameter topological descriptor, denoted as $P(X,f,g)$. For example, if $P(X,f)$ is a Reeb graph, then $P(X,f,g)$ is a Reeb space. Alternatively, $P(X,f)$ and $P(X,f,g)$ are 1- and $2$-parameter persistence modules, respectively. We ask the following question: how do we quantify the information gain from a 1-dimensional topological descriptor $P(X,f)$ to a 2-dimensional topological descriptor $P(X,f,g)$?

This problem first appeared in the work of Zhou et al. [37], where the authors investigated a method for stitching a pair of 1-parameter mappers together into a 2-parameter mapper, quantified and visualized topological notions of information gains during such a process. While the work in [37] provides some initial thoughts on this problem, including graph entropy, fiber-wise homology and Euler characteristics, it leaves much to be desired.

During this Dagstuhl Seminar, this question has been investigated by a working group studying topological information gain.

In complexity theory, a classical problem is the so-called planted clique problem. Given natural numbers $n$ and $k$, the planted clique problem uses the following procedure:

1. 1.

   Create an Erdős–Rényi graph $G$ on $n$ vertices with edge creation probability $p=0.5$.

2. 2.

   With probability $0.5$, select a subset of $k$ vertices in $G$ and turn them into a $k$-clique.

3. 3.

   Return $G$.

Given $G$, the goal is now to detect whether a clique has been planted or not. The planted clique problem is most interesting – and hard – for a specific range of $k$, viz.

My open question is whether topological descriptors can detect planted cliques in the distributional sense, for instance via persistence landscapes, calculated from an appropriately-selected filtration. (See the working groups section below for the preliminary results).

In complexity theory, a classical problem is the so-called planted clique problem. Given natural numbers $n$ and $k$, the planted clique problem uses the following procedure:

1. 1.

   Create an Erdős–Rényi graph $G$ on $n$ vertices with edge creation probability $p=0.5$.

2. 2.

   With probability $0.5$, select a subset of $k$ vertices in $G$ and turn them into a $k$-clique.

3. 3.

   Return $G$.

Given $G$, the goal is now to detect whether a clique has been planted or not. The planted clique problem is most interesting – and hard – for a specific range of $k$, viz.

My open question is whether topological descriptors can detect planted cliques in the distributional sense, for instance via persistence landscapes, calculated from an appropriately-selected filtration. (See the working groups section below for the preliminary results).

This group worked on a basic problem in the theory of metric space magnitude. Magnitude was introduced by Leinster and its fundamental properties are worked out in [26, 25]. The notation and initial exposition below follow [25].