From Trees to Barcodes and Back Again:A Combinatorial, Probabilistic and Geometric Study of a Topological Inverse Problem

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.

From Trees to Barcodes and Back Again: Theoretical and Statistical Perspectives

Adélie Eliane Garin, Kathryn Hess Bellwald, Lida Kanari

Methods of topological data analysis have been successfully applied in a wide range of fields to provide useful summaries of the structure of complex data sets in terms of topological descriptors, such as persistence diagrams. While there are many powerful techniques for computing topological descriptors, the inverse problem, i.e., recovering the input data from topological descriptors, has proved to be challenging. In this article, we study in detail the Topological Morphology Descriptor (TMD), which assigns a persistence diagram to any tree embedded in Euclidean space, and a sort of stochastic inverse to the TMD, the Topological Neuron Synthesis (TNS) algorithm, gaining both theoretical and computational insights into the relation between the two. We propose a new approach to classify barcodes using symmetric groups, which provides a concrete language to formulate our results. We investigate to what extent the TNS recovers a geometric tree from its TMD and describe the effect of different types of noise on the process of tree generation from persistence diagrams. We prove moreover that the TNS algorithm is stable with respect to specific types of noise.

2020

Unique decomposition of homogeneous languages and application to isothetic regions

Nicolas René Jean Ninin

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

Moyennabilité et courbure

Martin Anderegg

As Avez showed (in 1970), the fundamental group of a compact Riemannian manifold of nonpositive sectional curvature has exponential growth if and only if it is not flat. After several generalizations from Gromov, Zimmer, Anderson, Burger and Shroeder, the following theorem was proved by Adams and Ballmann (in 1998). Theorem Let X be a proper CAT(0) space. If Γ is an amenable group of isometries of X, then at least one of the following two assertions holds: Γ fixes a point in ∂X (boundary of X). X contains a Γ-invariant flat (isometric copy of Rn, n ≥ 0). Following an idea of my PhD advisor Nicolas Monod, I tried to generalize this theorem in the context of goupoids, in this case Borel G-spaces and countable Borel equivalence relations. This lead me to study the notion of Borel fields of metric spaces, which turns out to be a suitable context to define an action of a countable Borel equivalence relation. A field of metric spaces over a set Ω is a family {(Xω,dω)} ω∈Ω of nonempty metric spaces denoted by (Ω,X•). We introduced as S( Ω,X•) the set of maps Such maps are called sections. If Ω is a Borel space, we can define a Borel structure on a field of metric spaces to be a subset Lℒ( Ω,X•) of S( Ω,X•) satisfying these three conditions For all f, g ∈ ℒ(Ω,X•), the function Ω → R, ω → dω(f(ω), g(ω)) is Borel. If h ∈ S(Ω,X•) is such that the function Ω → R, ω → dω(f(ω), h(ω)) is Borel for all f ∈ ℒ(Ω,X•), then h ∈ ℒ(Ω,X•). There exists a countable family of sections {fn}n≥1 ⊆ ℒ(Ω,X•) such that {fn (ω)}n≥1 = Xω for all ω ∈ Ω. This definition is consistent with more classical definitions of Borel fields of Banach spaces or of Borel fields of Hilbert spaces. The notion of a Borel field of metric spaces has been used in convex analysis and in economy. As said before, we can define an action of a countable Borel equivalence relation ℛ ⊆ Ω2 on a Borel field of metric spaces (Ω,X•) in a natural way. It's determined by a family of bijectives maps {α(ω, ω') : Xω → Xω'}(ω,ω')∈ℛ such that For all (ω,ω'), (ω',ω") ∈ ℛ the following equality is satisfied α(ω', ω") ◦ α(ω, ω') = α(ω, ω"). For all f, g ∈ ℒ(Ω,X), the function ℛ → R, (ω, ω') → dω(f(ω), α(ω', ω)g(ω')) is Borel. Zimmer (1977) introduced the notion of amenability for ergodic G-spaces and equivalence relations, of which we obtained the first generalization (in collaboration with Philippe Henry). Theorem Let R be a countable, Borel, preserving the class of the measure, ergodic and amenable equivalence relation on the probability space Ω acting on a Borel field ( Ω,X•) of proper CAT(0) spaces with finite topological dimension. Then at least one of the following assertions is true: There exists an ℛ-invariant Borel section ξ ∈ L(Ω,∂X•). There exists an ℛ-invariant Borel subfield (Ω, F•) of (Ω,X•) consisting of flat subsets. And the second generalization for amenable ergodic G-spaces. Theorem Let G be a locally compact second countable group, Ω a preserving class of the measure, ergodic amenable G-space, X a proper CAT(0) space with finite topological dimension and α : G × Ω → Iso(X) a Borel cocycle. Then at least one of the following assertions is true: There exists an α-invariant Borel function ξ : Ω → ∂X. There exists an α-invariant borelian subfield (Ω, F•) of the trivial field (Ω, X) consisting of flat subsets. If we consider (Ω,μ) to be a strong boundary of the group G, the cocycle α to come from an action of G on X, and X to have flats of at most dimension 2, then we can conclude the following. Theorem Let G be a locally compact second countable group, (Ω,μ) a strong boundary of G, X a proper CAT(0) space with finite topological dimension and whose flats are of dimension at most 2. Let suppose that G acts by isometry on X. Then at least one of the following assertions is true: There exists a G-equivariant Borel function ξ: Ω → ∂X. There exists a G-invariant flat F in X. The proof of the three theorems are strongly based on properties of Borel field of metric spaces that we prove in this thesis.

EPFL2010

Moyennabilité et courbure

Martin Anderegg

EPFL2010