Lower Bounds

While it may be quite hard to compute the two distances \(M\) and \(\mu\) defined above we may try to compute lower bounds. Topological data analysis is a vast field and several solutions exist in this direction. Here we focus on two of them, namely the interleaving distance of join trees introduced by Morozov, Beketayev, and Weber (2013) and the interleaving distance of Reeb graphs by de Silva, Munch, and Patel (2016).

Join trees and Reeb graphs themselves are very similar. The join tree associated to a function \(f\) can be seen as a real-valued function itself whose fibers encode the connected components of the corresponding sublevel sets of \(f\) and the Reeb graph can be seen as a function whose fibers encode the connected components of the level sets. Join trees are much easier to work with however. While Morozov, Beketayev, and Weber (2013) defined their interleaving distance in an ad hoc manner, de Silva, Munch, and Patel (2016) introduce set-valued (pre)cosheaves first and then they define their interleaving distance. (Actually de Silva, Munch, and Patel (2016) introduce a second interleaving distance, that could be seen as a more ad hoc approach to the problem, but in the author’s opinion[1] their first notion of an interleaving distance using the theory of precosheaves is more convenient for our considerations.)

Here is the main motivation behind this document. For a continuous function \(f\) Morozov, Beketayev, and Weber (2013) define the join tree of \(f\) as the Reeb graph of the epigraph associated to \(f\). Later de Silva, Munch, and Patel (2016) introduced the interleaving distance of Reeb graphs and therefore there are now two different notions of an interleaving distance on join trees. For two continuous functions \(f \colon X \rightarrow {\mathbb{R}}\) and \(g \colon Y \rightarrow {\mathbb{R}}\) we have the interleaving distance of join trees associated to \(f\) and \(g\) as defined by Morozov, Beketayev, and Weber (2013) and we have the interleaving distance of the Reeb graphs associated to the epigraph of \(f\) respectively \(g\) as defined by de Silva, Munch, and Patel (2016). We aim to show that the two distances are the same when \(X\) and \(Y\) are compact smooth manifolds.

It is not really essential and more of a personal preference that from this point onward we work with functions with values in the extended real line \(\overline{{\mathbb{R}}} := [-\infty, \infty]\) and consider real-valued functions a subclass.

When working with different notions of an interleaving distance and in particular when comparing them, the use of some basic category theory seems very natural and simplifies several of our arguments. More specifically we will use functors and natural transformations on several occasions. Moreover we augment the class of \(\overline{{\mathbb{R}}}\)-valued continuous functions with the structure of a category, the category of \(\overline{{\mathbb{R}}}\)-spaces for short.

  • Definition. For two continuous functions \(f \colon X \rightarrow \overline{{\mathbb{R}}}\) and \(g \colon Y \rightarrow \overline{{\mathbb{R}}}\), a homomorphism \(\varphi\) from \(f\) to \(g\), also denoted by \(\varphi \colon f \rightarrow g\), is a continuous map \(\varphi \colon X \rightarrow Y\) such that the diagram \[ \xymatrix{ X \ar@/^/[rr]^{\varphi} \ar[dr]_{f} & & Y \ar[dl]^{g} \\ & \overline{{\mathbb{R}}} } \] commutes.

    We define the composition of homomorphisms in the category of \(\overline{{\mathbb{R}}}\)-spaces by the composition of maps.

    The category of \({\mathbb{R}}\)-spaces is the full subcategory of all real-valued continuous functions.

  • Remark. With these definitions in place a reformulation of question 1 is, whether \(f\) and \(g\) are isomorphic as objects of the category of \(\overline{{\mathbb{R}}}\)-spaces.



[1] the author of this document