On discrete Morse theory in persistent topology

Abstract

The main topic of this thesis is the interplay between discrete Morse theory and persistent topology: we apply methods from discrete Morse theory to filtered complexes, as they appear in Topological Data Analysis, and study certain persistent homotopy invariants of these complexes, namely merge trees and barcodes.<br /> This thesis is subdivided into three related research projects. In the first two projects we investigate the inverse problem between discrete Morse functions on graphs and their induced merge trees. We generalize a construction by Johnson–Scoville that associates a chiral merge tree to any discrete Morse–Benedetti function on a tree. Using this generalized construction, we present a complete combinatorial description of the fiber of the "induced merge tree" map. Moreover, we find an inverse construction: we associates a discrete Morse–Benedetti function on a tree, respectively graph, to any merge tree, respectively generalized merge tree. In addition, we give a finite number of edit moves, which we call component-merge equivalences, that relate all elements of the fiber to each other. It turns out that for generalized merge trees, which also contain cycle birth information, our inverse construction cannot always produce a critical discrete Morse function on a simple graph. We present a complete criterion for when a generalized merge tree can be realized by a discrete Morse–Benedetti function on a simple graph, and when such a graph can be chosen to be planar. Furthermore, we describe an algorithm that uses the induced (generalized) merge tree in order to optimize discrete Morse functions on graphs.<br /> In the third project, we develop models for parameter spaces of discrete Morse functions on CW complexes and parameter spaces of merge trees. We relate them to parameter spaces of smooth Morse functions on manifolds, parameter spaces of discrete Morse matchings on regular complexes and parameter spaces of barcodes. The project is motivated on one hand by Cerf’s investigation of the space of smooth functions on a manifold that he used to investigate under which circumstances pseudo-isotopies are actually isotopies. On the other hand the third project is also motivated by the goal of the previous two projects: investigations of inverse problems in Topological Data Analysis. parameter spaces provide a more convenient framework for the analysis of inverse problems in persistent topology because they carry more structure to capture the information of the persistent invariants at hand. Except for the parameter spaces of smooth Morse functions, which belong to the realm of (Fréchet) manifolds, all the other mentioned parameter spaces are of a combinatorial nature, namely spaces that are in some way associated to hyperplane arrangements in vector spaces of discrete functions. After introducing these parameter spaces, we realize the following constructions between their corresponding objects of study as continuous maps between the parameter spaces: defining a discrete Morse function on the CW decomposition induced by a smooth Morse function on a manifold, the merge tree induced by a discrete Morse function, the Morse matching induced by a discrete Morse function, and the barcode induced by a merge tree. We also study some basic properties of these maps between parameter spaces.