**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# Algebraic Homotopy Interleaving Distance

Abstract

The theory of persistence, which arises from topological data analysis, has been intensively studied in the one-parameter case both theoretically and in its applications. However, its extension to the multi-parameter case raises numerous difficulties, where it has been proven that no barcode-like decomposition exists. To tackle this problem, algebraic invariants have been proposed to summarize multi-parameter persistence modules, adapting classical ideas from commutative algebra and algebraic geometry to this context. Nevertheless, the crucial question of their stability has raised little attention so far, and many of the proposed invariants do not satisfy a naive form of stability. In this paper, we equip the homotopy and the derived category of multi-parameter persistence modules with an appropriate interleaving distance. We prove that resolution functors are always isometric with respect to this distance. As an application, this explains why the graded-Betti numbers of a persistence module do not satisfy a naive form of stability. This opens the door to performing homological algebra operations while keeping track of stability. We believe this approach can lead to the definition of new stable invariants for multi-parameter persistence, and to new computable lower bounds for the interleaving distance (which has been recently shown to be NP-hard to compute in [2]).

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (16)

Related publications (4)

Related MOOCs (9)

Algebraic geometry

Algebraic geometry is a branch of mathematics which classically studies zeros of multivariate polynomials. Modern algebraic geometry is based on the use of abstract algebraic techniques, mainly from commutative algebra, for solving geometrical problems about these sets of zeros. The fundamental objects of study in algebraic geometry are algebraic varieties, which are geometric manifestations of solutions of systems of polynomial equations.

Homotopy

In topology, a branch of mathematics, two continuous functions from one topological space to another are called homotopic (from ὁμός "same, similar" and τόπος "place") if one can be "continuously deformed" into the other, such a deformation being called a homotopy (həˈmɒtəpiː, ; ˈhoʊmoʊˌtoʊpiː, ) between the two functions. A notable use of homotopy is the definition of homotopy groups and cohomotopy groups, important invariants in algebraic topology. In practice, there are technical difficulties in using homotopies with certain spaces.

Commutative algebra

Commutative algebra, first known as ideal theory, is the branch of algebra that studies commutative rings, their ideals, and modules over such rings. Both algebraic geometry and algebraic number theory build on commutative algebra. Prominent examples of commutative rings include polynomial rings; rings of algebraic integers, including the ordinary integers ; and p-adic integers. Commutative algebra is the main technical tool in the local study of schemes.

In this thesis, we investigate the inverse problem of trees and barcodes from a combinatorial, geometric, probabilistic and statistical point of view.Computing the persistent homology of a merge tree yields a barcode B. Reconstructing a tree from B involves gluing the branches back together. We are able to define combinatorial equivalence classes of merge trees and barcodes that allow us to completely solve this inverse problem. A barcode can be associated with an element in the symmetric group, and the number of trees with the same barcode, the tree realization number, depends only on the permutation type. We compare these combinatorial definitions of barcodes and trees to those of phylogenetic trees, thus describing the subtle differences between these spaces. The result is a clear combinatorial distinction between the phylogenetic tree space and the merge tree space.The representation of a barcode by a permutation not only gives a formula for the tree realization number, but also opens the door to deeper connections between inverse problems in topological data analysis, group theory, and combinatorics.Based on the combinatorial classes of barcodes, we construct a stratification of the barcode space. We define coordinates that partition the space of barcodes into regions indexed by the averages and the standard deviations of birth and death times and by the permutation type of a barcode. By associating to a barcode the coordinates of its region, we define a new invariant of barcodes.These equivalence classes define a stratification of the space of barcodes with n bars where the strata are indexed by the symmetric group on n letters and its parabolic subgroups.We study the realization numbers computed from barcodes with uniform permutation type (i.e., drawn from the uniform distribution on the symmetric group) and establish a fundamental null hypothesis for this invariant. We show that the tree realization number can be used as a statistic to distinguish distributions of trees by comparing neuronal trees to random barcode distributions.

Algebra (part 1)

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

Algebra (part 1)

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

Algebra (part 2)

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

In the present thesis, we delve into different extremal and algebraic problems arising from combinatorial geometry. Specifically, we consider the following problems. For any integer $n\ge 3$, we define $e(n)$ to be the minimum positive integer such that any set of $e(n)$ points in general position in the plane contains $n$ points in convex position. In 1935, Erd\H{o}s and Szekeres proved that $e(n) \le {2n-4 \choose n-2}+1$ and later in 1961, they obtained the lower bound $2^{n-2}+1 \le e(n)$, which they conjectured to be optimal. We prove that $e(n) \le {2n-5 \choose n-2}-{2n-8 \choose n-3}+2$. In a recent breakthrough, Suk proved that $e(n) \le 2^{n+O\left(n^{2/3}\log n\right)}$. We strengthen this result by extending it to pseudo-configurations and also improving the error term. Combining our results with a theorem of Dobbins et al., we significantly improve the best known upper bounds on the following two functions, introduced by Bisztriczky and Fejes T'{o}th and by Pach and T'{o}th, respectively. Let $c(n)$ (and $c'(n)$) denote the smallest positive integer $N$ such that any family of $N$ pairwise disjoint convex bodies in general position (resp., $N$ convex bodies in general position, any pair of which share at most two boundary points) has an $n$ members in convex position. We show that $c(n)\le c'(n)\le 2^{n+O\left(\sqrt{n\log n}\right)}$. Given a point set $P$ in the plane, an ordinary circle for $P$ is defined as a circle containing exactly three points of $P$. We prove that any set of $n$ points in the plane, not all on a line or a circle, determines at least $\frac{1}{4}n^2-O(n)$ ordinary circles. We determine the exact minimum number of ordinary circles for all sufficiently large $n$, and characterize all point sets that come close to this minimum. We also consider the orchard problem for circles, where we determine the maximum number of circles containing four points of a given set and describe the extremal configurations. A special case of the Schwartz-Zippel lemma states that given an algebraic curve $C\subset \mathbb{C}^2$ of degree $d$ and two finite sets $A,B\subset \mathbb{C}$, we have $|C\cap (A\times B)|=O_d(|A|+|B|)$. We establish a two-dimensional version of this result, and prove upper bounds on the size of the intersection $|X\cap (P\times Q)|$ for a variety $X\subset \mathbb{C}^4$ and finite sets $P,Q\subset \mathbb{C}^2$. A key ingredient in our proofs is a two-dimensional version of a special case of Alon's combinatorial Nullstellensatz. As corollaries, we generalize the Szemer'edi-Trotter point-line incidence theorem and several known bounds on repeated and distinct Euclidean distances. We use incidence geometry to prove some sum-product bounds over arbitrary fields. First, we give an explicit exponent and improve a recent result of Bukh and Tsimerman by proving that $\max \{ |A+A|, |f(A, A)|\}\gg |A|^{6/5}$ for any small set $A\subset \mathbb{F}_p$ and quadratic non-degenerate polynomial $f(x, y)\in \mathbb{F}_p[x, y]$. This generalizes the result of Roche-Newton et al. giving the best known lower bound for the term $\max \{ |A+A|, |A \cdot A |\}$. Secondly, we improve and generalize the sum-product results of Hegyv'{a}ri and Hennecart on $\max\{ |A+B|, |f(B,C)|\}$, for a specific type of function $f$. Finally, we prove that the number of distinct cubic distances generated by any small set $A\times A\subset \mathbb{F}_p^2$ is $\Omega(|A|^{8/7})$, which improves a result of Yazici et al.

A language is said to be homogeneous when all its words have the same length. Homogeneous languages thus form a monoid under concatenation. It becomes freely commutative under the simultaneous actions of every permutation group G(n) on the collection of homogeneous languages of length n is an element of N. One recovers the isothetic regions from (Haucourt 2017, to appear (online since October 2017)) by considering the alphabet of connected subsets of the space vertical bar G vertical bar, viz the geometric realization of a finite graph G. Factoring the geometric model of a conservative program amounts to parallelize it, and there exists an efficient factoring algorithm for isothetic regions. Yet, from the theoretical point of view, one wishes to go beyond the class of conservative programs, which implies relaxing the finiteness hypothesis on the graph G. Provided that the collections of n-dimensional isothetic regions over G (denoted by R-n vertical bar G vertical bar) are co -unital distributive lattices, the prime decomposition of isothetic regions is given by an algorithm which is, unfortunately, very inefficient. Nevertheless, if the collections R-n vertical bar G vertical bar satisfy the stronger property of being Boolean algebras, then the efficient factoring algorithm is available again. We relate the algebraic properties of the collections R-n vertical bar G vertical bar to the geometric properties of the space I GI. On the way, the algebraic structure R-n vertical bar G vertical bar is proven to be the universal tensor product, in the category of semilattices with zero, of n copies of the algebraic structure R-1 vertical bar G vertical bar.

2019