Structure and stability of the one-dimensional Mapper (Q1620888)

Given a continuous function $f: X\longrightarrow \mathbb{R}$ and a cover $\mathcal{I}$ of its image by intervals, the Mapper is the nerve of a refinement of the pullback cover $f^{-1}(\mathcal{I})$. This paper introduces a theoretical framework that establishes a correspondence between the Mapper to one of the Reeb graphs, which makes it possible to predict which features will be present and which will be absent in the Mapper given the function and the cover and, for each feature, to quantify the degree of (in-)stability. This framework makes it possible to derive guarantees concerning the structure of the Mapper, its stability and its convergence to a Reeb graph as the granularity of the cover $\mathcal{I}$ goes to zero. \par The basic approach is to characterize the structure of the scalar field $f: X\longrightarrow \mathbb{R}$ in terms of the evolution of its level sets $f^{-1}(\{\alpha\})$ for $\alpha$ ranging over $ \mathbb{R}$. This characterization is summarized in a Reeb graph of the pair $(X,f)$ (denoted by $R_f(X)$), which is the quotient space obtained by identifying the points of $X$ that lie in the same connected component of the same level set of $f$. The focus in this paper is on the class of real-valued functions called of \textit{Morse type}, which are generalizations of classical Morse functions. A \textit{Morse function} $f: M\longrightarrow \mathbb{R}$ is a smooth function on a manifold $M$, provided (1) all critical points are non-degenerate and (2) the critical points have distinct function values [\textit{H. Edelsbrunner} and \textit{J. L. Harer}, Computational topology. An introduction. Providence, RI: American Mathematical Society (AMS) (2010; Zbl 1193.55001)]. A good introduction to Morse theory is given by \textit{J. W. Milnor} [Morse theory. Based on lecture notes by M. Spivak and R. Wells. Princeton University Press, Princeton, NJ (1963; Zbl 0108.10401)]. A thorough introduction to extended persistence, zigzag persistence and Reeb graphs is included in this paper. \par This paper has a number of important main results: (1) The topological structure of a Reeb graph $R_f(X)$ is a simplification of the topological structure of a Morse type function $f:X\longrightarrow \mathbb{R}$ (Theorem 7 in Section 2.4). (2) Stability of functional distortion distance between Reeb graphs (Theorem 10, also in Section 2.4). (3) An extended persistence diagram is a simplification of the bag-of-features signature of Reeb graph $R_f(X)$, proved thanks to introduction of \textit{cover zigzag persistence modules}, (Theorem 21 in Section 4). (4) The gomic distance stabilizes MultiNerve Mappers (Theorem 26 in Section 5.1). (5) Stability guarantee for signatures of MultiNerve Mappers (Theorem 28 in Section 5.2). (6) Quantification of how much covers should be permuted to make two multigraphs isomorphic (Theorem 29 in Section 6). (7) An alternative proof of Theorem 21 (Theorem 54 in Section 7). (8) When $(X, f)$ is known only through a finite set of sample points equipped with function values, approximation of a MultiNerve Mapper is obtained (Theorem 63 in Section 8.5). (9) Approximation of a MultiNerve Mapper signature (Theorem 64 , also in Section 8.5). \par This paper also includes a helpful bibliography of 34 related works, making it possible to cover the ground leading up to the results given in this paper.