\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage[all,2cell]{xy}
\UseTwocells
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\else % if luatex or xelatex
\ifxetex
\usepackage{mathspec}
\usepackage{xltxtra,xunicode}
\else
\usepackage{fontspec}
\fi
\defaultfontfeatures{Mapping=tex-text,Scale=MatchLowercase}
\newcommand{\euro}{€}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\usepackage[textwidth=13cm]{geometry}
\ifxetex
\usepackage[setpagesize=false, % page size defined by xetex
unicode=false, % unicode breaks when used with xetex
xetex]{hyperref}
\else
\usepackage[unicode=true]{hyperref}
\fi
\usepackage[usenames,dvipsnames]{color}
\hypersetup{breaklinks=true,
bookmarks=true,
pdfauthor={},
pdftitle={},
colorlinks=true,
citecolor=blue,
urlcolor=blue,
linkcolor=magenta,
pdfborder={0 0 0}}
\urlstyle{same} % don't use monospace font for urls
\usepackage{graphicx,grffile}
\makeatletter
\def\maxwidth{\ifdim\Gin@nat@width>\linewidth\linewidth\else\Gin@nat@width\fi}
\def\maxheight{\ifdim\Gin@nat@height>\textheight\textheight\else\Gin@nat@height\fi}
\makeatother
% Scale images if necessary, so that they will not overflow the page
% margins by default, and it is still possible to overwrite the defaults
% using explicit options in \includegraphics[width, height, ...]{}
\setkeys{Gin}{width=\maxwidth,height=\maxheight,keepaspectratio}
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
\setlength{\emergencystretch}{3em} % prevent overfull lines
\providecommand{\tightlist}{%
\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{0}
\date{}
% Redefines (sub)paragraphs to behave more like sections
\ifx\paragraph\undefined\else
\let\oldparagraph\paragraph
\renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}}
\fi
\ifx\subparagraph\undefined\else
\let\oldsubparagraph\subparagraph
\renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}}
\fi
\begin{document}
{
\hypersetup{linkcolor=black}
\setcounter{tocdepth}{3}
\tableofcontents
}
\renewcommand{\labelitemi}{~}
\newcommand{\id}{\operatorname{id}}
\newcommand{\Cn}{\mathbb{C}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\Ec}{\overline{\E}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\set}[3]{\{#1 \in #2 ~|~ #3\}}
\newcommand{\colim}{\operatorname{colim}}
\newcommand{\holink}[2]{\operatorname{holink} (#1, #2)}
\newcommand{\op}{\operatorname{op}}
\newcommand{\norm}[1]{\lVert #1 \rVert}
\newcommand{\dis}{\operatorname{dis}}
\newcommand{\siroc}{\operatorname{siroc}}
\newcommand{\epi}{\operatorname{epi}}
\newcommand{\ob}[1]{\operatorname{Ob}(#1)}
\renewcommand{\hom}{\operatorname{Hom}}
\newcommand{\selfm}[1]{\operatorname{End}(#1)}
\section{Introduction}\label{introduction}
The topic of the present text is the interleaving distance of join trees
by Morozov, Beketayev, and Weber
(\protect\hyperlink{ref-morozov2013}{2013}). Just like this paper we
focus on topological data analysis (TDA), which is a broad field. What
is interesting about join trees however, is that they provide for one of
the most simple non-trivial approaches to topological data analysis. We
use this as an excuse to motivate join trees through the role they play
in this domain.
\hypertarget{two-tda-setups}{\subsection{Two Setups in
TDA}\label{two-tda-setups}}
While there are several different approaches in topological data
analysis, our first step is to turn our data into a continuous function.
To be more precise, we associate a continuous function \(f\) to a real
world phenomenon, that we seek to understand, and then we capture some
data to which we associate a continuous function \(g\) approximating
\(f\). We start by loosely describing two different setups of a real
world phenomenon, the type of data we capture, and how we obtain the
continuous function \(g\) from this data.
\hypertarget{sensing-functions}{\subsubsection{Sensing continuous
Functions}\label{sensing-functions}}
When we examine the physical environment around us, we may want to
record our observations. Recording everything we observe is rarely
possible however and therefore we often try to single out one elementary
aspect and focus on this aspect alone. The most basic type of such a
recording is that of a single quantity that we express as a real number
\(r \in \R\). To obtain such a value \(r\), we often use some sensor
that we place somewhere in our physical environment and then we read the
sensor's value. In most situations the sensor will show a different
value, when we place it somewhere else and even when we repeat the
process and read the value from the sensor in the same location another
time, the value may be different. In the latter situation the value is
likely to be similar however and in the former situation the value is
likely to be similar, if the new location is very close to the previous
location. We assume that there is a certain subspace \(X\) of the
environment around us within our reach and interest, where we can place
the sensor. As a subspace of our environment, \(X\) inherits a
\href{https://en.wikipedia.org/wiki/Topological_space\#Definition_via_open_sets}{topology}
and the above observations lead to the intuition, that there is a
\href{https://en.wikipedia.org/wiki/Proper_map}{proper}
\href{https://en.wikipedia.org/wiki/Continuous_function\#Continuous_functions_between_topological_spaces}{continuous
function} \(f \colon X \rightarrow \R\) whose values we are reading of
the sensor in proximity. This is also called a scalar field. Now we may
never learn this function \(f\), but we can interpolate between our
samples from a sufficiently dense set of measuring locations, to define
another continuous function \(g \colon X \rightarrow \R\) that is close
to \(f\) in the sense that
\(-\varepsilon \leq f(p) - g(p) \leq \varepsilon\) for all \(p \in X\)
and a real number \(\varepsilon > 0\) of moderate size. More
specifically we can make \(\varepsilon\) as small as we like by
increasing both, the density of our samples and the accuracy of our
sensor. We concede that the problem of approximating \(f\) is
non-trivial and that
\href{https://en.wikipedia.org/wiki/Interpolation}{interpolation} is a
vast field outside the scope of this document.
\hypertarget{point-cloud}{\subsubsection{Point Clouds of
Shapes}\label{point-cloud}}
Imagine a subspace \(S\) of our environment, denoted by \(X\), is
densely covered with icing sugar. Further we assume we can see the icing
sugar but not the space \(S\) itself. Now let
\(f \colon X \rightarrow \R\) be the function that assigns to each point
in \(X\) it's distance to \(S\) and let \(g \colon X \rightarrow \R\)
assign to each point the distance to a nearest grain of icing sugar.
Then \(S\) is the zero locus of \(f\). Moreover \(g\) can be as close to
\(f\) as we like, if we only spread the icing sugar densely enough. The
icing sugar is also referred to as \emph{point-cloud data for \(S\)}.
\subsection{Distances on Functions}\label{distances-on-functions}
\protect\hyperlink{two-tda-setups}{Above} we discussed how we may
associate a continuous function to a real world phenomenon. Now we
explore what we can do with a continuous function or an approximation
thereof and the conclusions we can draw from this about the original
phenomenon. Let us assume we have two continuous functions
\(f \colon X \rightarrow \R\) and \(g \colon Y \rightarrow \R\) with
approximations \(f' \colon X \rightarrow \R\) respectively
\(g' \colon Y \rightarrow \R\).
\subsubsection{Absolute Distance of
Functions}\label{absolute-distance-of-functions}
We consider the following
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\tightlist
\item
\textbf{Question.} Is there a homeomorphism
\(\varphi \colon X \rightarrow Y\) such that \[
\xymatrix{
X
\ar@/^/[rr]^{\varphi}
\ar[dr]_{f}
& &
Y
\ar[dl]^{g}
\\
&
\R
}
\] commutes?
\end{enumerate}
\begin{itemize}
\item
\emph{Example.} We view a grayscale image as a function defined on a
rectangle describing the luminance of each point. The following image
shows the logo of the university of Bonn in grayscale.
\includegraphics{img/logo-grayscale.png}~
And this image shows a
\href{https://en.wikipedia.org/wiki/Image_warping}{warped} version of
the logo.
\includegraphics{img/logo-grayscale-trafo.png}~
If interpret the two images as functions on a rectangular shape, we
can get the second image from the first by precomposition with a
homeomorphism \(\varphi\) describing the warp we used. Roughly, for
two images, the answer to the above question is \emph{yes}, if we can
obtain one image from the other through a
\href{https://en.wikipedia.org/wiki/Image_warping}{warp}.
\end{itemize}
As we obtain an image from sampling the luminance with a sensor at each
pixel, the previous example corresponds to
\protect\hyperlink{sensing-functions}{the first setup above}. Let
\(S \subset X\) and \(S' \subset Y\) be subspaces of metric spaces \(X\)
respectively \(Y\) and let \(f\) respectively \(g\) describe the
distance to \(S\) respectively \(S'\) as in
\protect\hyperlink{point-cloud}{the second setup above}. Now suppose
\(\varphi \colon X \rightarrow Y\) is an isometry with
\(\varphi(S) = S'\), then the above diagram commutes. In some sense this
means, that if \(S\) and \(S'\) describe the same shape, then the answer
to the above questions is \emph{yes}.
The above question is very narrow as we ask for equality. In most
situations occurring in nature the answer is very likely to be
\emph{no}. But we may still try to quantify how \emph{distant an
affirmative answer is}. To this end we start with specifying an
\(\varepsilon \geq 0\) and asking the following
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{1}
\tightlist
\item
\textbf{Question.} Is there a homeomorphism
\(\varphi \colon X \rightarrow Y\) such that for all \(p \in X\) the
estimates \(-\varepsilon \leq f(p) - g(\varphi(p)) \leq \varepsilon\)
hold?
\end{enumerate}
Next we may ask, how large \(\varepsilon\) needs to be in order for the
answer to be \emph{yes}. This is the motivation behind the following
\begin{itemize}
\item
\textbf{Definition.} Let \(M(f, g)\) be the infimum of all
\(\varepsilon \geq 0\) such that the answer to the previous question
is affirmative. We name this \emph{the absolute distance of \(f\) and
\(g\)}.
\item
\emph{Remark.} Though we won't need it we have the following equation
for \(M\). Let \(\mathcal{H}\) be the set of homeomorphisms from \(X\)
to \(Y\), then \[M(f, g) =
\inf_{\varphi \in \mathcal{H}} \norm{f - g \circ \varphi}_{\infty} .\]
\end{itemize}
Next we observe that \(M\) satisfies the triangle inequality.
\begin{itemize}
\tightlist
\item
\textbf{Lemma} (Triangle Inequality)\textbf{.} Let
\(h \colon Z \rightarrow \R\) be another continuous function, then
\(M(f, h) \leq M(f, g) + M(g, h)\).
\end{itemize}
Now we recall that we started with two continuous functions \(f\) and
\(g\) and each might describe the luminance of an image or the distance
to a certain shape and this is all good, but we should not forget that
in practice we may never learn \(f\) or \(g\) and we have to cope with
their approximations \(f'\) respectively \(g'\). In topological data
analysis the keyword here is \emph{stability} ever since Cohen-Steiner,
Edelsbrunner, and Harer (\protect\hyperlink{ref-MR2460372}{2005}).
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{2}
\tightlist
\item
\textbf{Lemma} (Stability)\textbf{.} Suppose we have
\(\norm{f - f'}_{\infty} = \varepsilon\), then
\(M(f, f') \leq \varepsilon\).
\end{enumerate}
\begin{itemize}
\tightlist
\item
\emph{Proof.} Setting \(\varphi = \id_X\) we get an affirmative answer
to question 2.
\end{itemize}
The previous two lemmata have the following
\begin{itemize}
\tightlist
\item
\textbf{Corollary.} Suppose we have
\(\norm{f - f'}_{\infty} \leq \varepsilon \geq \norm{g - g'}_{\infty}\),\\
then \(|M(f', g') - M(f, g)| \leq 2 \varepsilon\).
\end{itemize}
In summary \(M\) defines an extended pseudometric on the class of
continuous functions and the above corollary shows that by approximating
the functions \(f\) and \(g\), we can also approximate their absolute
distance.
\subsubsection{Relative Distance of
Functions}\label{relative-distance-of-functions}
We reconsider \protect\hyperlink{sensing-functions}{the first setup
above} where we take samples to approximate the continuous functions
\(f \colon X \rightarrow \R\) and \(g \colon Y \rightarrow \R\). Now we
imagine that the region \(X\), where we sample \(f\), is miles away from
the region \(Y\), where we sample \(g\). Then it may be impractical to
use the same sensor for both \(f\) and \(g\). It would be more practical
if someone who lived near \(X\) took the samples for \(f\) and someone
else who lived near \(Y\) took the samples for \(g\), each of them using
their own sensor. Now suppose that any value read from the sensor used
for sampling \(f\) always differed by roughly the same additive constant
\(r \in \R\) from the value that would have been read of the other
sensor in the same location. The two sensors were so far apart however,
that we could not measure this value \(r\) nor could we calibrate one
sensor to match the other. To work around this dilemma we consider a
slight modification of question 1.
\begin{itemize}
\tightlist
\item
\textbf{Question.} Is there a homeomorphism
\(\varphi \colon X \rightarrow Y\) and a real number \(r\) such that
\[
\xymatrix@C+10pt{
X
\ar[r]^{\varphi}
\ar[d]_f
&
Y
\ar[d]^{g}
\\
\R
\ar[r]_{(r + \_)}
&
\R
}
\] commutes? (In other words \(r + f(p) = g(\varphi(p))\) for all
\(p \in X\).)
\end{itemize}
Again this is a very narrow question and in nature the answer is likely
to be \emph{no}. Nevertheless we may try to quantify how \emph{distant
an affirmative answer is}. To this end we specify \(\varepsilon \geq 0\)
and ask the following
\begin{itemize}
\tightlist
\item
\textbf{Question.} Is there a homeomorphism
\(\varphi \colon X \rightarrow Y\) and a real number \(r\) such that
for all \(p \in X\) the estimates
\(-\varepsilon \leq r + f(p) - g(\varphi(p)) \leq \varepsilon\) hold?
\end{itemize}
Now we minimize over all \(\varepsilon\) that provide an affirmative
answer.
\begin{itemize}
\item
\textbf{Definition.} Let \(\mu(f, g)\) be the infimum of all
\(\varepsilon \geq 0\) such that the answer to the previous question
is affirmative. We name this \emph{the relative distance of \(f\) and
\(g\)}.
\item
\emph{Remark.} Though we won't need it, we have the following
alternative description for \(\mu(f, g)\) if \(X \neq \emptyset\). Let
\(\mathcal{H}\) be the set of homeomorphisms from \(X\) to \(Y\), then
\[\mu(f, g) =
\frac{1}{2} \inf_{\varphi \in \mathcal{H}} \left(
\sup_{p \in X} (f(p) - g(\varphi(p))) -
\inf_{p \in X} (f(p) - g(\varphi(p)))
\right) .\]
\end{itemize}
Completely analogously to the above we have a triangular inequality.
\begin{itemize}
\tightlist
\item
\textbf{Lemma} (Triangle Inequality)\textbf{.} Let
\(h \colon Z \rightarrow \R\) be another continuous function, then
\(\mu(f, h) \leq \mu(f, g) + \mu(g, h)\).
\end{itemize}
Moreover we have the following relation to the absolute distance.
\begin{itemize}
\tightlist
\item
\textbf{Lemma.} We have \(\mu(f, g) \leq M(f, g)\).
\end{itemize}
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{3}
\tightlist
\item
\textbf{Corollary} (Stability)\textbf{.} Suppose we have
\(\norm{f - f'}_{\infty} = \varepsilon\), then
\(\mu(f, f') \leq \varepsilon\).
\end{enumerate}
\begin{itemize}
\tightlist
\item
\emph{Proof.} This follows in conjunction with lemma 3.
\end{itemize}
The Triangle Inequality and Stability have the following
\begin{itemize}
\tightlist
\item
\textbf{Corollary.} Suppose we have
\(\norm{f - f'}_{\infty} \leq \varepsilon \geq \norm{g - g'}_{\infty}\),\\
then \(|\mu(f', g') - \mu(f, g)| \leq 2 \varepsilon\).
\end{itemize}
In summary \(\mu\) defines an extended pseudometric on the class of
continuous functions and the above corollary shows that by approximating
the functions \(f\) and \(g\), we can also approximate their relative
distance.
\hypertarget{lower-bounds}{\subsection{Lower
Bounds}\label{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
(\protect\hyperlink{ref-morozov2013}{2013}) and the interleaving
distance of Reeb graphs by de Silva, Munch, and Patel
(\protect\hyperlink{ref-deSilva2016}{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 (\protect\hyperlink{ref-morozov2013}{2013}) defined their
interleaving distance in an ad hoc manner, de Silva, Munch, and Patel
(\protect\hyperlink{ref-deSilva2016}{2016}) introduce set-valued
(pre)cosheaves first and then they define their interleaving distance.
(Actually de Silva, Munch, and Patel
(\protect\hyperlink{ref-deSilva2016}{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\footnote{the author of this
document} 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
(\protect\hyperlink{ref-morozov2013}{2013}) define the join tree of
\(f\) as the \href{https://en.wikipedia.org/wiki/Reeb_graph}{Reeb graph}
of the
\href{https://en.wikipedia.org/wiki/Epigraph_\%28mathematics\%29}{epigraph}
associated to \(f\). Later de Silva, Munch, and Patel
(\protect\hyperlink{ref-deSilva2016}{2016}) introduced the
\emph{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 \R\) and
\(g \colon Y \rightarrow \R\) we have the interleaving distance of join
trees associated to \(f\) and \(g\) as defined by Morozov, Beketayev,
and Weber (\protect\hyperlink{ref-morozov2013}{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
(\protect\hyperlink{ref-deSilva2016}{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{\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
\href{https://en.wikipedia.org/wiki/Category_theory}{category theory}
seems very natural and simplifies several of our arguments. More
specifically we will use
\href{https://en.wikipedia.org/wiki/Functor\#Definition}{functors} and
\href{https://en.wikipedia.org/wiki/Natural_transformation\#Definition}{natural
transformations} on several occasions. Moreover we augment the class of
\(\overline{\R}\)-valued continuous functions with the structure of a
category, the \emph{category of \(\overline{\R}\)-spaces} for short.
\begin{itemize}
\item
\textbf{Definition.} For two continuous functions
\(f \colon X \rightarrow \overline{\R}\) and
\(g \colon Y \rightarrow \overline{\R}\), a \emph{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{\R}
}
\] commutes.
We define the composition of homomorphisms in the \emph{category of
\(\overline{\R}\)-spaces} by the composition of maps.
The \emph{category of \(\R\)-spaces} is the
\href{https://ncatlab.org/nlab/show/full+subcategory}{full
subcategory} of all real-valued continuous functions.
\item
\emph{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{\R}\)-spaces.
\end{itemize}
\subsubsection{Further References}\label{further-references}
Join trees have been harnessed for a similar purpose by Saikia, Seidel,
and Weinkauf (\protect\hyperlink{ref-saikia14a}{2014}). Further methods
to compare Reeb graphs have been proposed by Bauer, Ge, and Wang
(\protect\hyperlink{ref-bauer2014}{2014}) and for the special case of
functions on orientable surfaces by Di Fabio and Landi
(\protect\hyperlink{ref-diFabio2014}{2014}). The two distances from
(Bauer, Ge, and Wang \protect\hyperlink{ref-bauer2014}{2014}) and (de
Silva, Munch, and Patel \protect\hyperlink{ref-deSilva2016}{2016}) have
been shown to be equivalent in some sense by Bauer, Munch, and Wang
(\protect\hyperlink{ref-bauer2015}{2015}). Moreover the work presented
here borrows from (Bubenik, de Silva, and Scott
\protect\hyperlink{ref-bubenik2014}{2014}) on several aspects. There is
much more prior art and the papers we mentioned merely represent our
primary references. Most of the papers mentioned by de Silva, Munch, and
Patel (\protect\hyperlink{ref-deSilva2016}{2016}) and Bubenik, de Silva,
and Scott (\protect\hyperlink{ref-bubenik2014}{2014}) in their
introductions are antecedents to our work as well. We presented some of
the abstract ideas we use here in the form of a poster (Fluhr
\protect\hyperlink{ref-fluhr2017}{2017}). Little did we know that de
Silva, Munch, and Stefanou (\protect\hyperlink{ref-deSilva2017b}{2017})
were developing a very similar framework. Some differences between their
approach and ours is that they work in a very general setup with an
arbitrary metric space whereas we merely consider the real numbers as a
base space. This made it feasible for us to treat the absolute and the
relative interleaving distance in one go.
\section{Reeb Graphs}\label{reeb-graphs}
In this section we introduce Reeb graphs.
\begin{itemize}
\item
\textbf{Definition} (Reeb Graph)\textbf{.} Given a continuous function
\(f \colon X \rightarrow \overline{\R}\) and \(x \in X\), let
\(\pi_f (x)\) be the connected component of \(x\) in \(f^{-1}(f(x))\).
In this way we obtain a function
\(\pi_f \colon X \rightarrow \pi_f (X) \subset 2^X\) and we endow
\(\pi_f (X)\) with the quotient topology\footnote{see for example
(Bredon \protect\hyperlink{ref-bredon1993}{1993}, definition I.13.1)}.
By the
\href{https://en.wikipedia.org/wiki/Quotient_space_\%28topology\%29\#Properties}{universal
property of the quotient space} there is a unique continuous function
\(\mathcal{R} f \colon \pi_f (X) \rightarrow \overline{\R}\) such that
\[
\xymatrix{
X
\ar[r]^{\pi_f}
\ar[dr]_f
&
\pi_f (X)
\ar[d]^{\mathcal{R} f}
\\
&
\overline{\R}
}
\] commutes, i.e. \(\mathcal{R} f \circ \pi_f = f\).
For another continuous function
\(g \colon Y \rightarrow \overline{\R}\) and a homomorphism
\(\varphi \colon f \rightarrow g\) we may use the universal property
of \(\pi_f\) again, to obtain a unique continuous map
\(\mathcal{R} \varphi \colon \pi_f (X) \rightarrow \pi_g (Y)\) such
that \[
\xymatrix{
X
\ar[d]_{\pi_f}
\ar[r]^{\varphi}
&
Y
\ar[d]^{\pi_g}
\\
\pi_f (X)
\ar[r]_{\mathcal{R} \varphi}
&
\pi_g (Y)
}
\] commutes, i.e.
\(\mathcal{R} \varphi \circ \pi_f = \pi_g \circ \varphi\).
\end{itemize}
\begin{itemize}
\item
\textbf{Lemma.} Let \(f \colon X \rightarrow \overline{\R}\) and
\(g \colon Y \rightarrow \overline{\R}\) be continuous functions and
let \(\varphi \colon f \rightarrow g\) be a homomorphism, then the
diagram \[
\xymatrix{
\pi_f (X)
\ar@/^/[rr]^{\mathcal{R} \varphi}
\ar[dr]_{\mathcal{R} f}
& &
\pi_g (Y)
\ar[dl]^{\mathcal{R} g}
\\
&
\overline{\R}
}
\] commutes. Or in other words \(\mathcal{R} \varphi\) is a
homomorphism from \(\mathcal{R} f\) to \(\mathcal{R} g\) in the
category of \(\overline{\R}\)-spaces.
\item
\emph{Proof.} We consider the diagram \[
\xymatrix@C=5pt{
\pi_f (X)
\ar[rr]^{\mathcal{R} \varphi}
\ar@/_3pc/[ddr]_{\mathcal{R} f}
& &
\pi_g (Y)
\ar@/^3pc/[ddl]^{\mathcal{R} g}
\\
X
\ar[u]_{\pi_f}
\ar[rr]^{\varphi}
\ar[dr]^f
& &
Y
\ar[u]^{\pi_g}
\ar[dl]_g
\\ &
\overline{\R} .
}
\] In this diagram the three inner triangles and the square commute.
Further \(\pi_f\) and \(\pi_g\) are surjective and thus the outer
triangle commutes as well.
\item
\textbf{Lemma.} Let \(f \colon X \rightarrow \overline{\R}\),
\(g \colon Y \rightarrow \overline{\R}\), and
\(h \colon Z \rightarrow \overline{\R}\) be continuous functions and
let \(\varphi \colon f \rightarrow g\) and
\(\psi \colon g \rightarrow h\) be two homomorphisms, then
\(\mathcal{R} (\psi \circ \varphi) = \mathcal{R} \psi \circ \mathcal{R} \varphi\).
\item
\emph{Proof.} We consider the diagram \[
\xymatrix{
X
\ar[r]^{\varphi}
\ar[d]_{\pi_f}
&
Y
\ar[r]^{\psi}
\ar[d]_{\pi_g}
&
Z
\ar[d]_{\pi_h}
\\
\pi_f (X)
\ar[r]_{\mathcal{R} \varphi}
&
\pi_g (Y)
\ar[r]_{\mathcal{R} \psi}
&
\pi_h (Z) .
}
\] By definition both inner squares commute, hence the outer square
commutes as well. Now it follows from the uniqueness part of the
universal property of \(\pi_f\) that
\(\mathcal{R} (\psi \circ \varphi) = \mathcal{R} \psi \circ \mathcal{R} \varphi\).
\end{itemize}
The previous two lemmata imply that \(\mathcal{R}\) is an endofunctor on
the category of \(\overline{\R}\)-spaces. Later we will define an
interleaving distance on Reeb graphs, but first we will introduce join
trees and their interleavings. Join trees are easier to understand and
may provide us with some intuition for understanding the more
sophisticated interleavings of Reeb graphs.
\hypertarget{join-trees}{\section{Join Trees}\label{join-trees}}
In this section we define join trees and their interleaving distance due
to Morozov, Beketayev, and Weber
(\protect\hyperlink{ref-morozov2013}{2013}). We start with an auxiliary
\begin{itemize}
\item
\textbf{Definition} (Epigraph)\textbf{.} Let
\(f \colon X \rightarrow \overline{\R}\) be a continuous map, it's
\emph{epigraph} is
\(\epi f := \set{(x, y)}{X \times \overline{\R}}{y \geq f(x)}\).\\
Further we define\\
\(\mathcal{E} f \colon \epi f \rightarrow \overline{\R}, (x, y) \mapsto y\)
and\\
\(\kappa_f \colon X \rightarrow \epi f, x \mapsto (x, f(x))\).
For \(a \geq 0\) we set
\(i^{a}_f \colon \epi f \rightarrow \epi f, (x, y) \mapsto (x, y + a)\).
\end{itemize}
The epigraph and the Reeb graphs from the previous section allow for a
very brief definition of join trees.
\begin{itemize}
\item
\textbf{Definition} (Join Trees)\textbf{.} Let
\(f \colon X \rightarrow \R\) be a continuous map, it's \emph{join
tree} is \(\mathcal{R} \mathcal{E} f\).
\item
\emph{Example.} Let
\(f \colon \big[-3, 3 + \frac{1}{4}\big] \rightarrow \R, x \mapsto x^3 - 3 x\)
and
\(g \colon \big[-3, 3 + \frac{1}{4}\big] \rightarrow \R, x \mapsto 6x\).
The following image shows the graphs of \(f\) and \(g\).
\includegraphics{img/mpl/2functions-plot}~
The next image shows the corresponding epigraphs.
\includegraphics{img/mpl/2functions-epigraph}~
And a visualization of their join trees, i.e.~the Reeb graphs of their
epigraphs, is shown in the image below.
\includegraphics{img/mpl/2functions-join-trees}~
\end{itemize}
Before we get to interleavings we make some auxiliary definitions.
\begin{itemize}
\tightlist
\item
\textbf{Definition.} We set
\(D^{\perp} := \set{(a, b)}{(-\infty, \infty] \times (-\infty, \infty]}{a + b \geq 0}\).
\end{itemize}
Component-wise addition yields the structure of a monoid on
\(D^{\perp}\). Next we define two weightings on \(D^{\perp}\).
\begin{itemize}
\tightlist
\item
\textbf{Definition.} We set
\(\epsilon' \colon D^{\perp} \rightarrow [0, \infty], (a, b) \mapsto \frac{1}{2} (a + b)\)
and
\(\epsilon'' \colon D^{\perp} \rightarrow [0, \infty], (a, b) \mapsto \max \{a, b\}\).
\end{itemize}
We note that \(\epsilon'\) is additive and that \(\epsilon''\) is
subadditive. Now we define interleavings of join trees. To this end let
\(f \colon X \rightarrow \R\) and \(g \colon Y \rightarrow \R\) be
continuous functions.
\begin{itemize}
\item
\textbf{Definition} (Interleavings of Join Trees)\textbf{.} For
\((a, b) \in D^{\perp}\) an \emph{\((a, b)\)-interleaving of
\(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} g\)} is a
pair of homomorphisms
\(\varphi \colon b + \mathcal{R} \mathcal{E} f \rightarrow \mathcal{R} \mathcal{E} g\)
and
\(\psi \colon a + \mathcal{R} \mathcal{E} g \rightarrow \mathcal{R} \mathcal{E} f\)
such that the diagrams \[
\xymatrix{
a + b + \mathcal{R} \mathcal{E} f
\ar@/^/[rr]^{(\mathcal{R} \circ i^{a + b})_f}
\ar[dr]_{\varphi}
& &
\mathcal{R} \mathcal{E} f
\\
&
a + \mathcal{R} \mathcal{E} g
\ar[ru]_{\psi}
}
\] and \[
\xymatrix{
a + b + \mathcal{R} \mathcal{E} g
\ar@/^/[rr]^{(\mathcal{R} \circ i^{a + b})_g}
\ar[dr]_{\psi}
& &
\mathcal{R} \mathcal{E} g
\\
&
b + \mathcal{R} \mathcal{E} f
\ar[ru]_{\varphi}
}
\] commute.
For \(\varepsilon \geq 0\) an \emph{\(\varepsilon\)-interleaving of
\(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} g\)} is an
\((\varepsilon, \varepsilon)\)-interleaving.
\item
\emph{Example.} We consider the join trees from the previous example.
We set
\(\varphi \colon \pi_{\mathcal{E} f} (\epi f) \rightarrow \pi_{\mathcal{E} g} (\epi g), \pi_{\mathcal{E} f} ((x, y)) \mapsto \pi_{\mathcal{E} g} ((-3, y + 2))\)
and\\
\(\psi \colon \pi_{\mathcal{E} g} (\epi g) \rightarrow \pi_{\mathcal{E} f} (\epi f), \pi_{\mathcal{E} g} ((x, y)) \mapsto \pi_{\mathcal{E} f} ((-3, y + 2))\),
then \(\varphi\) and \(\psi\) form a \((2, 2)\)-interleaving of
\(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} g\).
\end{itemize}
With interleavings defined we can define the interleaving distances.
\begin{itemize}
\item
\textbf{Definition} (Interleaving Distances of Join Trees)\textbf{.}
Let \(\mathcal{I}\) be the set of all \(\mathbf{a} \in D^{\perp}\)
such that there is an \(\mathbf{a}\)-interleaving of
\(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} g\). Then
we set
\(M_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g) := \inf \epsilon'' (\mathcal{I})\)
and
\(\mu_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g) := \inf \epsilon' (\mathcal{I})\).
We name
\(M_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g)\) the
\emph{absolute interleaving distance of \(\mathcal{R} \mathcal{E} f\)
and \(\mathcal{R} \mathcal{E} g\)} and
\(\mu_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g)\) the
\emph{relative interleaving distance of \(\mathcal{R} \mathcal{E} f\)
and \(\mathcal{R} \mathcal{E} g\)}.
\end{itemize}
We note that these definitions of an interleaving distance are different
from the one by Morozov, Beketayev, and Weber
(\protect\hyperlink{ref-morozov2013}{2013}). However the subsequent
corollary shows that our absolute interleaving distance is equal to the
distance by Morozov, Beketayev, and Weber
(\protect\hyperlink{ref-morozov2013}{2013}). The reason we gave a
different definition is that now we can phrase the computation of the
absolute and the relative interleaving distance each as an optimization
problem over the same domain.
\begin{itemize}
\item
\textbf{Lemma} (Monotonicity)\textbf{.} For \((a, b) \in D^{\perp}\)
let
\(\varphi \colon b + \mathcal{R} \mathcal{E} f \rightarrow \mathcal{R} \mathcal{E} g\)
and
\(\psi \colon a + \mathcal{R} \mathcal{E} g \rightarrow \mathcal{R} \mathcal{E} f\)
be an \((a, b)\)-interleaving of \(\mathcal{R} \mathcal{E} f\) and
\(\mathcal{R} \mathcal{E} g\). Moreover let \(\varepsilon \geq 0\).
Then \((\mathcal{R} \circ i^{\varepsilon})_g \circ \varphi\) and
\(\psi\) yield an \((a, b + \varepsilon)\)-interleaving. Completely
analogously \(\varphi\) and
\((\mathcal{R} \circ i^{\varepsilon})_f \circ \psi\) form an
\((a + \varepsilon, b)\)-interleaving.
\item
\emph{Proof.} We consider the diagram \[
\xymatrix@C=40pt{
a + b + \varepsilon + \mathcal{R} \mathcal{E} f
\ar[r]|-{(\mathcal{R} \circ i^{a + b})_f}
\ar[dr]_{\varphi}
\ar@/^2pc/[rr]^{(\mathcal{R} \circ i^{a + b + \varepsilon})_f}
&
\varepsilon + \mathcal{R} \mathcal{E} f
\ar[r]|-{(\mathcal{R} \circ i^{\varepsilon})_f}
&
\mathcal{R} \mathcal{E} f
\\
&
a + \varepsilon + \mathcal{R} \mathcal{E} g
\ar[u]_{\psi}
\ar[r]_{(\mathcal{R} \circ i^{\varepsilon})_g}
&
a + \mathcal{R} \mathcal{E} g .
\ar[u]_{\psi}
}
\] Since all the inner triangles and the square commute in the above
diagram, the outer triangle commutes as well. The other triangle, for
\((\mathcal{R} \circ i^{\varepsilon})_g \circ \varphi\) and \(\psi\)
to be an interleaving, also commutes, because we have
\((\mathcal{R} \circ i^{\varepsilon})_g \circ (\mathcal{R} \circ i^{a + b})_g = (\mathcal{R} \circ i^{a + b + \varepsilon})_g\).
\item
\textbf{Corollary.} The absolute interleaving distance
\(M_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g)\) is
the infimum of all \(\varepsilon \geq 0\) such that there is an
\(\varepsilon\)-interleaving of \(\mathcal{R} \mathcal{E} f\) and
\(\mathcal{R} \mathcal{E} g\).
\item
\emph{Proof.} Let \(d\) be the infimum of all \(\varepsilon \geq 0\)
such that there is an \(\varepsilon\)-interleaving of
\(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} g\). Then
the inequality
\(d \leq M_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g)\)
is clear. For the other inequality suppose we have an
\((a, b)\)-interleaving of \(\mathcal{R} \mathcal{E} f\) and
\(\mathcal{R} \mathcal{E} g\). Then the previous lemma implies that we
also have an \((\epsilon''(a, b))\)-interleaving of
\(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} g\).
\end{itemize}
Next we underpin the naming conventions from the previous definition by
proving a type of triangle inequality for each interleaving distance. To
this end let \(h \colon Z \rightarrow \R\) be yet another continuous
function.
\begin{itemize}
\item
\textbf{Lemma.} Let \((a, b), (c, d) \in D^{\perp}\). Further let
\(\varphi \colon b + \mathcal{R} \mathcal{E} f \rightarrow \mathcal{R} \mathcal{E} g\)
and
\(\psi \colon a + \mathcal{R} \mathcal{E} g \rightarrow \mathcal{R} \mathcal{E} f\)
be an \((a, b)\)-interleaving of \(\mathcal{R} \mathcal{E} f\) and
\(\mathcal{R} \mathcal{E} g\) and let
\(\varphi' \colon d + \mathcal{R} \mathcal{E} g \rightarrow \mathcal{R} \mathcal{E} h\)
and
\(\psi' \colon c + \mathcal{R} \mathcal{E} h \rightarrow \mathcal{R} \mathcal{E} g\)
be a \((c, d)\)-interleaving of \(\mathcal{R} \mathcal{E} g\) and
\(\mathcal{R} \mathcal{E} h\). Then \(\varphi' \circ \varphi\) and
\(\psi \circ \psi'\) yield an \((a + c, b + d)\)-interleaving of
\(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} h\).
\item
\emph{Proof.} We consider the diagram \[
\xymatrix@C+=40pt{
a + b + c + d + \mathcal{R} \mathcal{E} f
\ar[r]|-{(\mathcal{R} \circ i^{a + b})_f}
\ar[dr]_{\varphi}
\ar@/^2pc/[rr]^{(\mathcal{R} \circ i^{a + b + c + d})_f}
&
c + d + \mathcal{R} \mathcal{E} f
\ar[r]|-{(\mathcal{R} \circ i^{c + d})_f}
&
\mathcal{R} \mathcal{E} f
\\
&
a + c + d + \mathcal{R} \mathcal{E} g
\ar[u]_{\psi}
\ar[r]|-{(\mathcal{R} \circ i^{c + d})_g}
\ar[dr]_{\varphi'}
&
a + \mathcal{R} \mathcal{E} g
\ar[u]_{\psi}
\\
& &
a + c + \mathcal{R} \mathcal{E} h .
\ar[u]_{\psi'}
}
\] The upper triangle commutes since
\(i^{a + b + c + d}_f = i^{c + d}_f \circ i^{a + b}_f\) and since
\(\mathcal{R}\) is a functor. The other two inner triangles and the
square commute by definition and thus the outer triangle commutes as
well. The proof that the other triangle, for
\(\varphi' \circ \varphi\) and \(\psi \circ \psi'\) to be an
interleaving, commutes, is completely analogous.
\item
\textbf{Corollary} (Triangle Inequality)\textbf{.} We have \[
M_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} h)
\leq
M_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g) +
M_{J} (\mathcal{R} \mathcal{E} g, \mathcal{R} \mathcal{E} h)
\] and \[
\mu_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} h)
\leq
\mu_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g) +
\mu_{J} (\mathcal{R} \mathcal{E} g, \mathcal{R} \mathcal{E} h) .
\]
\end{itemize}
Next we show that the interleaving distances provide lower bounds for
the corresponding distances of functions
\protect\hyperlink{lower-bounds}{as promised}.
\begin{itemize}
\item
\textbf{Proposition.} Suppose we have a homeomorphism
\(\varphi \colon X \rightarrow Y\), \(\varepsilon \geq 0\), and
\(r \in \R\) such that
\(-\varepsilon \leq r + f(p) - g(\varphi(p)) \leq \varepsilon\) for
all \(p \in X\). Let
\(\varphi' \colon \epi f \rightarrow \epi g, (p, u) \mapsto (\varphi(p), u + r + \varepsilon)\)
and
\(\psi' \colon \epi g \rightarrow \epi f, (q, v) \mapsto (\varphi^{-1}(q), v - r + \varepsilon)\).
Then \(\mathcal{R} \varphi'\) and \(\mathcal{R} \psi'\) are an
\((-r + \varepsilon, r + \varepsilon)\)-interleaving of
\(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} g\).
\item
\textbf{Corollary.} We have
\(M_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g) \leq M (f, g)\)
and
\(\mu_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g) \leq \mu (f, g)\).
\end{itemize}
This corollary concludes our treatment of join trees by themselves. The
next step concerning join trees would be to describe practical
algorithms to compute them and to compute each of their interleaving
distances, but this is outside the scope of this document. Next we
consider other more elaborate approaches to finding lower bounds to the
absolute and relative distance of functions. Nevertheless the main
stream of arguments will always be very similar to the one in this
section. We will just use more auxiliary results from domains other than
topological data analysis. After we covered Reeb graphs we will even
describe a more general framework that encompasses both join trees and
Reeb graphs, so we could actually abandon the results from this section.
At the expense of some repetition we chose not to do this because this
section contains everything that follows in a nutshell.
\hypertarget{precosheaves}{\section{Interlude on
Precosheaves}\label{precosheaves}}
In this section we develop the theory of precosheaves to the extend
needed for the interleaving distance of Reeb graphs by de Silva, Munch,
and Patel (\protect\hyperlink{ref-deSilva2016}{2016}) and subsequent
sections. Before we get to precosheaves we start with some point-set
topological definitions.
\begin{itemize}
\item
\textbf{Definition} (Intersection-Base)\textbf{.} Let \(X\) be a set.
An \emph{intersection-base on \(X\)} is a collection \(\mathcal{B}\)
of subsets of \(X\) that covers \(X\) and such that for any
\(U, V \in \mathcal{B}\) we have \(U \cap V \in \mathcal{B}\).
\item
\emph{Example.} Let \(X\) be a topological space, then the topology on
\(X\) is an intersection-base on \(X\).
The set of open intervals of \(\R\) is an intersection-base on \(\R\).
\item
\textbf{Definition} (Intersection-based space)\textbf{.} An
\emph{intersection-based space} is a set \(X\) together with an
intersection-base \(\mathcal{B}\) on \(X\).
For any \(U \in \mathcal{B}\) we say that \(U\) is a
\emph{distinguished open subset of \(X\)}.
\end{itemize}
Similar to topological spaces we can equip subsets of an
intersection-based space with an induced intersection-base.
\begin{itemize}
\item
\textbf{Lemma.} Let \(X\) be a set and \(\mathcal{B}\) be an
intersection base on \(X\). For a subset \(Y \subseteq X\) the family
\(\{Y \cap U\}_{u \in \mathcal{B}}\) is an intersection-base on \(Y\).
\item
\textbf{Definition.} In the context of the previous lemma we say
\emph{\(Y\) is a subspace of \(X\)}.
\end{itemize}
In addition to subspaces we also define products.
\begin{itemize}
\tightlist
\item
\textbf{Definition} (Product)\textbf{.} Let \(X\) and \(Y\) be
intersection-based spaces with intersection-bases \(\mathcal{B}_X\)
respectively \(\mathcal{B}_Y\). We augment \(X \times Y\) with the
intersection-base \(\mathcal{B}_X \times \mathcal{B}_Y\) and name this
space the \emph{product \(X \times Y\) of \(X\) and \(Y\)}.
\end{itemize}
Next we define continuous maps between intersection-based spaces.
\begin{itemize}
\item
\textbf{Definition.} For two intersection-based spaces \(X\) and \(Y\)
a map of sets \(\varphi \colon X \rightarrow Y\) is said to be
\emph{continuous} if for any distinguished open subset
\(V \subseteq Y\) it's preimage \(\varphi^{-1} (V)\) is a
distinguished open subset of \(X\).
\item
\emph{Remark.} The previous definition augments the class of
intersection-based spaces with the structure of a category that
contains the category of topological spaces as a
\href{https://ncatlab.org/nlab/show/full+subcategory}{full
subcategory}.
\item
\emph{Example.} Suppose \(Y\) is a subspace of the intersection-based
space \(X\), then the inclusion of \(Y\) into \(X\) is continuous.
\item
\textbf{Lemma.} Let \(X\) be a topological space, let \(Y\) be a set,
and let \(\mathcal{B}\) be an intersection-base on \(Y\). Then a map
of sets \(\varphi \colon X \rightarrow Y\) is continuous as a map
between intersection-based spaces if and only if it is continuous with
respect to the topology on \(Y\) induced by \(\mathcal{B}\).
\item
\emph{Remark.} The previous lemma implies that the category of
topological spaces is a
\href{https://ncatlab.org/nlab/show/coreflective+subcategory}{coreflective
subcategory} of the category of intersection-based spaces.
\end{itemize}
As we can see intersection-based spaces and topological spaces are very
similar and so far intersection-based spaces didn't provide us with
anything new. It is the following definition where intersection-based
spaces provide something that their corresponding topological spaces my
not provide.
\begin{itemize}
\tightlist
\item
\textbf{Definition.} Let \(X\) and \(Y\) be intersection-based spaces
with intersection-bases \(\mathcal{B}_X\) respectively
\(\mathcal{B}_Y\). A continuous map \(\varphi \colon X \rightarrow Y\)
is \emph{Galois} if for all \(U \in \mathcal{B}_X\) the set
\(\set{V}{\mathcal{B}_Y}{U \subseteq \varphi^{-1} (V)}\) has a minimum
which we denote by \(\varphi^{+1} (U)\).
\end{itemize}
The reason we name such a map \(\varphi\) Galois is that
\(\varphi^{+1}\) and \(\varphi^{-1}\) then form a
\href{https://en.wikipedia.org/wiki/Galois_connection\#.28Monotone.29_Galois_connection}{monotone
Galois connection} \(\varphi^{+1} \dashv \varphi^{-1}\).
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{4}
\tightlist
\item
\textbf{Lemma.} Let \(\varphi \colon X \rightarrow Y\) and
\(\psi \colon Y \rightarrow Z\) be continuous and Galois, then
\(\psi \circ \varphi\) is Galois and
\((\psi \circ \varphi)^{+1} = \psi^{+1} \circ \varphi^{+1}\).
\end{enumerate}
\begin{itemize}
\tightlist
\item
\emph{Proof.} This follows from a general statement about Galois
connections, see for example (Erné et al.
\protect\hyperlink{ref-MR1277847}{1993}, proposition 2).
\end{itemize}
These are all the point-set topological notions we need, so we can start
with precosheaves.
\begin{itemize}
\tightlist
\item
\textbf{Definition} (Set-valued Precosheaves)\textbf{.} Let \(X\) be
an intersection-based space with intersection base \(\mathcal{B}\). A
set-valued precosheaf \(F\) on \(X\) is a functor from
\(\mathcal{B}\), partially ordered by inclusions, to the category of
sets.
\end{itemize}
The reader may already guess that for an intersection-based space \(X\)
we will also augment the class of set-valued precosheaves on \(X\) with
the structure of a category.
\begin{itemize}
\item
\textbf{Definition.} Let \(F\) and \(G\) be precosheaves on some
intersection-based space \(X\). A homomorphism
\(\alpha \colon F \rightarrow G\) is a natural transformation from
\(F\) to \(G\).
Composition of homomorphisms is given by composition of natural
transformations.
\end{itemize}
Now let \(\varphi \colon X \rightarrow Y\) be a continuous map between
intersection-based spaces. We associate to \(\varphi\) a functor from
the category of set-valued precosheaves on \(X\) to the category of
precosheaves on \(Y\).
\begin{itemize}
\tightlist
\item
\textbf{Definition} (Pushforward)\textbf{.} For a precosheaf \(F\) on
\(X\) we set \(\varphi_* F := F \circ \varphi^{-1}\) and for a
homomorphism \(\alpha \colon F \rightarrow G\) we set
\(\varphi_* \alpha := \alpha \circ \varphi^{-1}\). Here we view
\(\varphi^{-1}\) as a monotone map from the intersection-base of \(Y\)
to the intersection-base of \(X\). We name \(\varphi_* F\) the
\emph{pushforward of \(F\) by \(\varphi\)}.
\end{itemize}
We note that \(\varphi_*\) is a functor from the category of
precosheaves on \(X\) to the category of precosheaves on \(Y\). Now let
\(\psi \colon Y \rightarrow Z\) be another continuous map between
intersection-based spaces.
\begin{itemize}
\tightlist
\item
\textbf{Lemma.} We have
\((\psi \circ \varphi)_* = \psi_* \circ \varphi_*\).
\end{itemize}
Now suppose \(\varphi\) and \(\psi\) are Galois. We describe a functor
in the other direction.
\begin{itemize}
\tightlist
\item
\textbf{Definition} (Pullback)\textbf{.} For a precosheaf \(G\) on
\(Y\) we set \(\varphi_p G := G \circ \varphi^{+1}\) and for a
homomorphism \(\alpha \colon F \rightarrow G\) we set
\(\varphi_p \alpha := \alpha \circ \varphi^{+1}\). We name
\(\varphi_p G\) the \emph{pullback of \(G\) by \(\varphi\)}.
\end{itemize}
We note that \(\varphi_p\) is a functor from the category of
precosheaves on \(Y\) to the category of precosheaves on \(X\).
\begin{itemize}
\item
\textbf{Lemma.} We have
\((\psi \circ \varphi)_p = \varphi_p \circ \psi_p\).
\item
\emph{Proof.} This follows from lemma 5.
\item
\textbf{Definition.} For all distinguished open subsets
\(U \subseteq X\) we have
\(U \subseteq (\varphi^{+1} \circ \varphi^{-1})(U)\) and this yields a
natural homomorphism
\(\eta^{\varphi}_F \colon F \rightarrow \varphi_p \varphi_* F\) for
any precosheaf \(F\) on \(X\).
Conversely we have
\((\varphi^{-1} \circ \varphi^{+1})(V) \subseteq V\) for all
distinguished open subsets \(V \subseteq Y\). This induces a natural
homomorphism
\(\varepsilon^{\varphi}_G \colon \varphi_* \varphi_p G \rightarrow G\)
for any precosheaf \(G\) on \(Y\).
\end{itemize}
If \(\varphi\) is not Galois then a functor like \(\varphi_p\) still
exists, see for example (Stacks Project Authors
\protect\hyperlink{ref-stacks-project}{2017},
\href{http://stacks.math.columbia.edu/tag/008C}{tag 008C}), but it is
not as easy to define and not as easy to work with. In particular the
previous lemma would not hold in this form and such compositions would
invoke some subtleties. This is the reason we introduced
intersection-based spaces in the first place.
\begin{itemize}
\tightlist
\item
\textbf{Definition} (Restriction)\textbf{.} For a subspace \(Y\) of an
intersection-based space \(X\) whose inclusion is Galois and a
precosheaf \(F\) on \(X\) we denote the pullback of \(F\) by the
inclusion by \(F |_Y\).
\end{itemize}
\section{Monoidal Posets for
1D-Interleavings}\label{monoidal-posets-for-1d-interleavings}
Before we defined \protect\hyperlink{join-trees}{interleavings of join
trees} we introduced the poset \(D^{\perp}\) and the two weightings
\(\epsilon'\) and \(\epsilon''\) on \(D^{\perp}\). Morozov, Beketayev,
and Weber (\protect\hyperlink{ref-morozov2013}{2013}) used a more ad hoc
approach and we justified our approach by also introducing the relative
interleaving distance. With Reeb graphs we will do something similar and
we introduce more formalism than de Silva, Munch, and Patel
(\protect\hyperlink{ref-deSilva2016}{2016}). The reason for this is two
fold. Starting from the approach by de Silva, Munch, and Patel
(\protect\hyperlink{ref-deSilva2016}{2016}) the author added one layer
of formalism to define the relative interleaving distance and then
another layer of formalism, which may help with the computation of these
interleaving distances. The nice thing about join trees is that we can
get both benefits with just one additional layer of formalism whereas
here we need two layers, so that a dedicated section is required. In
other words we beg the reader to bear with us for one more section until
we get to the absolute and relative interleaving distances of Reeb
graphs.
\begin{itemize}
\tightlist
\item
\textbf{Definition.} Let
\(D := \set{(a, b)}{[-\infty, \infty) \times (-\infty, \infty]}{a \leq b}\)
then \(D\) is a monoid by component-wise addition. Moreover we set
\(\mathbf{o} := (0, 0)\) and we define a partial order \(\preceq\) on
\(D\) by
\((x, y) \preceq (x', y') : \Leftrightarrow x \geq x' \wedge y \leq y' .\)
\end{itemize}
A set augmented with a partial ordering and a monotone monoid structure
like \(D\), we call a \emph{monoidal poset}. Moreover \(D \times D\) is
a monoidal poset with the product ordering and component-wise addition.
With some abuse of notation we write \((a, b; c, d)\) for points
\(((a, b), (c, d)) \in D \times D\). Next we define three monoidal
sub-posets of \(D \times D\).
\begin{itemize}
\tightlist
\item
\textbf{Definition.} We set\\
\(\mathcal{D} := \set{(a, b; c, d)}{D \times D} {a + c \leq 0 \leq b + d}\),\\
\(\triangledown := \set{(a, b; c, d)}{\mathcal{D}} {c + b = 0 = a + d}\),
and\\
\(\blacktriangledown := \set{(a, b; c, d)}{\triangledown} {a + b = 0}\).
\end{itemize}
So now we have the chain of monoidal posets
\(\blacktriangledown \subset \triangledown \subset \mathcal{D}\). For
each of the two inclusions we aim to describe a monotone subadditive map
in the other direction.
\begin{itemize}
\tightlist
\item
\textbf{Definition.} For \((a, b; c, d) \in \mathcal{D}\) we set
\(\delta((a, b; c, d)) := (-d', b'; -b', d')\) where
\(b' = \max \{-c, b\}\) and \(d' = \max \{-a, d\}\). And for
\((a, b; c, d) \in \triangledown\) we set
\(\gamma((a, b; c, d)) := (-\varepsilon, \varepsilon; -\varepsilon, \varepsilon)\)
where \(\varepsilon = \max \{b, d\}\).
\end{itemize}
\begin{itemize}
\item
\textbf{Lemma.} For all \(\mathbf{A} \in \mathcal{D}\) and
\(\mathbf{B} \in \triangledown\) with
\(\mathbf{A} \preceq \mathbf{B}\) we have
\(\delta(\mathbf{A}) \preceq \mathbf{B}\).
Similarly we have \(\gamma(\mathbf{A}) \preceq \mathbf{B}\) for all
\(\mathbf{A} \in \triangledown\) and
\(\mathbf{B} \in \blacktriangledown\) with
\(\mathbf{A} \preceq \mathbf{B}\).
\end{itemize}
In other words \(\delta\) and \(\gamma\) are lower adjoints to the
corresponding inclusions in the sense of
\href{https://en.wikipedia.org/wiki/Galois_connection\#.28Monotone.29_Galois_connection}{monotone
Galois connections}. Now we will first describe a weighting on
\(\triangledown\) and then we will harness these two maps to describe
two weightings on \(\mathcal{D}\).
\begin{itemize}
\tightlist
\item
\textbf{Definition.} We set
\(\epsilon \colon \triangledown \rightarrow [0, \infty], (a, b; c, d) \mapsto \frac{1}{2} (b + d)\).
\end{itemize}
We note that \(\epsilon\) is monotone and additive. Moreover the
restriction \(\epsilon |_{\blacktriangledown}\) is an isomorphism of
monoidal posets. The two different weightings on \(\mathcal{D}\) are now
\(\epsilon \circ \gamma \circ \delta\) and \(\epsilon \circ \delta\).
Next we provide explicit formulas for these two weightings.
\begin{itemize}
\tightlist
\item
\textbf{Lemma.} For all \((a, b; c, d) \in \mathcal{D}\) we have \[
(\epsilon \circ \gamma \circ \delta)((a, b; c, d)) =
\max \{-a, b, -c, d\}
\] and \[
(\epsilon \circ \delta)((a, b; c, d)) =
\frac{1}{2} (\max \{-c, b\} + \max \{-a, d\}) .
\]
\end{itemize}
\section{Interleaving Reeb Graphs}\label{interleaving-reeb-graphs}
In this section we define the interleaving distance of Reeb graphs due
to de Silva, Munch, and Patel
(\protect\hyperlink{ref-deSilva2016}{2016}). Strictly speaking it is
somewhat misleading to name this the interleaving distance of Reeb
graphs because we are not comparing the Reeb graphs directly, instead we
compare what we name the Reeb precosheaf\footnote{de Silva, Munch, and
Patel (\protect\hyperlink{ref-deSilva2016}{2016}) actually name it the
Reeb cosheaf, because in their setup, using locally connected spaces,
it always is a cosheaf, a precosheaf with further properties.}. de
Silva, Munch, and Patel (\protect\hyperlink{ref-deSilva2016}{2016})
discuss very thoroughly, why we may do this and later they also
translate this into a more geometric comparison of Reeb graphs. We
define this Reeb precosheaf somewhat differently from the way it is
defined in this article. Using the notion of an intersection-based space
we may say that de Silva, Munch, and Patel
(\protect\hyperlink{ref-deSilva2016}{2016}) define the Reeb precosheaf
as a precosheaf on the intersection-based space, that has the real
numbers as an underlying set and the open intervals as distinguished
open subsets. We will use a different space, but all of the
distinguished open subsets of this space, except for three, can be
identified with an open interval. Now because precosheaves are just
functors on the distinguished open subsets, this is pretty much the same
data. And the reason we can't identify all distinguished open subsets
with an interval is that we work with \(\overline{\R}\) instead of
\(\R\), in some sense \(\overline{\R}\) has three more open intervals
than \(\R\). Now we begin with defining this intersection-based space.
\begin{itemize}
\item
\textbf{Definition.} We define \(\overline{\R}_{\infty}\) to be the
space that has \(\overline{\R}\) as an underlying set and
\(\{\overline{\R}\} \cup \{(a, \infty] ~ | ~ a \in \overline{\R}\}\)
as it's intersection-base.
Similarly we define \(\overline{\R}_{-\infty}\) to be the space with
the same underlying set and
\(\{\overline{\R}\} \cup \{[-\infty, b) ~ | ~ b \in \overline{\R}\}\)
as it's intersection-base.
Finally we set
\(\Ec := \overline{\R}_{\infty} \times \overline{\R}_{-\infty}\) and
\(\overline{D} := \set{(x, y)}{\Ec}{x \leq y}\).
\end{itemize}
We note that any functor from the category of topological spaces to the
category of sets defines a precosheaf on any topological space \(X\),
since we may equip any open subset \(U \subseteq X\) with the subspace
topology and since inclusions of subsets are continuous with respect to
this topology. In the following definition we define a functor on the
category of topological spaces and in this way also a precosheaf on any
topological space.
\begin{itemize}
\item
\textbf{Definition.} For topological space \(X\) we define
\(\Lambda(X)\) to be the set of connected components of \(X\).
For a continuous map \(\varphi \colon X \rightarrow Y\) we define
\(\Lambda(\varphi)\) to be the induced map from \(\Lambda(X)\) to
\(\Lambda(Y)\).
\end{itemize}
Now let \(f \colon X \rightarrow \overline{\R}\) and
\(g \colon Y \rightarrow \overline{\R}\) be continuous functions, let
\(\varphi \colon f \rightarrow g\) be a homomorphism in the category of
\(\overline{\R}\)-spaces, and let
\(\Delta \colon \overline{\R} \rightarrow \overline{D}, t \mapsto (t, t)\).
For a distinguished open subset \(U \subseteq \overline{D}\) let
\(\varphi |_{(\Delta \circ f)^{-1} (U)} \colon (\Delta \circ f)^{-1} (U) \rightarrow (\Delta \circ g)^{-1} (U)\)
be the restriction of \(\varphi\) to \((\Delta \circ f)^{-1} (U)\).
\begin{itemize}
\item
\textbf{Definition} (Reeb Precosheaf)\textbf{.} We set
\(\mathcal{C} f := (\Delta \circ f)_* \Lambda\) and name this the
\emph{Reeb precosheaf of \(f\)}.
Moreover we define a homomorphism \(\mathcal{C} \varphi\) from
\(\mathcal{C} f\) to \(\mathcal{C} g\). For a distinguished open
subset \(U \subseteq \overline{D}\) we set
\((\mathcal{C} \varphi)_U := \Lambda \big(\varphi |_{(\Delta \circ f)^{-1} (U)}\big)\).
\end{itemize}
With these definitions \(\mathcal{C}\) defines a functor from the
category of \(\overline{\R}\)-spaces to the category of set-valued
precosheaves on \(\overline{D}\). Now assume that \(g\) is a
constructible \(\overline{\R}\)-space\footnote{see the
\protect\hyperlink{constructible-spaces}{first appendix} for our
definition of a constructible \(\overline{\R}\)-space}. We discuss the
relationship of the Reeb graph \(\mathcal{R} g\) and the Reeb precosheaf
\(\mathcal{C} g\).
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{5}
\tightlist
\item
\textbf{Lemma.} The homomorphism \((\mathcal{C} \circ \pi)_g\) from
\(\mathcal{C} g\) to \(\mathcal{C} \mathcal{R} g\) is an isomorphism
of precosheaves.
\end{enumerate}
The previous lemma implies that the isomorphism class of
\(\mathcal{C} g\) is determined by \(\mathcal{R} g\). Next we will see
that the converse is also true.
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{6}
\tightlist
\item
\textbf{Lemma.} Let
\(\beta \colon \mathcal{C} f \rightarrow \mathcal{C} g\) be a
homomorphism of precosheaves, then there is a unique homomorphism
\(\alpha \colon f \rightarrow \mathcal{R} g\) of
\(\overline{\R}\)-spaces such that the diagram \[
\xymatrix@+=3pc{
\mathcal{C} f
\ar[d]_{\mathcal{C} \alpha}
\ar[dr]^{\beta}
\\
\mathcal{C} \mathcal{R} g
&
\mathcal{C} g
\ar[l]^{(\mathcal{C} \circ \pi)_g}
}
\] commutes.
\end{enumerate}
\begin{itemize}
\tightlist
\item
\emph{Remark.} One can rephrase the previous lemma in the terminology
of category theory in the following way. The homomorphism
\((\mathcal{C} \circ \pi)_g^{-1}\) yields a representation of the
contravariant functor \(\hom (\mathcal{C} \_, \mathcal{C} g)\). A vast
generalization of this statement has been provided by Funk
(\protect\hyperlink{ref-MR1322801}{1995}).
\end{itemize}
The previous two lemmata have the following
\begin{itemize}
\item
\textbf{Corollary.} The map \[\mathcal{C} (\_) \colon
\hom (f, \mathcal{R} g) \rightarrow
\hom (\mathcal{C} f, \mathcal{C} \mathcal{R} g),
\alpha \mapsto \mathcal{C} \alpha\] is a bijection.
\item
\emph{Proof.} First we note that the post-composition
\((\mathcal{C} \circ \pi)_g^{-1} \circ (\_)\) yields a bijection from
\(\hom (\mathcal{C} f, \mathcal{C} \mathcal{R} g)\) to
\(\hom (\mathcal{C} f, \mathcal{C} g)\). Now the previous lemma states
that the composition
\((\mathcal{C} \circ \pi)_g^{-1} \circ \mathcal{C} (\_)\) is a
bijection as well. Thus also \(\mathcal{C} (\_)\) is a bijection.
\end{itemize}
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{7}
\tightlist
\item
\textbf{Corollary.} The functor \(\mathcal{C}\) is
\href{https://ncatlab.org/nlab/show/full+functor}{full} and
\href{https://ncatlab.org/nlab/show/faithful+functor}{faithful} on the
\href{https://ncatlab.org/nlab/show/full+subcategory}{full
subcategory} of Reeb graphs of constructible \(\overline{\R}\)-spaces.
\end{enumerate}
The previous corollary implies that the isomorphism class of
\(\mathcal{R} g\) is determined by the isomorphism class of
\(\mathcal{C} \mathcal{R} g\) and this class in turn is determined by
\(\mathcal{C} g\), hence \(\mathcal{C} g\) determines the isomorphism
class of \(\mathcal{R} g\).
In summary we may associate to any \(\overline{\R}\)-space a set-valued
precosheaf, the Reeb precosheaf. In the following subsection we define
two interleaving distances for set-valued precosheaves on
\(\overline{D}\). And for constructible \(\overline{\R}\)-spaces we may
also refer to the interleaving distances of the Reeb precosheaves as
interleaving distances of Reeb graphs. This is justified by the fact
that de Silva, Munch, and Patel
(\protect\hyperlink{ref-deSilva2016}{2016}) also define an interleaving
distance of Reeb graphs, that is equal to the interleaving distance of
the Reeb precosheaves for constructible \(\overline{\R}\)-spaces.
\hypertarget{interleaving-precosheaves-on-d}{\subsection{\texorpdfstring{Interleaving
Precosheaves on
\emph{D}}{Interleaving Precosheaves on D}}\label{interleaving-precosheaves-on-d}}
In the \protect\hyperlink{precosheaves}{interlude on precosheaves} we
described how continuous and Galois maps between intersection-based
spaces yield functors between the corresponding categories of
precosheaves. We start by describing some self-maps on \(\overline{D}\)
to yield us endofunctors on the category of precosheaves on
\(\overline{D}\).
\begin{itemize}
\tightlist
\item
\textbf{Definition.} For \(a \in \R\) we define
\(s^a \colon \overline{\R} \rightarrow \overline{\R}, t \mapsto t + a\)\\
and we set
\(s^{\pm \infty} \colon \overline{\R} \rightarrow \overline{\R}, t \mapsto \pm \infty\).
\end{itemize}
We note that \(s^a\) is continuous and Galois on
\(\overline{\R}_{\infty}\) for \(- \infty \leq a < \infty\) and on
\(\overline{\R}_{- \infty}\) for \(- \infty < a \leq \infty\). Thus the
following definition yields a continuous and Galois self-map on \(\Ec\)
for all \((a, b) \in D\).
\begin{itemize}
\tightlist
\item
\textbf{Definition.} For \((a, b) \in D\) we set
\(S^{(a, b)} := (s^a \circ \pi^1) \times (s^b \circ \pi^2)\).
\end{itemize}
More explicitly we have \(S^{(a, b)} (x, y) = (s^a (x), s^b (y))\) for
all \((a, b) \in D\) and \(x, y \in \overline{\R}\). For all
\(\mathbf{a} \in D\) we have
\(S^{\mathbf{a}} \big(\overline{D}\big) \subseteq \overline{D}\), hence
\(S^{\mathbf{a}}\) also defines a continuous and Galois self-map on
\(\overline{D}\). Now let \(F\) be a set-valued precosheaf on
\(\overline{D}\). Using the definitions from the
\protect\hyperlink{precosheaves}{interlude on precosheaves} we get the
precosheaf \(S^{\mathbf{a}}_p F\) for any \(\mathbf{a} \in D\). Now for
\(\mathbf{o} \preceq \mathbf{a}\) and any distinguished open subset
\(U \subseteq \overline{D}\) we have
\(U \subseteq (S^{\mathbf{a}})^{+1} (U)\), hence the precosheaf \(F\)
itself yields a map from \(F(U)\) to \(S^{\mathbf{a}}_p F (U)\). Now
\((S^{\mathbf{a}})^{+1}\) is monotone and thus these maps describe a
homomorphism from \(F\) to \(S^{\mathbf{a}}_p F\).
\begin{itemize}
\tightlist
\item
\textbf{Definition.} We denote the previously described homomorphism
by\\
\(\Sigma^{\mathbf{a}}_F \colon F \rightarrow S^{\mathbf{a}}_p F\).
\end{itemize}
We note that \(\Sigma^{\mathbf{a}}\) is a
\href{https://en.wikipedia.org/wiki/Natural_transformation\#Definition}{natural
transformation} from the identity functor \(\id\) to
\(S^{\mathbf{a}}_p\). With these definitions in place we can define
interleavings of precosheaves. To this end let \(F\) and \(G\) be
precosheaves on \(\overline{D}\).
\begin{itemize}
\item
\textbf{Definition.} For \((\mathbf{a}, \mathbf{b}) \in \mathcal{D}\)
an \emph{\((\mathbf{a}, \mathbf{b})\)-interleaving of \(F\) and \(G\)}
is a pair of homomorphisms
\(\varphi \colon F \rightarrow S^{\mathbf{a}}_p G\) and
\(\psi \colon G \rightarrow S^{\mathbf{b}}_p F\) such that \[
\xymatrix{
F
\ar@/^/[rr]^{\Sigma^{\mathbf{a} + \mathbf{b}}_F}
\ar[dr]_{\varphi}
& &
S^{\mathbf{a} + \mathbf{b}}_p F
\\
&
S^{\mathbf{a}}_p G
\ar[ru]_{S^{\mathbf{a}}_p \psi}
}
\] and \[
\xymatrix{
G
\ar@/^/[rr]^{\Sigma^{\mathbf{a} + \mathbf{b}}_G}
\ar[dr]_{\psi}
& &
S^{\mathbf{a} + \mathbf{b}}_p G
\\
&
S^{\mathbf{b}}_p F
\ar[ru]_{S^{\mathbf{b}}_p \varphi}
}
\] commute.
We say \emph{\(F\) and \(G\) are
\((\mathbf{a}, \mathbf{b})\)-interleaved} if there is an
\((\mathbf{a}, \mathbf{b})\)-interleaving of \(F\) and \(G\).
\end{itemize}
Now we use the weightings on \(\mathcal{D}\) we defined previously to
describe two interleaving distances for precosheaves on
\(\overline{D}\).
\begin{itemize}
\item
\textbf{Definition.} Let \(\mathcal{I}\) be the set of all
\((\mathbf{a}, \mathbf{b}) \in \mathcal{D}\) such that there is an
\((\mathbf{a}, \mathbf{b})\)-interleaving of \(F\) and \(G\).\\
Then we set
\(M (F, G) := \inf (\epsilon \circ \gamma \circ \delta) (\mathcal{I})\)
and \(\mu (F, G) := \inf (\epsilon \circ \delta) (\mathcal{I})\).
We name \(M (F, G)\) the \emph{absolute interleaving distance of \(F\)
and \(G\)} and \(\mu (F, G)\) the \emph{relative interleaving distance
of \(F\) and \(G\)}.
\end{itemize}
Now let \(f \colon X \rightarrow \R\) and \(g \colon Y \rightarrow \R\)
be continuous functions. At this point the next steps would be to proof
the triangle inequalities for \(M\) and \(\mu\) and to show, that the
interleaving distances \(M(\mathcal{C} f, \mathcal{C} g)\) and
\(\mu(\mathcal{C} f, \mathcal{C} g)\) really provide
\protect\hyperlink{lower-bounds}{lower bounds} to \(M(f, g)\)
respectively \(\mu(f, g)\) as we did for
\protect\hyperlink{join-trees}{join trees}. Instead we will derive these
results from more general statements however.
Nevertheless we can now repeat another question that we
\protect\hyperlink{lower-bounds}{pledged to address} in a more precise
way. In the \protect\hyperlink{join-trees}{beginning} we introduced the
interleaving distances of join trees \(\mathcal{R} \mathcal{E} f\) and
\(\mathcal{R} \mathcal{E} g\). Above we argued that the functors
\(\mathcal{R}\) and \(\mathcal{C}\) are closely related, so it seems
very reasonable to compare the interleavings distances of
\(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} g\) to those
of the precosheaves \(\mathcal{C} \mathcal{E} f\) and
\(\mathcal{C} \mathcal{E} g\). Later we will show the following
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{8}
\tightlist
\item
\textbf{Theorem.} If \(X\) and \(Y\) are smooth and compact manifolds,
then \[M_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g) =
M (\mathcal{C} \mathcal{E} f, \mathcal{C} \mathcal{E} g)\] and
\[\mu_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g) =
\mu (\mathcal{C} \mathcal{E} f, \mathcal{C} \mathcal{E} g) .\]
\end{enumerate}
\hypertarget{interleavings-in-d-categories}{\section{\texorpdfstring{Interleavings
in
\emph{D}-Categories}{Interleavings in D-Categories}}\label{interleavings-in-d-categories}}
Up to this point we have seen two notions of an interleaving, the first
for join trees and the second for precosheaves. In order to show theorem
9 we will use several more and to not repeatedly define new notions with
slight modifications we define a common generalization. The idea is to
formalize the additional structure, needed on a certain category
\(\mathbf{C}\), to define the notion of an interleaving between any two
objects in \(\mathbf{C}\).
\begin{itemize}
\tightlist
\item
\textbf{Definition} (Strict \(D\)-Categories)\textbf{.} A \emph{strict
\(D\)-category} is a category \(\mathbf{C}\) with a strict
\href{https://en.wikipedia.org/wiki/Monoidal_functor}{monoidal
functor} \(\mathcal{S}\) from \(D\) to the
\href{https://ncatlab.org/nlab/show/endofunctor}{category of
endofunctors} on \(\mathbf{C}\). We refer to \(\mathcal{S}\) as the
\emph{smoothing functor of \(\mathbf{C}\)}.
\end{itemize}
Now let \(\mathbf{C}\) be a strict \(D\)-category with smoothing functor
\(\mathcal{S}\) and let \(A\) and \(B\) be two objects in
\(\mathbf{C}\). It turns out that the smoothing functor \(\mathcal{S}\)
is all we need in order to define the notion of an interleaving between
\(A\) and \(B\).
\begin{itemize}
\item
\textbf{Definition} (Interleavings)\textbf{.} For
\((\mathbf{a}, \mathbf{b}) \in \mathcal{D}\) an
\emph{\((\mathbf{a}, \mathbf{b})\)-interleaving of \(A\) and \(B\)} is
a pair of homomorphisms
\(\varphi \colon A \rightarrow \mathcal{S}(\mathbf{a})(B)\) and
\(\psi \colon B \rightarrow \mathcal{S}(\mathbf{b})(A)\) such that the
diagrams \[
\xymatrix{
A
\ar@/^/[rr]^{\mathcal{S}(\mathbf{o} \preceq \mathbf{a} + \mathbf{b})_A \quad}
\ar[dr]|-{\varphi}
& &
\mathcal{S}(\mathbf{a} + \mathbf{b})(A)
\\
&
\mathcal{S}(\mathbf{a})(B)
\ar[ru]|-{\mathcal{S}(\mathbf{a})(\psi)}
}
\] and \[
\xymatrix{
B
\ar@/^/[rr]^{\mathcal{S}(\mathbf{o} \preceq \mathbf{a} + \mathbf{b})_B \quad}
\ar[dr]|-{\psi}
& &
\mathcal{S}(\mathbf{a} + \mathbf{b})(B)
\\
&
\mathcal{S}(\mathbf{b})(A)
\ar[ru]|-{\mathcal{S}(\mathbf{b})(\varphi)}
}
\] commute.
We say \emph{\(A\) and \(B\) are
\((\mathbf{a}, \mathbf{b})\)-interleaved} if there is an
\((\mathbf{a}, \mathbf{b})\)-interleaving of \(A\) and \(B\).
\end{itemize}
The two interleaving distances of \(A\) and \(B\) are defined similarly
to those of two precosheaves, we spell out the definitions nevertheless.
\begin{itemize}
\tightlist
\item
\textbf{Definition} (Interleaving Distances)\textbf{.} Let
\(\mathcal{I}\) be the set of all
\((\mathbf{a}, \mathbf{b}) \in \mathcal{D}\) such that there is an
\((\mathbf{a}, \mathbf{b})\)-interleaving of \(A\) and \(B\).\\
Then we set
\(M_{\mathcal{S}} (A, B) := \inf (\epsilon \circ \gamma \circ \delta) (\mathcal{I})\)
and
\(\mu_{\mathcal{S}} (A, B) := \inf (\epsilon \circ \delta) (\mathcal{I})\).
\end{itemize}
In the following example we show that interleavings of precosheaves and
the interleaving distances of precosheaves on \(\overline{D}\) are an
instance of the notions we defined here.
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{9}
\tightlist
\item
\emph{Example.} Let \(\mathcal{B}\) be the intersection-base of
\(\overline{D}\), then we may identify the monoidal poset of monotone
self-maps \(\selfm{\mathcal{B}}\) with the category of endofunctors on
\(\mathcal{B}\). Now let \(\mathbf{C}\) be the category of set-valued
precosheaves on \(\overline{D}\). We define the precomposition functor
\[
\tilde{\mathcal{S}} \colon \selfm{\mathcal{B}} \rightarrow \selfm{\mathbf{C}},
\begin{cases}
\begin{split}
T & \mapsto (F \mapsto F \circ T) \\
\eta & \mapsto (F \mapsto F \circ \eta) .
\end{split}
\end{cases}
\] We note that \(\tilde{\mathcal{S}}\) is a strict monoidal functor.
Moreover the map \[
\big(S^{(\_)}\big)^{+1} \colon D \rightarrow \selfm{\mathcal{B}},
\mathbf{a} \mapsto (S^{\mathbf{a}})^{+1}
\] is a homomorphism of monoidal posets, hence the functor
\(\mathcal{S} := \tilde{\mathcal{S}} \circ \big(S^{(\_)}\big)^{+1}\)
is strict monoidal as well. Now we observe that
\(\mathcal{S}(\mathbf{a}) = S^{\mathbf{a}}_p\) for
\(\mathbf{a} \in D\). And if \(\mathbf{o} \preceq \mathbf{a}\), then
\(\mathcal{S}(\mathbf{o} \preceq \mathbf{a}) = \Sigma^{\mathbf{a}}\).
\end{enumerate}
\hypertarget{properties-of-interleavings}{\subsection{Properties of
Interleavings}\label{properties-of-interleavings}}
Now let \(\mathbf{C}\) be a strict \(D\)-category with smoothing functor
\(\mathcal{S}\) and let \(A\) and \(B\) be objects of \(\mathbf{C}\). We
aim to provide some useful properties about interleavings in
\(\mathbf{C}\).
\begin{itemize}
\item
\textbf{Lemma} (Monotonicity)\textbf{.} For
\((\mathbf{a}, \mathbf{b}) \in \mathcal{D}\) let
\(\varphi \colon A \rightarrow \mathcal{S}(\mathbf{a})(B)\) and
\(\psi \colon B \rightarrow \mathcal{S}(\mathbf{b})(A)\) be an
\((\mathbf{a}, \mathbf{b})\)-interleaving of \(A\) and \(B\). Now
suppose we have \(\mathbf{c} \in D\) with
\(\mathbf{a} \preceq \mathbf{c}\). Then
\(\mathcal{S}(\mathbf{a} \preceq \mathbf{c})_B \circ \varphi\) and
\(\psi\) form an \((\mathbf{c}, \mathbf{b})\)-interleaving of \(A\)
and \(B\). Completely analogously
\(\mathcal{S}(\mathbf{b} \preceq \mathbf{d})_A \circ \psi\) and
\(\varphi\) yield an \((\mathbf{a}, \mathbf{d})\)-interleaving for any
\(\mathbf{d} \in D\) with \(\mathbf{b} \preceq \mathbf{d}\).
\item
\emph{Proof.} We consider the diagram \[
\xymatrix@C+=6pc@R+=4pc{
A
\ar[r]_{\mathcal{S}(\mathbf{o} \preceq \mathbf{a} + \mathbf{b})_A}
\ar[dr]_{\varphi}
\ar@/^2pc/[rr]^{
\mathcal{S}(\mathbf{o} \preceq \mathbf{c} + \mathbf{b})_A
}
&
\mathcal{S}(\mathbf{a} + \mathbf{b})(A)
\ar[r]_{
\mathcal{S}(\mathbf{a} + \mathbf{b} \preceq \mathbf{c} + \mathbf{b})_A
}
&
\mathcal{S}(\mathbf{c} + \mathbf{b})(A)
\\
&
\mathcal{S}(\mathbf{a})(B)
\ar[u]_{\mathcal{S}(\mathbf{a})(\psi)}
\ar[r]_{\mathcal{S}(\mathbf{a} \preceq \mathbf{c})_B}
&
\mathcal{S}(\mathbf{c})(B) .
\ar[u]_{\mathcal{S}(\mathbf{c})(\psi)}
}
\] The upper triangle commutes because \(\mathcal{S}\) is a functor
and the triangle on the left commutes by assumption. Further we have
\(\mathcal{S}(\mathbf{a} + \mathbf{b} \preceq \mathbf{c} + \mathbf{b}) = \mathcal{S}(\mathbf{a} \preceq \mathbf{c}) \circ \mathcal{S}(\mathbf{b})\),
since \(\mathcal{S}\) is strict monoidal and thus the square commutes
as \(\mathcal{S}(\mathbf{a} \preceq \mathbf{c})\) is a natural
transformation. Since all the inner triangles and the square commute
in the above diagram, the outer triangle commutes as well. The other
triangle, for
\(\mathcal{S}(\mathbf{a} \preceq \mathbf{c})_B \circ \varphi\) and
\(\psi\) to be an interleaving, also commutes, because we have
\(\mathcal{S}(\mathbf{a} + \mathbf{b} \preceq \mathbf{c} + \mathbf{b})_B \circ \mathcal{S}(\mathbf{o} \preceq \mathbf{a} + \mathbf{b})_B = \mathcal{S}(\mathbf{o} \preceq \mathbf{c} + \mathbf{b})_B\).
\end{itemize}
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{10}
\tightlist
\item
\textbf{Corollary.} Let \(\mathcal{I}\) be the set of all
\((\mathbf{a}, \mathbf{b}) \in \mathcal{D}\) such that \(A\) and \(B\)
are \((\mathbf{a}, \mathbf{b})\)-interleaved. Further let
\(\mathcal{I}' := \mathcal{I} \cap \triangledown\) and
\(\mathcal{I}'' := \mathcal{I} \cap \blacktriangledown\). Then we have
\(\mu_{\mathcal{S}} (A, B) = \inf \epsilon (\mathcal{I}')\) and
\(M_{\mathcal{S}} (A, B) = \inf (\epsilon \circ \gamma)(\mathcal{I}') = \inf \epsilon (\mathcal{I}'')\).
\end{enumerate}
\begin{itemize}
\tightlist
\item
\emph{Proof.} First we note that
\(\mathcal{I}' \subseteq \delta(\mathcal{I})\), since
\(\delta |_{\triangledown} = \id_{\triangledown}\). By the previous
lemma we also have \(\mathcal{I}' \supseteq \delta(\mathcal{I})\),
hence \(\mathcal{I}' = \delta(\mathcal{I})\). This implies
\(\mu_{\mathcal{S}} (A, B) = \inf \epsilon (\mathcal{I}')\) and
\(M_{\mathcal{S}} (A, B) = \inf (\epsilon \circ \gamma)(\mathcal{I}')\).
Similarly we have \(\mathcal{I}'' = \gamma(\mathcal{I}')\) and thus
\(M_{\mathcal{S}} (A, B) = \inf \epsilon (\mathcal{I}'')\).
\end{itemize}
We will now use this corollary to give more concise descriptions of the
interleaving distances. The reason we didn't define the interleaving
distances with these more concise descriptions in the first place is
that we believe, having those additional interleavings around, can help
with the computation of the interleaving distances. Now suppose
\((a, b; c, d) \in \triangledown\), then
\((a, b; c, d) = (-d, b; -b, d)\). Thus we have the bijection \[
\Phi \colon \triangledown \rightarrow D^{\perp}, (a, b; c, d) \mapsto (d, b)
\] with inverse \[
\Psi \colon D^{\perp} \rightarrow \triangledown, (a, b) \mapsto (-a, b; -b, a) .
\]
\begin{itemize}
\item
\textbf{Definition.} For \((a, b) \in D^{\perp}\) an
\emph{\((a, b)\)-interleaving of \(A\) and \(B\)} is a
\((-a, b; -b, a)\)-interleaving of \(A\) and \(B\).
If there is an \((a, b)\)-interleaving of \(A\) and \(B\), we say
\emph{\(A\) and \(B\) are \((a, b)\)-interleaved}.
\end{itemize}
With this definition we get a corollary to the previous corollary.
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{11}
\tightlist
\item
\textbf{Corollary.} Let \(\mathcal{J}\) be the set of all
\((a, b) \in D^{\perp}\) such that \(A\) and \(B\) are
\((a, b)\)-interleaved, then
\(\mu_{\mathcal{S}} (A, B) = \inf \epsilon' (\mathcal{J})\) and
\(M_{\mathcal{S}} (A, B) = \inf \epsilon'' (\mathcal{J})\).
\end{enumerate}
\begin{itemize}
\tightlist
\item
\emph{Proof.} Let \(\mathcal{I}'\) be as in the previous corollary. By
the above observations we have \(\mathcal{I}' = \Psi(J)\), thus in
conjunction with the previous corollary
\(\mu_{\mathcal{S}} (A, B) = \inf (\epsilon \circ \Psi)(\mathcal{J})\)
and
\(M_{\mathcal{S}} (A, B) = \inf (\epsilon \circ \gamma \circ \Psi)(\mathcal{J})\).
Now let \((a, b) \in D^{\perp}\) and \(\varepsilon = \max \{a, b\}\),
then we have
\((\epsilon \circ \Psi)((a, b)) = \epsilon (-a, b; -b, a) = \frac{1}{2}(b + a) = \epsilon' (a, b)\)
and \[
\begin{split}
(\epsilon \circ \gamma \circ \Psi)(a, b)
& =
(\epsilon \circ \gamma)(-a, b; -b, a) \\
& =
\epsilon (-\varepsilon, \varepsilon; -\varepsilon, \varepsilon) \\
& =
\varepsilon = \max \{a, b\} = \epsilon'' (a, b) .
\end{split}
\]
\end{itemize}
We further simplify the absolute interleaving distance of \(A\) and
\(B\).
\begin{itemize}
\item
\textbf{Defintion} (\(\varepsilon\)-Interleaving)\textbf{.} For
\(\varepsilon \geq 0\) an \emph{\(\varepsilon\)-interleaving of \(A\)
and \(B\)} is an \((\varepsilon, \varepsilon)\)-interleaving of \(A\)
and \(B\).
If there is an \(\varepsilon\)-interleaving of \(A\) and \(B\), we say
\emph{\(A\) and \(B\) are \(\varepsilon\)-interleaved}.
\end{itemize}
Now an \((\varepsilon, \varepsilon)\)-interleaving of \(A\) and \(B\) is
just a
\((-\varepsilon, \varepsilon; -\varepsilon, \varepsilon)\)-interleaving.
Further we have
\(\epsilon ((-\varepsilon, \varepsilon; -\varepsilon, \varepsilon)) = \varepsilon\).
And as noted earlier \(\epsilon |_{\blacktriangledown}\) is a bijection.
Thus we have yet another corollary to corollary 11.
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{12}
\tightlist
\item
\textbf{Corollary.} Let \(\mathcal{V}\) be the set of all
\(\varepsilon \geq 0\) such that \(A\) and \(B\) are
\(\varepsilon\)-interleaved. Then
\(M_{\mathcal{S}} (A, B) = \inf \mathcal{V}\).
\end{enumerate}
\begin{itemize}
\tightlist
\item
\emph{Proof.} Let \(\mathcal{I}''\) be as in the corollary 11. By the
above observations we have
\(\mathcal{I}'' = (\epsilon |_{\blacktriangledown})^{-1} (\mathcal{V})\).
In conjunction with the corollary 11 we get
\(M_{\mathcal{S}} (A, B) = \inf \epsilon \big((\epsilon |_{\blacktriangledown})^{-1} (\mathcal{V})\big) = \inf \mathcal{V} .\)
\end{itemize}
Next we proof a type of triangle inequality for both interleaving
distances. To this end let \(C\) be another object of \(\mathbf{C}\).
\begin{itemize}
\item
\textbf{Lemma.} Let
\((\mathbf{a}, \mathbf{b}), (\mathbf{c}, \mathbf{d}) \in \mathcal{D}\).
Further let
\(\varphi \colon A \rightarrow \mathcal{S}(\mathbf{a})(B)\) and
\(\psi \colon B \rightarrow \mathcal{S}(\mathbf{b})(A)\) be an
\((\mathbf{a}, \mathbf{b})\)-interleaving of \(A\) and \(B\) and let
\(\varphi' \colon B \rightarrow \mathcal{S}(\mathbf{c})(C)\) and
\(\psi' \colon C \rightarrow \mathcal{S}(\mathbf{d})(B)\) be a
\((\mathbf{c}, \mathbf{d})\)-interleaving of \(B\) and \(C\). Then
\(\mathcal{S}(\mathbf{a})(\varphi') \circ \varphi\) and
\(\mathcal{S}(\mathbf{d})(\psi) \circ \psi'\) form an
\((\mathbf{a} + \mathbf{c}, \mathbf{b} + \mathbf{d})\)-interleaving of
\(A\) and \(C\).
\item
\emph{Proof.} We consider the diagram \[
\xymatrix@C+=6pc@R+=4pc{
A
\ar[r]_{\mathcal{S}(\mathbf{o} \preceq \mathbf{a} + \mathbf{b})_A}
\ar[dr]_{\varphi}
\ar@/^2pc/[rr]^{
\mathcal{S}(\mathbf{o} \preceq
\mathbf{a} + \mathbf{b} + \mathbf{c} + \mathbf{d})_A
}
&
\mathcal{S}(\mathbf{a} + \mathbf{b})(A)
\ar[r]_{
\mathcal{S}(\mathbf{a} + \mathbf{b} \preceq
\mathbf{a} + \mathbf{b} + \mathbf{c} + \mathbf{d})_A
\quad
}
&
\mathcal{S}(\mathbf{a} + \mathbf{b} + \mathbf{c} + \mathbf{d})(A)
\\
&
\mathcal{S}(\mathbf{a})(B)
\ar[u]_{\mathcal{S}(\mathbf{a})(\psi)}
\ar[r]_{
\mathcal{S}(\mathbf{a} \preceq \mathbf{a} + \mathbf{c} + \mathbf{d})_B
\quad
}
\ar[dr]_{\mathcal{S}(\mathbf{a})(\varphi')}
&
\mathcal{S}(\mathbf{a} + \mathbf{c} + \mathbf{d})(B)
\ar[u]_{\mathcal{S}(\mathbf{a} + \mathbf{c} + \mathbf{d})(\psi)}
\\
& &
\mathcal{S}(\mathbf{a} + \mathbf{c})(C) .
\ar[u]_{\mathcal{S}(\mathbf{a} + \mathbf{c})(\psi')}
}
\] Now the upper triangle commute because \(\mathcal{S}\) is a functor
and the triangle on the left commutes by assumption. Further we have
\(\mathcal{S}(\mathbf{a}) \circ \mathcal{S}(\mathbf{o} \preceq \mathbf{c} + \mathbf{d}) = \mathcal{S}(\mathbf{a} \preceq \mathbf{a} + \mathbf{c} + \mathbf{d})\),
since \(\mathcal{S}\) is strict monoidal and thus the lower triangle
commutes. For the square to commute, we observe that
\(\mathcal{S}(\mathbf{a} + \mathbf{b} \preceq \mathbf{a} + \mathbf{b} + \mathbf{c} + \mathbf{d}) = \mathcal{S}(\mathbf{a} \preceq \mathbf{a} + \mathbf{c} + \mathbf{d}) \circ \mathcal{S}(\mathbf{b})\),
again because \(\mathcal{S}\) is strict monoidal. Since all inner
triangles and the square commute in the above diagram, the outer
triangle commutes as well. Now
\(\mathcal{S}(\mathbf{a} + \mathbf{c} + \mathbf{d}) = \mathcal{S}(\mathbf{a} + \mathbf{c}) \circ \mathcal{S}(\mathbf{d})\)
once again because \(\mathcal{S}\) is strict monoidal, hence \[
\begin{split}
\mathcal{S}(\mathbf{a} + \mathbf{c})(\mathcal{S}(
\mathbf{d})(\psi) \circ \psi'
) & =
\mathcal{S}(\mathbf{a} + \mathbf{c})(\mathcal{S}(\mathbf{d})(\psi)) \circ
\mathcal{S}(\mathbf{a} + \mathbf{c})(\mathcal{S}(\psi') \\
& =
\mathcal{S}(\mathbf{a} + \mathbf{c} + \mathbf{d})(\psi) \circ
\mathcal{S}(\mathbf{a} + \mathbf{c})(\mathcal{S}(\psi') .
\end{split}
\] If we now consider the large triangle on it's own and we substitute
the two vertical maps on the right with the left hand side of the
previous equation, then we obtain the first of the two triangles for
\(\mathcal{S}(\mathbf{a})(\varphi') \circ \varphi\) and
\(\mathcal{S}(\mathbf{d})(\psi) \circ \psi'\) to be an interleaving.
The proof that the second triangle commutes is completely analogous.
\end{itemize}
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{13}
\tightlist
\item
\textbf{Corollary} (Triangle Inequality)\textbf{.} We have \[
M_{\mathcal{S}} (A, C) \leq M_{\mathcal{S}} (A, B) + M_{\mathcal{S}} (B, C)
\] and \[
\mu_{\mathcal{S}} (A, C) \leq
\mu_{\mathcal{S}} (A, B) + \mu_{\mathcal{S}} (B, C) .
\]
\end{enumerate}
\hypertarget{homomorphisms-D-cat}{\subsection{\texorpdfstring{Homomorphisms
of
\emph{D}-Categories}{Homomorphisms of D-Categories}}\label{homomorphisms-D-cat}}
After introducing the notion of a strict \(D\)-category, we seek ways to
relate different \(D\)-categories and their interleavings to each other.
To this end let \(\mathbf{C}\) and \(\mathbf{C}'\) be strict
\(D\)-categories with smoothing functor \(\mathcal{S}\) respectively
\(\mathcal{S}'\).
\begin{itemize}
\item
\textbf{Definition} (1-Homomorphism)\textbf{.} A
\emph{\(1\)-homomorphism of strict \(D\)-categories from
\(\mathbf{C}\) to \(\mathbf{C}'\)} is a functor
\(F \colon \mathbf{C} \rightarrow \mathbf{C}'\) such that \[
\xymatrix{
\mathbf{C}
\ar[r]^{\mathcal{S}(\mathbf{a})}
\ar[d]_F
&
\mathbf{C}
\ar[d]^F
\\
\mathbf{C}'
\ar[r]_{\mathcal{S}'(\mathbf{a})}
&
\mathbf{C}'
}
\] and \[
\xymatrix@C+=6pc@R+=5pc{
\mathbf{C}
\rtwocell<6>_{\mathcal{S}(\mathbf{b})}^{\mathcal{S}(\mathbf{a})}
{\qquad ~ \mathcal{S}(\mathbf{a} \preceq \mathbf{b})}
\ar[d]_F
&
\mathbf{C}
\ar[d]^F
\\
\mathbf{C}'
\rtwocell<6>_{\mathcal{S}'(\mathbf{b})}^{\mathcal{S}'(\mathbf{a})}
{\qquad ~ \, \mathcal{S}'(\mathbf{a} \preceq \mathbf{b})}
&
\mathbf{C}'
}
\] commute for all \(\mathbf{a}, \mathbf{b} \in D\) with
\(\mathbf{a} \preceq \mathbf{b}\).
\item
\emph{Remark.} We read the second diagram of the above definition as
\(F \circ \mathcal{S} (\mathbf{a} \preceq \mathbf{b}) = \mathcal{S}' (\mathbf{a} \preceq \mathbf{b}) \circ F\).
\end{itemize}
Now let \(F \colon \mathbf{C} \rightarrow \mathbf{C}'\) be a
\(1\)-homomorphism and let \(A\) and \(B\) be objects of \(\mathbf{C}\).
\begin{itemize}
\tightlist
\item
\textbf{Lemma.} Let
\(\varphi \colon A \rightarrow \mathcal{S}(\mathbf{a})(B)\) and
\(\psi \colon B \rightarrow \mathcal{S}(\mathbf{b})(A)\) be an
\((\mathbf{a}, \mathbf{b})\)-interleaving for some
\((\mathbf{a}, \mathbf{b}) \in \mathcal{D}\), then \(F(\varphi)\) and
\(F(\psi)\) form an \((\mathbf{a}, \mathbf{b})\)-interleaving in
\(\mathbf{C}'\).
\end{itemize}
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{14}
\tightlist
\item
\textbf{Corollary.} We have
\(M_{\mathcal{S}'} (F(A), F(B)) \leq M_{\mathcal{S}} (A, B)\) and
\(\mu_{\mathcal{S}'} (F(A), F(B)) \leq \mu_{\mathcal{S}} (A, B)\).
\end{enumerate}
\begin{itemize}
\tightlist
\item
\textbf{Lemma.} Now suppose that \(F\) is
\href{https://ncatlab.org/nlab/show/faithful+functor}{faithful} as a
functor from \(\mathbf{C}\) to \(\mathbf{C}'\) and that
\(\varphi \colon A \rightarrow \mathcal{S}(\mathbf{a})(B)\) and
\(\psi \colon B \rightarrow \mathcal{S}(\mathbf{b})(A)\) are arbitrary
homomorphisms for some \((\mathbf{a}, \mathbf{b}) \in \mathcal{D}\),
with \(F(\varphi)\) and \(F(\psi)\) an
\((\mathbf{a}, \mathbf{b})\)-interleaving of \(F(A)\) and \(F(B)\).
Then \(\varphi\) and \(\psi\) are an
\((\mathbf{a}, \mathbf{b})\)-interleaving as well.
\end{itemize}
The previous two lemmata have the following
\begin{itemize}
\item
\textbf{Corollary.} If \(F\) is
\href{https://ncatlab.org/nlab/show/full+functor}{full} and
\href{https://ncatlab.org/nlab/show/faithful+functor}{faithful}, then
\(F\) induces a bijection between the
\((\mathbf{a}, \mathbf{b})\)-interleavings of \(A\) and \(B\) and the
\((\mathbf{a}, \mathbf{b})\)-interleavings of \(F(A)\) and \(F(B)\)
for any \((\mathbf{a}, \mathbf{b}) \in \mathcal{D}\).
\item
\textbf{Corollary.} If \(F\) is full and faithful we have
\(M_{\mathcal{S}'} (F(A), F(B)) = M_{\mathcal{S}} (A, B)\) and
\(\mu_{\mathcal{S}'} (F(A), F(B)) = \mu_{\mathcal{S}} (A, B)\).
\end{itemize}
We also note that we can compose \(1\)-homomorphisms. To this end let
\(\mathbf{C}''\) be another strict \(D\)-category.
\begin{itemize}
\tightlist
\item
\textbf{Lemma.} Let \(G \colon \mathbf{C}' \rightarrow \mathbf{C}''\)
be another \(1\)-homomorphism, then \(G \circ F\) is a
\(1\)-homomorphism from \(\mathbf{C}\) to \(\mathbf{C}''\).
\end{itemize}
Now we defined \(1\)-homomorphisms as functors with special properties.
For any two functors \(F\) and \(G\) from \(\mathbf{C}\) to
\(\mathbf{C}'\) we have the class of natural transformations from \(F\)
to \(G\). Now suppose \(F\) and \(G\) are \(1\)-homomorphisms, then
\(F\) and \(G\) are in some sense compatible with \(\mathcal{S}\) and
\(\mathcal{S}'\). We name a natural transformation from \(F\) to \(G\),
that is compatible with \(\mathcal{S}\) and \(\mathcal{S}'\), a
\emph{\(2\)-homomorphism from \(F\) to \(G\)}.
\begin{itemize}
\item
\textbf{Definition} (2-Homomorphism) \textbf{.} A
\emph{\(2\)-homomorphism of strict \(D\)-categories from \(F\) to
\(G\)} is a natural transformation \(\eta \colon F \Rightarrow G\)
such that \[
\xymatrix@+=3pc{
\mathbf{C}
\ar[r]^{\mathcal{S}(\mathbf{a})}
\dtwocell<4>_F^G{^\eta}
&
\mathbf{C}
\dtwocell<4>_F^G{^\eta}
\\
\mathbf{C}'
\ar[r]_{\mathcal{S}'(\mathbf{a})}
&
\mathbf{C}'
}
\] commutes for all \(\mathbf{a} \in D\).
\item
\emph{Remark.} We read the diagram of the previous definition as
\(\eta \circ \mathcal{S} (\mathbf{a}) = \mathcal{S}' (\mathbf{a}) \circ \eta\).
This definition does not include the condition
\(\eta \circ \mathcal{S} (\mathbf{a} \preceq \mathbf{b}) = \mathcal{S}' (\mathbf{a} \preceq \mathbf{b}) \circ \eta\)
for \(\mathbf{a} \preceq \mathbf{b}\), where \(\circ\) is the
\href{https://ncatlab.org/nlab/show/Godement+product}{Godement
product} of natural transformations. The reason is, that this equation
follows from the previous two definitions. If we choose one of the two
formulas for the Godement product of \(\eta\) and
\(\mathcal{S} (\mathbf{a} \preceq \mathbf{b})\) and rewrite the term
using the previous two definitions, then we obtain the other of the
two formulas for the Godement product of
\(\mathcal{S}' (\mathbf{a} \preceq \mathbf{b})\) and \(\eta\).
\end{itemize}
Just like we can compose natural transformations we can also compose
\(2\)-homomorphisms.
\begin{itemize}
\tightlist
\item
\textbf{Lemma.} Let \(\eta \colon F \Rightarrow G\) and
\(\theta \colon G \Rightarrow H\) be \(2\)-homomorphisms, then
\(\theta \circ \eta\) is a \(2\)-homomorphism as well.
\end{itemize}
Moreover we can compose \(1\)-homomorphisms with \(2\)-homomorphisms and
vice versa.
\begin{itemize}
\item
\textbf{Lemma.} Let \(F\) and \(G\) be \(1\)-homomorphisms from
\(\mathbf{C}\) to \(\mathbf{C}'\), let \(\eta \colon F \Rightarrow G\)
be a \(2\)-homomorphism, and let \(H\) be a \(1\)-homomorphism from
\(\mathbf{C}'\) to \(\mathbf{C}''\), then the composition
\(H \circ \eta\), pictorially \[
\xymatrix{
\mathbf{C}
\rtwocell^F_G{\eta}
&
\mathbf{C}'
\ar[r]^H
&
\mathbf{C}'' ,
}
\] is \(2\)-homomorphism from \(H \circ F\) to \(H \circ G\).
Similarly if \(F\) and \(G\) are \(1\)-homomorphisms from
\(\mathbf{C}'\) to \(\mathbf{C}''\) and if \(H\) is a
\(1\)-homomorphism from \(\mathbf{C}\) to \(\mathbf{C}'\), then the
composition \(\eta \circ H\), pictorially \[
\xymatrix{
\mathbf{C}
\ar[r]^H
&
\mathbf{C}'
\rtwocell^F_G{\eta}
&
\mathbf{C}'' ,
}
\] is again a \(2\)-homomorphism.
\item
\emph{Remark.} Altogether we obtain the structure of a
\href{https://ncatlab.org/nlab/show/strict+2-category}{strict
2-category} on the collection of all strict \(D\)-categories.
\end{itemize}
\section{Positive
Persistence-Enhancements}\label{positive-persistence-enhancements}
In the previous section we defined strict \(D\)-categories,
interleavings of objects in \(D\)-categories, and showed that
interleavings of precosheaves are an instance of this. Then we derived
some properties about the interleaving distances, such as the triangle
inequality and this compensates for the triangle inequality having been
left out in the section before. However we did not prove, that the
interleaving distances of Reeb precosheaves provide lower bounds to the
corresponding distances of spaces. And it is the aim of this section to
make up for this deficit. In the previous section we already observerd
that \(1\)-homomorphisms of \(D\)-categories yield inequalities for the
corresponding interleaving distances. To use this result we will take
two steps. First we will embed the category of \(\R\)-spaces into a
\(D\)-category \(\mathbf{F}\), so that the interleaving distances on the
image of this embedding are equal to the corresponding distances on
\(\R\)-spaces. Second we factor \(\mathcal{C}\) into this embedding and
a \(1\)-homomorphism \(\tilde{\mathcal{C}}\) from \(\mathbf{F}\) to the
category of precosheaves on \(\overline{D}\).
\begin{itemize}
\item
\textbf{Definition.} Here we define the category \(\mathbf{F}\).
The class of objects of \(\mathbf{F}\) is the class of all pairs
\((f, \mathbf{a})\), where \(f \colon X \rightarrow \R\) is a
continuous real-valued function and \(\mathbf{a} \in D\).
Next we specify the homomorphsims of \(\mathbf{F}\). To this end let
\(f \colon X \rightarrow \R\) and \(g \colon Y \rightarrow \R\) be
continuous functions and \((a, b), (c, d) \in D\). Then a
\emph{homomorphism from \((f, (a, b))\) to \((g, (c, d))\)} is a
continuous map \(\varphi \colon X \rightarrow Y\) such that
\(b - d \leq f(p) - g(\varphi(p)) \leq a - c\) for all \(p \in X\).
For \(b = d = \infty\) we read the left hand side of the previous
inequality as \(-\infty\) and for \(a = c = -\infty\) we read the
right hand side to be \(\infty\).
\end{itemize}
So far we have the category \(\mathbf{F}\) and the full embedding \[
(\_, \mathbf{o}) \colon
\begin{cases}
\begin{split}
f & \mapsto (f, \mathbf{o}) \\
\varphi & \mapsto \varphi .
\end{split}
\end{cases}
\] Next we provide a smoothing functor for \(\mathbf{F}\).
\begin{itemize}
\tightlist
\item
\textbf{Definition.} Let \(f \colon X \rightarrow \R\) be a continuous
function and let \(\mathbf{a}, \mathbf{b}, \mathbf{c} \in D\) with
\(\mathbf{b} \preceq \mathbf{c}\). Then we set
\(\mathcal{T}(\mathbf{b})((f, \mathbf{a})) := (f, \mathbf{a} + \mathbf{b})\)
and
\(\mathcal{T}(\mathbf{b} \preceq \mathbf{c})_{(f, \mathbf{a})} := \id_X\).
\end{itemize}
The previous definition augments \(\mathbf{F}\) with the structure of a
strict \(D\)-category. Now we compare the distances of functions to the
interleaving distances of \(\mathbf{F}\). To this end let
\(f \colon X \rightarrow \R\) and \(g \colon Y \rightarrow \R\) be
continuous functions.
\begin{itemize}
\item
\textbf{Lemma.} Let \(r \in \R\), \(\varepsilon \geq 0\), and let
\(\varphi \colon X \rightarrow Y\) be a homeomorphism. Then we have
\(-\varepsilon \leq r + f(p) - g(\varphi(p)) \leq \varepsilon\) if and
only if \(\varphi\) and \(\varphi^{-1}\) form an
\((-r + \varepsilon, r + \varepsilon)\)-interleaving of
\((f, \mathbf{o})\) and \((g, \mathbf{o})\).
\item
\textbf{Corollary.} We have
\(M(f, g) = M_{\mathcal{T}} ((f, \mathbf{o}), (g, \mathbf{o}))\) and
\(\mu(f, g) = \mu_{\mathcal{T}} ((f, \mathbf{o}), (g, \mathbf{o}))\).
\item
\emph{Proof.} The first equation follows in conjunction with corollary
13, see \protect\hyperlink{properties-of-interleavings}{the section on
properties of interleavings}, and the second equation follows in
conjunction with corollary 12.
\end{itemize}
Now we have an embedding of the category of \(\R\)-spaces into
\(\mathbf{F}\), that preserves the distances. In example 10 from the
\protect\hyperlink{interleavings-in-d-categories}{previous section} we
augmented the category of set-valued precosheaves on \(\overline{D}\)
with the structure of a \(D\)-category and we observed that the
\protect\hyperlink{interleaving-precosheaves-on-d}{interleavings of
precosheaves} are precisely the interleavings with respect to this
structure. Our next and final step towards a lower bound is to provide a
\(1\)-homomorphism \(\tilde{\mathcal{C}}\) from \(\mathbf{F}\) to the
category of set-valued precosheaves on \(\overline{D}\) such that
\(\mathcal{C} = \tilde{\mathcal{C}}((\_, \mathbf{o}))\). Applying the
same procedure to an arbitrary functor \(F\) on the category of
\(\R\)-spaces is what we name a \emph{positive persistence-enhancement
for \(F\)}. Now let \(F\) be a functor from the category of
\(\R\)-spaces to some category \(\mathbf{C}\)
\begin{itemize}
\tightlist
\item
\textbf{Definition} (Positive Persistence-Enhancement)\textbf{.} A
\emph{postive persistence-enhancement for \(F\)} is the structure of a
strict \(D\)-category on \(\mathbf{C}\) together with a
\(1\)-homomorphism \(\tilde{F}\) from \(\mathbf{F}\) to \(\mathbf{C}\)
such that \(F = \tilde{F}((\_, \mathbf{o}))\).
\end{itemize}
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{15}
\tightlist
\item
\textbf{Propostion.} If there is a positive persistence-enhancement of
\(F\) with smoothing functor \(\mathcal{S}\) on \(\mathbf{C}\), then
we have \(M_{\mathcal{S}}(F(f), F(g)) \leq M(f, g)\) and
\(\mu_{\mathcal{S}}(F(f), F(g)) \leq \mu(f, g)\).
\end{enumerate}
\begin{itemize}
\item
\emph{Proof.} This follows from corollary 15, see
\protect\hyperlink{homomorphisms-D-cat}{the section on homomorphisms
in \(D\)-categories}, and the previous corollary.
\item
\emph{Example.} As a first example we provide a positive
persistence-enhancements for the Reeb precosheaf \(\mathcal{C}\). In
the previous section we already defined the structure of a strict
\(D\)-category on the category of precosheaves. So the only thing left
to define for a positive persistence-enhancement is the functor
\(\tilde{\mathcal{C}}\). To this end we set
\(\Delta^{\mathbf{a}} \colon \R \rightarrow \Ec, t \mapsto (t, t) - \mathbf{a}\)
and
\(\overline{\mathcal{C}}((f, \mathbf{a})) := (\Delta^{\mathbf{a}} \circ f)_* \Lambda\)
for any \(\mathbf{a} \in D\). Now let
\(\varphi \colon (f, \mathbf{a}) \rightarrow (g, \mathbf{b})\) be a
homomorphism in \(\mathbf{F}\) for some
\(\mathbf{a}, \mathbf{b} \in D\) and let \(U \subseteq \Ec\) be a
distinguished open subset, then we have
\(\varphi((\Delta^{\mathbf{a}} \circ f)^{-1}(U)) \subseteq (\Delta^{\mathbf{b}} \circ g)^{-1}(U)\)
and thus the restriction
\(\varphi |_{(\Delta^{\mathbf{a}} \circ f)^{-1}(U)} \colon (\Delta^{\mathbf{a}} \circ f)^{-1}(U) \rightarrow (\Delta^{\mathbf{b}} \circ g)^{-1}(U)\).
We set
\(\overline{\mathcal{C}}(\varphi)_U := \Lambda\big(\varphi |_{(\Delta^{\mathbf{a}} \circ f)^{-1}(U)}\big)\).
This defines the functor \(\overline{\mathcal{C}}\) from
\(\mathbf{F}\) to the category of set-valued precosheaves on \(\Ec\).
Now let \(i \colon \overline{D} \subseteq \Ec\) denote the inclusion,
then the composition
\(\tilde{\mathcal{C}} := i_p \circ \overline{\mathcal{C}}\) defines a
\(1\)-homomorphism of strict \(D\)-categories with
\(\mathcal{C} = \tilde{\mathcal{C}}((\_, \mathbf{o}))\).
\end{itemize}
Now let \(F\) and \(G\) be functors from the category of \(\R\)-spaces
to some \(D\)-category \(\mathbf{C}\) with smoothing functor
\(\mathcal{S}\) and let \(\eta \colon F \rightarrow G\) be a natural
transformation. We consider \(\eta\) a functor from the category of
\(\R\)-spaces to the
\href{https://unapologetic.wordpress.com/2007/05/23/arrow-categories/}{category
of arrows} in \(\mathbf{C}\). Moreover we consider the
\href{https://unapologetic.wordpress.com/2007/05/23/arrow-categories/}{category
of arrows} in \(\mathbf{C}\) a \(D\)-category with smoothing functor
\(\mathcal{S}\). (We just apply the smoothing functor to the
homomorphisms.) Then a (positive) persistence-enhancement of \(\eta\)
with smoothing functor \(\mathcal{S}\) is already determined by the
corresponding enhancements for \(F\) and \(G\). Now suppose
\(\tilde{F}\) and \(\tilde{G}\) are arbitrary persistence-enhancements
for \(F\) and \(G\) both with smoothing functor \(\mathcal{S}\).
\begin{itemize}
\tightlist
\item
\textbf{Definition.} We say \emph{\(\mathcal{S}\), \(\tilde{F}\), and
\(\tilde{G}\) combine to a persistence-enhancement of \(\eta\)} if the
map \((f, \mathbf{a}) \mapsto (\mathcal{S}(\mathbf{a}) \circ \eta)_f\)
is a natural transformation from \(\tilde{F}\) to \(\tilde{G}\).
\end{itemize}
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{16}
\tightlist
\item
\emph{Remark.} If \(\mathcal{S}\), \(\tilde{F}\), and \(\tilde{G}\)
combine to a persistence-enhancement of \(\eta\), then
\((f, \mathbf{a}) \mapsto (\mathcal{S}(\mathbf{a}) \circ \eta)_f\) is
a \(2\)-homomorphism from \(\tilde{F}\) to \(\tilde{G}\).
\end{enumerate}
\hypertarget{complete-persistence-enhancements}{\section{Complete
Persistence-Enhancements}\label{complete-persistence-enhancements}}
In the previous section we defined positive persistence enhancements of
functors on \(\R\)-spaces and provided one for \(\mathcal{C}\), thereby
finally establishing that the interleaving distances of the Reeb
precosheaves provide lower bounds to the correspoding distances on
functions. The next aim is to connect this to the interleaving distances
of \protect\hyperlink{join-trees}{join-trees} and to proof theorem 9.
Unfortunately there is a bit of a problem with our use of infinity. If
we consider the diagrams for interleavings in \(D\)-categories, then
there is a smoothing functor on the top right but none on the top left.
In the diagrams for interleavings of join trees however there is a shift
on the top left but none on the top right. If it wasn't possible for
\(a\) or \(b\) to attain the value \(\infty\), then it wouldn't matter
if we shift on the left or on the right. But if \(a\) or \(b\) is
infinity, then the corresponding shift on the right is ill-defined. The
purpose of including infinity is that we get an \(\infty\)-interleaving
from any other interleaving by monotonicity. So to determine the
interleaving distances we could start by considering all
\(\infty\)-interleavings and then optimize them with respect to the two
weightings. The downside is that in order to harness this framework for
comparing the interleaving distance of the Reeb precosheaf to that of
the join tree, we have to introduce some more terminology.
Above we defined the monoidal poset \(D\). Now the partial order
\(\preceq\) canonically extends to \(\Ec\) but for the monoidal
operation there is some ambiguity when adding \(\infty\) and
\(-\infty\). But it is still possible if we give up commutativity. More
specifically we specify \(-\infty + \infty := \infty\) and
\(\infty - \infty := -\infty\). So the last term always dominates. Now
\(\Ec\) contains \(D\) as a submonoid. Moreover \(-D\) is a commutative
submonoid of \(\Ec\) as well and negation yields an order-reversing
monoid isomorphism from \(D\) to \(-D\). Similarly to \(D\)-categories
we now define \(-D\)- and \(\Ec\)-categories.
\begin{itemize}
\item
\textbf{Definition.} A \emph{strict \(\Ec\)-category} respectively
\emph{\(-D\)-category} is a category \(\mathbf{C}\) with a strict
\href{https://en.wikipedia.org/wiki/Monoidal_functor}{monoidal
functor} \(\mathcal{S}\) from \(\Ec\) respectively \(-D\) to the
\href{https://ncatlab.org/nlab/show/endofunctor}{category of
endofunctors} on \(\mathbf{C}\). We refer to \(\mathcal{S}\) as the
\emph{smoothing functor of \(\mathbf{C}\)}.
\item
\emph{Remark.} If \(\mathbf{C}\) is a strict \(-D\)-category with
smoothing functor \(\mathcal{S}\), then the opposite category
\(\mathbf{C}^{\op}\) is a strict \(D\)-category with smoothing functor
\(\mathcal{S}(- (\_))\).
\end{itemize}
Now we define interleavings in \(-D\)-categories. To this end let
\(\mathbf{C}\) be a \(-D\)-category with smoothing functor
\(\mathcal{S}\) and let \(A\) and \(B\) be objects of \(\mathbf{C}\).
\begin{itemize}
\item
\textbf{Definition.} For \((\mathbf{a}, \mathbf{b}) \in \mathcal{D}\)
an \emph{\((\mathbf{a}, \mathbf{b})\)-interleaving of \(A\) and \(B\)
in \(\mathbf{C}\)} is an \((\mathbf{a}, \mathbf{b})\)-interleaving of
\(B\) and \(A\) in \(\mathbf{C}^{\op}\) with respect to the smoothing
functor \(\mathcal{S}(- (\_))\).
We say \emph{\(A\) and \(B\) are
\((\mathbf{a}, \mathbf{b})\)-interleaved} if there is an
\((\mathbf{a}, \mathbf{b})\)-interleaving of \(A\) and \(B\).
Similarly an \emph{\((a, b)\)-interleaving of \(A\) and \(B\) in
\(\mathbf{C}\)} is an \((a, b)\)-interleaving of \(B\) and \(A\) in
\(\mathbf{C}^{\op}\) for \((a, b) \in D^{\perp}\).
\end{itemize}
For convenience we spell out the meaning of the previous definition.
\begin{itemize}
\tightlist
\item
\emph{Remark.} For \((\mathbf{a}, \mathbf{b}) \in \mathcal{D}\) an
\((\mathbf{a}, \mathbf{b})\)-interleaving of \(A\) and \(B\) in
\(\mathbf{C}\) is a pair of homomorphisms
\(\varphi \colon \mathcal{S}(-\mathbf{a})(A) \rightarrow B\) and
\(\psi \colon \mathcal{S}(-\mathbf{b})(B) \rightarrow A\) such that
the diagrams \[
\xymatrix{
\mathcal{S}(- (\mathbf{a} + \mathbf{b}))(A)
\ar@/^/[rr]^{\quad \mathcal{S}(- (\mathbf{a} + \mathbf{b}) \preceq \mathbf{o})_A}
\ar[dr]|-{\mathcal{S}(-\mathbf{b})(\varphi)}
& &
A
\\
&
\mathcal{S}(-\mathbf{b})(B)
\ar[ru]|-{\psi}
}
\] and \[
\xymatrix{
\mathcal{S}(- (\mathbf{a} + \mathbf{b}))(B)
\ar@/^/[rr]^{\quad \mathcal{S}(- (\mathbf{a} + \mathbf{b}) \preceq \mathbf{o})_B}
\ar[dr]|-{\mathcal{S}(-\mathbf{a})(\psi)}
& &
B
\\
&
\mathcal{S}(-\mathbf{a})(A)
\ar[ru]|-{\varphi}
}
\] commute.
\end{itemize}
With these definitions we may talk about the absolute and relative
interleaving distance of \(A\) and \(B\). Now let us assume
\(\mathbf{C}\) is a strict \(\Ec\)-category with smoothing functor
\(\mathcal{S}\), then it also is a \(D\)- and a \(-D\)-category. So if
we don't mention, whether we work with \(\mathbf{C}\) as a
\(D\)-category or as a \(-D\)-category, then our term
\emph{interleaving} is ambiguous. Here (and with the next lemma) we
argue that this creates no problem. Suppose we have
\(\varphi \colon A \rightarrow \mathcal{S}(\mathbf{a})(B)\) for some
\(\mathbf{a} \in D\), then we get the homomorphism
\(\varphi^b := \mathcal{S}(\mathbf{a}-\mathbf{a} \preceq \mathbf{o})_B \circ \mathbf{S}(-\mathbf{a})(\varphi)\)
from \(\mathcal{S}(-\mathbf{a})(A)\) to \(B\). And if we now apply the
functor \(\mathcal{S}(\mathbf{a})\) to \(\varphi^b\) and precompose with
\(\mathcal{S}(\mathbf{o} \preceq -\mathbf{a}+\mathbf{a})_A\), then we
reobtain \(\varphi\), using that \(\mathcal{S}\) is monoidal. Such
considerations lead us to the following
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{17}
\tightlist
\item
\textbf{Lemma.} The interleavings of \(A\) and \(B\) with respect to
the \(D\)-category sructure of \(\mathbf{C}\) are in a canonical
bijection with the interleavings of \(A\) and \(B\) with respect to
the \(-D\)-category sructure.
\end{enumerate}
Homomorphisms of \(-D\)- and \(\Ec\)-categories are defined completely
analogously to those of \(D\)-categories.
\begin{itemize}
\item
\textbf{Definition.} Here we define the categories \(-\mathbf{F}\) and
\(\pm \mathbf{F}\).
The class of objects of \(-\mathbf{F}\) respectively
\(\pm \mathbf{F}\) is the class of all pairs \((f, \mathbf{a})\),
where \(f \colon X \rightarrow \R\) is a continuous real-valued
function and \(\mathbf{a} \in -D\) respectively
\(\mathbf{a} \in \Ec\).
Next we specify the homomorphsims of \(\mathbf{F}\). To this end let
\(f \colon X \rightarrow \R\) and \(g \colon Y \rightarrow \R\) be
continuous functions and \((a, b), (c, d) \in \Ec\). Then a
\emph{homomorphism from \((f, (a, b))\) to \((g, (c, d))\)} is a
continuous map \(\varphi \colon X \rightarrow Y\) such that
\(b - d \leq f(p) - g(\varphi(p)) \leq a - c\) for all \(p \in X\).
Whenever there is any ambiguity interpreting the left-hand side of
this inequality, we interpret it as \(-\infty\), for the right-hand
side as \(\infty\).
\end{itemize}
Next we define negative and complete persistence-enhancements. To this
end let \(F\) be a functor from the category of \(\R\)-spaces to some
category \(\mathbf{C}\).
\begin{itemize}
\tightlist
\item
\textbf{Definition.} A \emph{negative} respectively a \emph{complete
persistence-enhancement of \(F\)} is the structure of a strict
\(-D\)-category respectively \(\Ec\)-category on \(\mathbf{C}\)
together with a \(1\)-homomorphism \(\tilde{F}\) from \(-\mathbf{F}\)
resepctively \(\pm \mathbf{F}\) to \(\mathbf{C}\) such that
\(F = \tilde{F}((\_, \mathbf{o}))\).
\end{itemize}
\section{Some Equivalences}\label{some-equivalences}
In this section we move one step closer to proving theorem 9. We
consider interleavings of precosheaves in the image of the functor
\(\mathcal{C} \mathcal{E}\) and transform those into interleavings
somewhat closer to those of join trees.
\hypertarget{equivalence-to-descending-precosheaf}{\subsection{Equivalence
to descending Precosheaf}\label{equivalence-to-descending-precosheaf}}
We start by describing the structure of an \(\Ec\)-category on the the
category of set-valued precosheaves on \(\overline{\R}_{-\infty}\). We
proceed similar to example 10. To this end let \(\mathcal{U}\) be the
topology or intersection-base of \(\overline{\R}_{-\infty}\) (here they
are the same), \(\mathcal{Q}\) the intersection-base of
\(\overline{D}\), and let \[
\overline{s} \colon \Ec \mapsto \selfm{\mathcal{U}},
(a, b) \mapsto
\begin{cases}
(s^b)^{+1} & b > -\infty \\
(s^{-b})^{-1} & b < \infty .
\end{cases}
\] We note that this definition is not over-determined and that
\(\overline{s}\) is monotone. Now post-composition with the
precomposition functor \(\tilde{\mathcal{S}}\) yields the smoothing
functor
\(\overline{\mathcal{S}} := \tilde{\mathcal{S}} \circ \overline{s}\). We
note that \(\overline{\mathcal{S}}((a, b)) = s^b_p\) for \(b > -\infty\)
and \(\overline{\mathcal{S}}((a, b)) = s^{-b}_*\) for \(b < \infty\).
Now we have the continuous map \(\pi^2\) from \(\overline{D}\) to
\(\overline{\R}_{-\infty}\) and we aim to show that \(\pi^2_*\) and
\(\pi^2_p\) are \(1\)-homomorphisms between the corresponding
\(D\)-categories and that \(\eta^{\pi^2}\) is a \(2\)-homomorphism. For
\((a, b) \in D\) we have \(\pi^2 \circ S^{(a, b)} = s^b \circ \pi^2\)
and with this we convince ourselves that the diagram \[
\xymatrix@+=3pc{
\mathcal{Q}
\ar[d]_{\big(S^{(a, b)}\big)^{+1}}
\ar[r]^{(\pi^2)^{+1}}
&
\mathcal{U}
\ar[d]|-{(s^b)^{+1}}
\ar[r]^{(\pi^2)^{-1}}
&
\mathcal{Q}
\ar[d]^{\big(S^{(a, b)}\big)^{+1}}
\\
\mathcal{Q}
\ar[r]_{(\pi^2)^{+1}}
&
\mathcal{U}
\ar[r]_{(\pi^2)^{-1}}
&
\mathcal{Q}
}
\] commutes for all \((a, b) \in D\). (We note that lemma 5 is the
commutativity of the left square.)
\begin{itemize}
\item
\textbf{Lemma.} The functor \(\pi^2_*\) is a \(1\)-homomorphism of
\(D\)-categories.
\item
\emph{Proof.} This follows from the commutativity of the right square
in the above diagram and the monotonicity of post-composition by
\((\pi^2)^{-1}\).
\item
\textbf{Lemma.} The functor \(\pi^2_p\) is a \(1\)-homomorphism of
\(D\)-categories.
\item
\emph{Proof.} This follows from the commutativity of the left square
in the above diagram and the monotonicity of post-composition by
\((\pi^2)^{+1}\).
\item
\textbf{Lemma.} The natural transformation \(\eta^{\pi^2}\) is a
\(2\)-homomorphism of \(D\)-categories.
\item
\emph{Proof.} This follows from the commutativity of the outer square
in the above diagram.
\end{itemize}
The previous three lemmata have the following
\begin{itemize}
\tightlist
\item
\textbf{Corollary.} The full subcategory of set-valued precosheaves
\(F\) on \(\overline{D}\), with \(\eta^{\pi^2}_F\) an isomorphism, is
a sub-\(D\)-category in the sense that it is invariant under
\(\mathcal{S}(\mathbf{a})\) for all \(\mathbf{a} \in D\).
\end{itemize}
Now the functor \(\pi^2_*\) is full and faithful on the category of
precosheaves \(F\), with \(\eta^{\pi^2}_F\) an isomorphism. Since this
is also a \(D\)-category and \(\pi^2_*\) is a \(1\)-homomorphism on this
\(D\)-category, \(\pi^2_*\) yields bijections of interleavings.
Now let \(f \colon X \rightarrow \R\) a continuous function.
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{18}
\tightlist
\item
\textbf{Lemma.} The homomorphism
\((\eta^{\pi^2} \circ \mathcal{C} \circ \mathcal{E})_f\) from
\(\mathcal{C} \mathcal{E} f\) to
\(\pi^2_p \pi^2_* \mathcal{C} \mathcal{E} f\) is an isomorphism.
\end{enumerate}
\begin{itemize}
\tightlist
\item
\emph{Proof.} For \(a < r < b\) we set
\(U := (a, \infty] \times [-\infty, b)\), then we have
\((\mathcal{C} \mathcal{E} f)(U) = \Lambda(\epi f \cap X \times (a, b))\)
and
\((\pi^2_p \pi^2_* \mathcal{C} \mathcal{E} f)(U) = \Lambda(\epi f \cap X \times [-\infty, b))\).
Now let \(i\) be the inclusion of \(\epi f \cap X \times [r, b)\) into
\(\epi f \cap X \times (a, b)\) and let \(j\) be the inclusion of
\(\epi f \cap X \times (a, b)\) into
\(\epi f \cap X \times [-\infty, b)\). First we prove that
\(\Lambda(i)\) is a bijection. Let
\((x, y) \in \epi f \cap X \times (a, r)\), then
\(c \colon [0, 1] \rightarrow \epi f \cap X \times (a, b), t \mapsto (x, t(r-y) + y)\)
defines a path from \((x, y)\) to \((x, r)\), hence \(\Lambda(i)\) is
surjective. Now let
\(R \colon \epi f \cap X \times (a, b) \rightarrow \epi f \cap X \times [r, b), (x, y) \mapsto (x, \max \{r, y\})\),
then \(R \circ i = \id\) and thus
\(\Lambda(R) \circ \Lambda(i) = \id\), hence \(\Lambda(i)\) is
injective. By a similar argument we obtain that
\(\Lambda(j \circ i) = \Lambda(j) \circ \Lambda(i)\) is bijective. Now
that both \(\Lambda(i)\) and \(\Lambda(j) \circ \Lambda(i)\) are
bijective, we also have that \(\Lambda(j)\) is bijective. But
\(\Lambda(j)\) is just
\((\eta^{\pi^2} \circ \mathcal{C} \circ \mathcal{E})_{f ~ U}\) and
this implies the claim.
\end{itemize}
Now let \(g \colon Y \rightarrow \R\) be another continuous function.
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{19}
\tightlist
\item
\textbf{Corollary.} The interleavings of \(\mathcal{C} \mathcal{E} f\)
and \(\mathcal{C} \mathcal{E} g\) are in bijection to those of
\(\pi^2_* \mathcal{C} \mathcal{E} f\) and
\(\pi^2_* \mathcal{C} \mathcal{E} g\).
\end{enumerate}
\subsection{A second type of
Interleavings}\label{a-second-type-of-interleavings}
We reuse the notation and the definitions from the previous subsection.
In the present subsection we define the structure of a \(-D\)-category
on \(\mathbf{C}\) with the smoothing functor named \(\mathcal{S}'\). Now
for a smoothing functor we need two things, first we need the
endofunctors \(\mathcal{S}'(\mathbf{a})\) associated to any
\(\mathbf{a} \in -D\) and second we need the natural transformations
\(\mathcal{S}'(\mathbf{a} \preceq \mathbf{b})\) associated to any
\(\mathbf{a}, \mathbf{b} \in D\) with \(\mathbf{a} \preceq \mathbf{b}\).
Now in order to get there, we will do something seemingly unnecessary.
We will define the endofunctors \(\mathcal{S}'(\mathbf{a})\) not just on
\(\mathbf{D}\) but on the whole category of set-valued precosheaves on
\(\overline{D}\). Then we will show, that \(\mathbf{C}\) is invariant
under these endofunctors. In this sense the endofunctors
\(\mathcal{S}'(\mathbf{a})\) restrict to endofunctors on \(\mathbf{C}\).
Then we define the natural transformations.
So let us start with the endofunctors setting
\(\mathcal{S}'((a, b)) := S^{(-b, -b)}_*\) for all \((a, b) \in -D\).
Now in order to see that \(\mathbf{C}\) is invariant under these
endofunctors we will show that \(\pi^2_*\), \(\pi^2_p\),
\(\eta^{\pi^2}\), and \(\overline{\mathcal{S}}\) are compatible with
these endofunctors in the same way they would by compatible if
\(\pi^2_*\) and \(\pi^2_p\) were \(1\)-homomorphisms and
\(\eta^{\pi^2}\) was a \(2\)-homomorphism. To this end we convince
ourselves that the diagram \[
\xymatrix@+=3pc{
\mathcal{Q}
\ar[d]_{\big(S^{(-b, -b)}\big)^{-1}}
\ar[r]^{(\pi^2)^{+1}}
&
\mathcal{U}
\ar[d]|-{(s^{-b})^{-1}}
\ar[r]^{(\pi^2)^{-1}}
&
\mathcal{Q}
\ar[d]^{\big(S^{(-b, -b)}\big)^{-1}}
\\
\mathcal{Q}
\ar[r]_{(\pi^2)^{+1}}
&
\mathcal{U}
\ar[r]_{(\pi^2)^{-1}}
&
\mathcal{Q}
}
\] commutes for all \(b < \infty\).
\begin{itemize}
\item
\textbf{Lemma.} The functor \(\pi^2_*\) commutes with
\(\mathcal{S}'(\mathbf{a})\) and
\(\overline{\mathcal{S}}(\mathbf{a})\) for all \(\mathbf{a} \in -D\).
\item
\emph{Proof.} This follows from the commutativity of the right square
in the above diagram.
\item
\textbf{Lemma.} The functor \(\pi^2_p\) commutes with
\(\overline{\mathcal{S}}(\mathbf{a})\) and
\(\mathcal{S}'(\mathbf{a})\) for all \(\mathbf{a} \in -D\).
\item
\emph{Proof.} This follows from the commutativity of the left square
in the above diagram.
\item
\textbf{Lemma.} The natural transformation \(\eta^{\pi^2}\) commutes
with \(\mathcal{S}'(\mathbf{a})\) for all \(\mathbf{a} \in -D\).
\item
\emph{Proof.} This follows from the commutativity of the outer square
in the above diagram.
\end{itemize}
The previous three lemmata have the following
\begin{itemize}
\tightlist
\item
\textbf{Corollary.} The subcategory \(\mathbf{C}\) is invariant under
\(\mathcal{S}'(\mathbf{a})\) for all \(\mathbf{a} \in -D\).
\end{itemize}
So far we defined the endofunctors for the smoothing functor
\(\mathcal{S}'\) on \(\mathbf{C}\). The next step is to define the
natural transformations \(\mathcal{S}'(\mathbf{a} \preceq \mathbf{b})\)
for any \(\mathbf{a}, \mathbf{b} \in D\) with
\(\mathbf{a} \preceq \mathbf{b}\). Now we already convinced ourselves
that \(\pi^2_*\), \(\pi^2_p\), and \(\eta^{\pi^2}\) are compatible with
the endofunctors of \(\mathcal{S}'\) and \(\overline{\mathcal{S}}\). So
that is already half the part of \(\pi^2_*\) and \(\pi^2_p\) being
\(1\)-homomorphisms and \(\eta^{\pi^2}\) being a \(2\)-homomorphism for
this hypothetical smoothing functor. So it would be nice if we could
define these natural transformations in such a way that \(\pi^2_*\),
\(\pi^2_p\), and \(\eta^{\pi^2}\) were actually \(1\)- respectively
\(2\)-homomorphisms. Now suppose we were already there, then we would
have the commutative diagram \[
\xymatrix@C+=5pc{
\mathcal{S}'(\mathbf{a})
\ar@{=>}[r]^{\mathcal{S}'(\mathbf{a} \preceq \mathbf{b})}
\ar@{=>}[d]_{\eta^{\pi^2} \circ \mathcal{S}(\mathbf{a})}
&
\mathcal{S}'(\mathbf{b})
\ar@{=>}[d]^{\eta^{\pi^2} \circ \mathcal{S}(\mathbf{b})}
\\
\pi^2_p \circ \overline{\mathcal{S}}(\mathbf{a}) \circ \pi^2_*
\ar@{=>}[r]_{\pi^2_p \circ
\overline{\mathcal{S}}(\mathbf{a} \preceq \mathbf{b}) \circ \pi^2_*}
&
\pi^2_p \circ \overline{\mathcal{S}}(\mathbf{b}) \circ \pi^2_*
}
\] for all \(\mathbf{a}, \mathbf{b} \in D\) with
\(\mathbf{a} \preceq \mathbf{b}\). And this determines
\(\mathcal{S}'(\mathbf{a} \preceq \mathbf{b})\), since \(\eta^{\pi^2}\)
is a natural isomorphism on \(\mathbf{C}\). Also it does the job.
So now that \(\pi^2_*\) is a \(1\)-homomorphism with respect to this
second smoothing functor \(\mathcal{S}'\) on \(\mathbf{C}\) and
\(\overline{\mathcal{S}}\), the interleavings of
\(\mathcal{C} \mathcal{E} f\) and \(\mathcal{C} \mathcal{E} g\) with
respect to \(\mathcal{S}'\) are in bijection with those of
\(\pi^2_* \mathcal{C} \mathcal{E} f\) and
\(\pi^2_* \mathcal{C} \mathcal{E} g\). Now these are all interleavings
in \(-D\)-categories. But with \(\overline{\mathcal{S}}\) we gave the
category of set-valued precosheaves on \(\overline{\R}_{-\infty}\) the
structure of an \(\Ec\)-category. So by lemma 18, from the section on
\protect\hyperlink{complete-persistence-enhancements}{complete
persistence-enhancements}, the interleavings of
\(\mathcal{C} \mathcal{E} f\) and \(\mathcal{C} \mathcal{E} g\), with
respect to the \(-D\)-category structure given by
\(\overline{\mathcal{S}}\), are in canonical bijection with those given
by the \(\overline{\mathcal{S}}\)-induced structure of a \(D\)-category.
So in conjunction with corollary 20 from the previous subsection we have
the following
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{20}
\tightlist
\item
\textbf{Propostion.} The interleavings of
\(\mathcal{C} \mathcal{E} f\) and \(\mathcal{C} \mathcal{E} g\) with
respect to \(\mathcal{S}\) and with respect to \(\mathcal{S}'\) are in
bijection.
\end{enumerate}
\section{A negative Enhancement for Join
Trees}\label{negative-enhancement-for-join-trees}
To provide a negative persistence-enhancement for
\(\mathcal{R} \circ \mathcal{E}\) we first provide one for
\(\mathcal{E}\). To this end let \(\mathbf{D}\) be the
\href{https://ncatlab.org/nlab/show/full+subcategory}{full subcategory}
of \(\overline{\R}\)-spaces of the form \(r + \mathcal{E} f\) or
\(r + \mathcal{R} \mathcal{E} f\) for some bounded constructible
\(\R\)-space \(f\) and some \(r \in (-\infty, \infty]\). (We don't need
constructibility for the results of this section, but we will need it
later and we don't intend to introduce even more notation.) Now we
define the smoothing functor \(\mathcal{S}\) on \(\mathbf{D}\). The
easiest part of the definition are the endofunctors. Moreover these
endofunctors exist on the whole category of \((-\infty, \infty]\)-spaces
and not just \(\mathbf{D}\). Now let
\(f \colon X \rightarrow (-\infty, \infty]\) be a continuous function,
then we set \(\mathcal{S}((a, b))(f) := f - b\) for all
\((a, b) \in -D\). And for any homomorphism \(\varphi\) in the category
of \((-\infty, \infty]\)-spaces we set
\(\mathcal{S}((a, b))(\varphi) := \varphi\). This defines the
endofunctors \(\{\mathcal{S}(\mathbf{a}) ~|~ \mathbf{a} \in -D\}\) on
all \((-\infty, \infty]\)-spaces.
Now let \(f \colon X \rightarrow \R\) be an \(\R\)-space, let
\(r \in \R\), and let \((a, b), (c, d) \in -D\) with
\((a, b) \preceq (c, d)\). Then we set \[
\mathcal{S}((a, b) \preceq (c, d))(r + \mathcal{E} f) \colon
\epi f \rightarrow \epi f,
(p, t) \mapsto (p, t - b + d) .
\] Moreover we set \[
\mathcal{S}((a, b) \preceq (c, d))(r + \mathcal{R} \mathcal{E} f) :=
\mathcal{R}(\mathcal{S}((a, b) \preceq (c, d))(r + \mathcal{E} f)) .
\] And this concludes our definition of \(\mathcal{S}\).
Now for \((a, b) \in D^{\perp}\), the \((a, b)\)-interleavings of two
join trees are precisely the \((a, b)\)-interleavings with respect to
\(\mathcal{S}\). In particular the interleaving distances coincide by
corollary 12. Admittedly it is a bit of a cheat or kind of trivial,
since we specifically defined this subcategory \(\mathbf{D}\) so that
this was going to work out.
Next we define the functor \(\tilde{\mathcal{E}}\). To this end let
\(f \colon X \rightarrow \R\) and \(g \colon Y \rightarrow \R\) be
continuous functions, let \((a, b), (c, d) \in -D\), and let
\(\varphi \colon X \rightarrow Y\) be a homomorphism from
\((f, (a, b))\) to \((g, (c, d))\) in \(-\mathbf{F}\). Then we set
\(\tilde{\mathcal{E}}(f, (a, b)) := -b + \mathcal{E} f\), similarly for
\((g, (c, d))\) of course, and
\(\tilde{\mathcal{E}}(\varphi) \colon \epi f \rightarrow \epi g, (p, t) \mapsto (\varphi(p), t - b + d)\).
This defines our negative persistence-enhancement of \(\mathcal{E}\).
(Again a bit of a cheat.)
We note that we have the following
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{21}
\tightlist
\item
\textbf{Lemma.} The endofunctor \(\mathcal{R}\) is a
\(1\)-homomorphism from \(\mathbf{D}\) to \(\mathbf{D}\) and
\(\pi \colon \id \Rightarrow \mathcal{R}\) is a \(2\)-homomorphism.
\end{enumerate}
In particular \(\mathcal{S}\) and
\(\mathcal{R} \circ \tilde{\mathcal{E}}\) form a negative
persistence-enhancement of join trees. (This does not yield any new
results about join trees, we just meant to show, they fit into this
framework.)
\section{Equality of Interleaving
Distances}\label{equality-of-interleaving-distances}
Finally we get to proving theorem 9. We reuse the notation and the
definitions from the previous two subsections. We aim to show that the
Reeb precosheaf \(\mathcal{C}\) defines a \(1\)-homomorphism from
\(\mathbf{D}\) to \(\mathbf{C}\). Now in order for this statement even
to make any sense, the image of \(\mathbf{D}\) under \(\mathcal{C}\)
should lie in \(\mathbf{C}\).
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{22}
\tightlist
\item
\textbf{Lemma.} The image of \(\mathbf{D}\) under \(\mathcal{C}\) is
part of the subcategory \(\mathbf{C}\).
\end{enumerate}
Now let \(f \colon X \rightarrow \R\) be a bounded constructible
\(\R\)-space. To proof the previous lemma it suffices to show that
\(\mathcal{C} (r + \mathcal{E} f)\) and
\(\mathcal{C} (r + \mathcal{R} \mathcal{E} f)\) are an object of
\(\mathbf{C}\) for all \(r \in (-\infty, \infty]\).
We consider the case \(r = 0\) first. By lemma 19 the precosheaf
\(\mathcal{C} \mathcal{E} f\) is an object of \(\mathbf{C}\). By lemma
30 from \protect\hyperlink{skeleton-epigraph}{the last appendix} the
projection \(\mathcal{E} f\) from \(\epi f\) to \(\overline{\R}\) is a
constructible \(\overline{\R}\)-space. This in conjunction with lemma 6
yields the following
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{23}
\tightlist
\item
\textbf{Lemma.} The homomorphism
\((\mathcal{C} \circ \pi \circ \mathcal{E})_f\) from
\(\mathcal{C} \mathcal{E} f\) to
\(\mathcal{C} \mathcal{R} \mathcal{E} f\) is an isomorphism of
precosheaves.
\end{enumerate}
Now \(\mathbf{C}\) is closed under isomorphisms and thus also
\(\mathcal{C} \mathcal{R} \mathcal{E} f\) lies in \(\mathbf{C}\).
We continue with the case of \(r\) not necessarily being \(0\). To this
end let \(g \colon Y \rightarrow (-\infty, \infty]\) be a continuous
function, possibly an object of \(\mathbf{D}\). We note that for any
\(r \in (-\infty, \infty]\) we have
\(r + g = \mathcal{S}((\infty, -r)) (g)\), by definition of
\(\mathcal{S}\). We now recall that we also defined the endofunctors
associated to the smoothing functor \(\mathcal{S}'\) for \(\mathbf{D}\)
on the whole category of set-valued precosheaves on \(\overline{D}\) and
not just \(\mathbf{D}\). With \(\mathbf{D}\) being invariant under these
endofunctors, lemma 23 follows from the following
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{24}
\tightlist
\item
\textbf{Lemma.} For all \(\mathbf{a} \in -D\) we have
\((\mathcal{C} \circ \mathcal{S}(\mathbf{a}))_g = (\mathcal{S}'(\mathbf{a}) \circ \mathcal{C})_g\).
\end{enumerate}
\begin{itemize}
\tightlist
\item
\emph{Proof.} For \((a, b) \in -D\) we have
\(\Delta \circ \mathcal{S}((a, b))(g) = S^{(-b, -b)} \circ \Delta \circ g\)
and this implies the claim.
\end{itemize}
Next we show that \(\mathcal{C}\) is compatible with the natural
transformations of the smoothing functors. To this end let
\(\mathbf{a}, \mathbf{b} \in -D\) with
\(\mathbf{a} \preceq \mathbf{b}\).
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{25}
\tightlist
\item
\textbf{Lemma.} We have
\((\overline{\mathcal{S}}(\mathbf{a} \preceq \mathbf{b}) \circ \pi^2_* \circ \mathcal{C} \circ \mathcal{E})_f = (\pi^2_* \circ \mathcal{C} \circ \mathcal{S}(\mathbf{a} \preceq \mathbf{b}) \circ \mathcal{E})_f\).
\end{enumerate}
\begin{itemize}
\item
\emph{Proof.} First we set \((a', a) := \mathbf{a}\) and
\((b', b) := \mathbf{b}\). Now let \(r \in \R\). If we unravel the
definitions we obtain \[
(\overline{\mathcal{S}}(\mathbf{a}) \pi^2_* \mathcal{C} \mathcal{E} f)(
[-\infty, r)
) =
\Lambda(\epi f \cap X \times [-\infty, r + a))
\] and \[
(\overline{\mathcal{S}}(\mathbf{b}) \pi^2_* \mathcal{C} \mathcal{E} f)(
[-\infty, r)
) =
\Lambda(\epi f \cap X \times [-\infty, r + b)) .
\] Let \(i\) be the inclusion of
\(\epi f \cap X \times [-\infty, r + a)\) into
\(\epi f \cap X \times [-\infty, r + b)\) and let \[
\tau \colon \epi f \cap X \times [-\infty, r + a) \rightarrow
\epi f \cap X \times [-\infty, r + b),
(p, t) \mapsto (p, t - a + b) ,
\] then \[
(\overline{\mathcal{S}}(\mathbf{a} \preceq \mathbf{b}) \circ
\pi^2_* \circ \mathcal{C} \circ \mathcal{E})_{f ~ [-\infty, r)} = \Lambda(i)
\] and \[
(\pi^2_* \circ \mathcal{C} \circ \mathcal{S}(\mathbf{a} \preceq \mathbf{b})
\circ \mathcal{E})_{f ~ [-\infty, r)} = \Lambda(\tau) .
\] Now let \((p, t) \in \epi f \cap X \times [-\infty, r + a)\), then
\(\{p\} \times [t, t - a + b]\) is contained in
\(\epi f \cap X \times [-\infty, r + b)\). Moreover we have
\((p, t), (p, t - a + b) \in \{p\} \times [t, t - a + b]\), hence
\(\Lambda(i) = \Lambda(\tau)\).
\item
\textbf{Corollary.} We have
\((\mathcal{S}'(\mathbf{a} \preceq \mathbf{b}) \circ \mathcal{C} \circ \mathcal{E})_f = (\mathcal{C} \circ \mathcal{S}(\mathbf{a} \preceq \mathbf{b}) \circ \mathcal{E})_f\).
\item
\emph{Proof.} This follows from \(\pi^2_*\) being a \(1\)-homomorphism
and being full and faithful on \(\mathbf{C}\).
\item
\textbf{Corollary.} We have
\((\mathcal{S}'(\mathbf{a} \preceq \mathbf{b}) \circ \mathcal{C} \circ \mathcal{R} \circ \mathcal{E})_f = (\mathcal{C} \circ \mathcal{S}(\mathbf{a} \preceq \mathbf{b}) \circ \mathcal{R} \circ \mathcal{E})_f\).
\item
\emph{Proof.} By the lemmata 22 and 25 and the previous corollary we
have the commutative diagram \[
\xymatrix@R+=4pc@C+=6pc{
\mathcal{S}'(\mathbf{a}) \mathcal{C} \mathcal{E} f
\ar[r]^{
(\mathcal{S}'(\mathbf{a} \preceq \mathbf{b}) \circ
\mathcal{C} \circ \mathcal{E})_f
}
\ar[d]|-{
(\mathcal{S}'(\mathbf{a}) \circ \mathcal{C} \circ \pi \circ
\mathcal{E})_f
}
&
\mathcal{S}'(\mathbf{b}) \mathcal{C} \mathcal{E} f
\ar[d]|-{
(\mathcal{S}'(\mathbf{b}) \circ \mathcal{C} \circ \pi \circ
\mathcal{E})_f
}
\\
\mathcal{S}'(\mathbf{a}) \mathcal{C} \mathcal{R} \mathcal{E} f
\ar[r]_{
(\mathcal{C} \circ \mathcal{S}(\mathbf{a} \preceq \mathbf{b})
\circ \mathcal{R} \circ \mathcal{E})_f
}
&
\mathcal{S}'(\mathbf{b}) \mathcal{C} \mathcal{R} \mathcal{E} f .
}
\] Now by lemma 24 the vertical arrows are isomorphisms and thus the
naturality of \(\mathcal{S}'(\mathbf{a} \preceq \mathbf{b})\) implies
that
\((\mathcal{C} \circ \mathcal{S}(\mathbf{a} \preceq \mathbf{b}) \circ \mathcal{R} \circ \mathcal{E})_f = (\mathcal{S}'(\mathbf{a} \preceq \mathbf{b}) \circ \mathcal{C} \circ \mathcal{R} \circ \mathcal{E})_f\).
\end{itemize}
Eventually the previous two corollaries and lemma 25 imply the
\begin{itemize}
\tightlist
\item
\textbf{Proposition.} The functor \(\mathcal{C}\) is a
\(1\)-homomorphism from \(\mathbf{D}\) to \(\mathbf{C}\).
\end{itemize}
Now let \(g \colon Y \rightarrow \R\) be another bounded constructible
\(\R\)-space. Then we have the following
\begin{itemize}
\item
\textbf{Corollary.} The interleavings of \(\mathcal{R} \mathcal{E} f\)
and \(\mathcal{R} \mathcal{E} g\) with respect to \(\mathcal{S}\) are
in bijection with the interleavings of \(\mathcal{C} \mathcal{E} f\)
and \(\mathcal{C} \mathcal{E} g\) with respect to \(\mathcal{S}'\).
\item
\emph{Proof.} We observe that all join trees of bounded constructible
\(\R\)-spaces lie in a \(-D\)-subcategory of \(\mathbf{D}\). By the
previous proposition \(\mathcal{C}\) yields a \(1\)-homomorphism from
this \(-D\)-category to \(\mathbf{C}\). Moreover corollary 8 implies
that \(\mathcal{C}\) is full and faithful on this category and thus
the interleavings of \(\mathcal{R} \mathcal{E} f\) and
\(\mathcal{R} \mathcal{E} g\) are in bijection with those of
\(\mathcal{C} \mathcal{R} \mathcal{E} f\) and
\(\mathcal{C} \mathcal{R} \mathcal{E} g\). Now by lemma 24 these are
isomorphic to \(\mathcal{C} \mathcal{E} f\) and
\(\mathcal{C} \mathcal{E} g\) and this implies the claim.
\end{itemize}
Now we can finally proof theorem 9. To this end let
\(f \colon X \rightarrow \R\) and \(g \colon Y \rightarrow \R\) be
continuous maps with \(X\) and \(Y\) smooth and compact manifolds.
\begin{itemize}
\item
\emph{Proof} (Theorem 9). Let \(\delta > 0\), by Bröcker and Jänich
(\protect\hyperlink{ref-BrJae1973}{1973} Satz 14.8) there are smooth
functions \(f' \colon X \rightarrow \R\) and
\(g' \colon Y \rightarrow \R\) with
\(\norm{f - f'}_{\infty} \leq \frac{\delta}{8} \geq \norm{g - g'}_{\infty}\).
Further there are
\href{https://en.wikipedia.org/wiki/Morse_theory\#Fundamental_theorems}{Morse
functions} \(f'' \colon X \rightarrow \R\) and
\(g'' \colon Y \rightarrow \R\) with
\(\norm{f' - f''}_{\infty} \leq \frac{\delta}{8} \geq \norm{g' - g''}_{\infty}\)
by Milnor (\protect\hyperlink{ref-MR0163331}{1963} corollary 6.8).
These two results together yield
\(\norm{f - f''}_{\infty} \leq \frac{\delta}{4} \geq \norm{g - g''}_{\infty}\).
By corollary 14, corollary 4, proposition 16, proposition 21, and the
previous corollary, we have \[
\begin{split}
\mu(\mathcal{C} \mathcal{E} f, \mathcal{C} \mathcal{E} g)
& \leq
\mu(\mathcal{C} \mathcal{E} f, \mathcal{C} \mathcal{E} f'') +
\mu(\mathcal{C} \mathcal{E} f'', \mathcal{C} \mathcal{E} g'') +
\mu(\mathcal{C} \mathcal{E} g'', \mathcal{C} \mathcal{E} g)
\\
& \leq
\norm{f - f''}_{\infty} +
\mu_J (\mathcal{R} \mathcal{E} f'', \mathcal{R} \mathcal{E} g'') +
\norm{g'' - g}_{\infty}
\\
& \leq
\mu_J (\mathcal{R} \mathcal{E} f'', \mathcal{R} \mathcal{E} f) +
\mu_J (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g) +
\mu_J (\mathcal{R} \mathcal{E} g, \mathcal{R} \mathcal{E} g'') +
\frac{\delta}{2}
\\
& \leq
\norm{f'' - f}_{\infty} +
\mu_J (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g) +
\norm{g - g''}_{\infty} +
\frac{\delta}{2}
\\
& \leq
\mu_J (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g) +
\delta .
\end{split}
\] Similarly we have
\(\mu_J (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g) \leq \mu(\mathcal{C} \mathcal{E} f, \mathcal{C} \mathcal{E} g) + \delta\).
Since \(\delta > 0\) was arbitrary, we have
\(\mu_J (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g) = \mu(\mathcal{C} \mathcal{E} f, \mathcal{C} \mathcal{E} g)\).
The proof for \(M\) and \(M_J\) is completely analogous.
\end{itemize}
\section{Relation to the Join Precosheaf}\label{join-precosheaf}
In the section
\protect\hyperlink{equivalence-to-descending-precosheaf}{Equivalence to
descending Precosheaf} we discussed the \(\overline{\E}\)-category of
precosheaves on \(\overline{\R}_{-\infty}\) with smoothing functor
\(\overline{\mathcal{S}}\) and the \(1\)-homomorphism \(\pi^2_*\) from
the \(D\)-category of precosheaves on \(\overline{D}\). Together with
\(\mathcal{C}\) and \(\tilde{\mathcal{C}}\) we obtain the functor
\(\pi^2_* \circ \mathcal{C}\) with the positive persistence-enhancement
\(\pi^2_* \circ \tilde{\mathcal{C}}\). And this is pretty much the
precosheaf-theoretical version of the join tree introduced by Bubenik,
de Silva, and Scott (\protect\hyperlink{ref-bubenik2014}{2014} example
1.2.3). We name \(\pi^2_* \circ \mathcal{C}\) the \emph{join
precosheaf}. With \(\pi^2_*\) being a \(1\)-homomorphism we conclude
from corollary 15 that the interleaving distances of join precosheaves
provide lower bounds to the corresponding distances of Reeb
precosheaves. Now we will see that this join precosheaf is indeed
closely related to the other versions of join trees we have seen. We
start with a self-contained description of a complete
persistence-enhancement for \(\pi^2_* \circ \mathcal{C}\) extending
\(\pi^2_* \circ \tilde{\mathcal{C}}\). To this end let
\(f \colon X \rightarrow \R\) and \(g \colon Y \rightarrow \R\) be
continuous functions and let
\((a, b), (c, d) \in \overline{\mathbb{E}}\). We set
\(\widetilde{(\pi^2_* \circ \mathcal{C})}((f, (a, b))) := (s^{-b} \circ \pi^2 \circ \Delta \circ f)_* \Lambda\).
Now let \(\varphi \colon (f, (a, b)) \rightarrow (g, (c, d))\) be a
homomorphism in \(\pm \mathbf{F}\) and let
\(U \subseteq \overline{\R}_{-\infty}\) be an open subset, then we have
\(\varphi((s^{-b} \circ \pi^2 \circ \Delta \circ f)^{-1} (U)) = \varphi((s^{-b} \circ f)^{-1} (U)) \subseteq \varphi((s^{-d} \circ f)^{-1} (U))\)
and thus the restriction
\(\varphi |_{(s^{-b} \circ f)^{-1} (U)} \colon (s^{-b} \circ f)^{-1} (U) \rightarrow (s^{-d} \circ f)^{-1} (U)\).
We set
\(\widetilde{(\pi^2_* \circ \mathcal{C})}(\varphi)_U := \Lambda \big( \varphi |_{(s^{-b} \circ f)^{-1} (U)} \big)\).
\begin{itemize}
\tightlist
\item
\textbf{Lemma.} We have
\(\widetilde{(\pi^2_* \circ \mathcal{C})} |_{\mathbf{F}} = \pi^2_* \circ \tilde{C}\).
\end{itemize}
So the positive persistence-enhancement we get from
\(\widetilde{(\pi^2_* \circ \mathcal{C})}\) coincides with
\(\pi^2_* \circ \tilde{C}\). Now we examine the negative
persistence-enhancement
\(\widetilde{(\pi^2_* \circ \mathcal{C})} |_{(-\mathbf{F})}\) and how it
relates to \(\pi^2_* \circ \mathcal{C} \circ \tilde{\mathcal{E}}\).
\begin{itemize}
\tightlist
\item
\textbf{Lemma.} The homomorphism
\((\pi^2_* \circ \mathcal{C} \circ \kappa)_f\) is an isomorphism from
\((\pi^2_* \circ \mathcal{C})(f)\) to
\((\pi^2_* \circ \mathcal{C} \circ \mathcal{E})(f)\).
\end{itemize}
The proof of this lemma is similar to the proof of lemma 19.
\begin{itemize}
\tightlist
\item
\textbf{Corollary.} The interleavings of
\((\pi^2_* \circ \mathcal{C})(f)\) and
\((\pi^2_* \circ \mathcal{C})(g)\) are in bijection to those of
\((\pi^2_* \circ \mathcal{C} \circ \mathcal{E})(f)\) and
\((\pi^2_* \circ \mathcal{C} \circ \mathcal{E})(g)\).
\end{itemize}
This corollary already captures what we care about most of the time, but
we might also like to know whether the interleavings that we get from
interleavings in \(-\mathbf{F}\) are preserved by this bijection. An
affirmative answer is provided by remark 17 and the following
\begin{itemize}
\tightlist
\item
\textbf{Lemma.} The functors \(\overline{\mathcal{S}}\),
\(\widetilde{(\pi^2_* \circ \mathcal{C})} |_{(-\mathbf{F})}\), and
\(\pi^2_* \circ \mathcal{C} \circ \tilde{\mathcal{E}}\) combine to a
negative persistence-enhancement for
\(\pi^2_* \circ \mathcal{C} \circ \kappa\).
\end{itemize}
The proof of this lemma is similar to the proof of lemma 26.
\section{Appendix}\label{appendix}
\hypertarget{constructible-spaces}{\subsection{Constructible Spaces over
the Reals}\label{constructible-spaces}}
\begin{itemize}
\tightlist
\item
\textbf{Definition.} Let
\(S = \{a_1 < a_2 < \dots < a_n\} \subset \R\) for some non-negative
integer \(n\) and let \(a_0 = -\infty\) and \(a_{n+1} = \infty\).\\
Then an \emph{\(S\)-skeleton \(X\) for an \(\overline{\R}\)-space} is
given by the following data:
\begin{itemize}
\tightlist
\item
For \(i = 1, \dots, n\) a locally path-connected compact topological
space \(V_i\).
\item
For \(i = 0, \dots, n\) a locally path-connected compact topological
space \(E_i\).
\item
For \(i = 1, \dots, n\) two continuous maps
\(l_i \colon E_i \rightarrow V_i\) and
\(r_{i-1} \colon E_{i-1} \rightarrow V_i\).
\end{itemize}
For an \(S\)-skeleton \(X\) as above we define the \emph{geometric
realization} \(|X|\) to be \[\left(
\coprod_{i=1}^n V_i \times \{a_i\}
\right)
\coprod
\coprod_{i=0}^{n} E_i \times [a_i, a_{i+1}] / \sim,\] where \(\sim\)
is the equivalence relation generated by
\((l_i(x), a_i) \sim (x, a_i)\) for \(i = 1, \dots, n\) and
\((r_i(x), a_{i+1}) \sim (x, a_{i+1})\) for \(i = 0, \dots, n-1\).
Moreover we define \(f_X \colon |X| \rightarrow \overline{\R}\) to be
the map induced by the projection onto the second factor.
An \(\overline{\R}\)-space given by a continuous map
\(g \colon Y \rightarrow \overline{\R}\) is \emph{constructible} if
there is a finite subset \(S \subset \R\) and an \(S\)-skeleton \(X\),
such that \(f_X \cong g\) as \(\overline{\R}\)-spaces.
The \(S\)-skeleton \(X\) is an \emph{\(S\)-skeleton for a bounded
\(\R\)-space} if \(E_0 = \emptyset = E_n\).
A bounded \(\R\)-space \(g \colon Y \rightarrow \R\) is
\emph{constructible} if there is a finite subset \(S \subset \R\) and
an \(S\)-skeleton \(X\) with \(E_0 = \emptyset = E_n\), such that
\(f_X \cong g\) as \(\overline{\R}\)-spaces.
\end{itemize}
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{26}
\item
\emph{Example.} The following image depicts the geometric realization
and the associated height function of an
\(\{a_1, a_2, a_3\}\)-skeleton for an \(\overline{\R}\)-space.
\includegraphics{img/mpl/constructible-example}~
\end{enumerate}
Now let \(S = \{a_1 < a_2 < \dots < a_n\} \subset \R\) for some
non-negative integer \(n\) and let \(a_0 = -\infty\) and
\(a_{n+1} = \infty\).
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{27}
\tightlist
\item
\textbf{Definition.} Let \(X\) and \(X'\) be two \(S\)-skeletons for
an \(\overline{\R}\)-space and suppose we have the following data:
\begin{itemize}
\tightlist
\item
For \(i = 1, \dots, n\) a continuous map
\(\varphi^v_i \colon V_i \rightarrow V'_i\).
\item
For \(i = 0, \dots, n\) a continuous map
\(\varphi^e_i \colon E_i \rightarrow E'_i\).
\end{itemize}
This data describes \emph{a homomorphism of \(S\)-skeletons for an
\(\overline{\R}\)-space} \(\varphi \colon X \rightarrow X'\), if the
two diagrams \[
\xymatrix{
V_i
\ar[d]_{\varphi^v_i}
&
E_i
\ar[d]^{\varphi^e_i}
\ar[l]_{l_i}
\\
V'_i
&
E'_i
\ar[l]^{l'_i}
}
\] and \[
\xymatrix{
E_{i-1}
\ar[r]^{r_{i-1}}
\ar[d]_{\varphi^e_{i-1}}
&
V_i
\ar[d]^{\varphi^v_i}
\\
E'_{i-1}
\ar[r]_{r'_{i-1}}
&
V'_i
}
\] commute for \(i = 1, \dots, n\).
The composition of two homomorphisms of \(S\)-skeletons is defined by
composing the individual maps \(\varphi^v_i\) and \(\varphi^e_i\).
\end{enumerate}
In the first definition we described the geometric realization of an
\(S\)-skeleton for an \(\overline{\R}\)-space. This picture is only
complete, if we also describe a geometric pendant to any homomorphism
between \(S\)-skeletons.
\begin{itemize}
\tightlist
\item
\textbf{Definition.} For a homomorphism
\(\varphi \colon X \rightarrow X'\) of \(S\)-skeletons for
\(\overline{\R}\)-spaces, we define the \emph{geometric realization
\(|\varphi|\) of \(\varphi\)} to be the map induced on the quotients
defined by the maps:
\begin{itemize}
\tightlist
\item
\(V_i \times \{a_i\} \rightarrow V'_i \times \{a_i\}, (p, a_i) \mapsto (\varphi^v_i (p), a_i)\)
for \(i = 1, \dots, n\).
\item
\(E_i \times [a_i, a_{i+1}] \rightarrow E'_i \times [a_i, a_{i+1}], (p, t) \mapsto (\varphi^e_i(p), t)\)
for \(i = 0, \dots, n\).
\end{itemize}
\end{itemize}
Altogether this defines a faithful functor \(|\_|\) from the category of
\(S\)-skeletons for \(\overline{\R}\)-spaces to the category of
\(\overline{\R}\)-spaces.
\subsection{Graphs over the Reals}\label{graphs-over-the-reals}
\begin{itemize}
\tightlist
\item
\textbf{Definition.} Let
\(S = \{a_1 < a_2 < \dots < a_n\} \subset \R\) for some non-negative
integer \(n\). Then an \(S\)-graph \(G\) is given by the following
data:
\begin{itemize}
\tightlist
\item
For \(i = 1, \dots, n\) a finite set \(V_i\).
\item
For \(i = 0, \dots, n\) a finite set \(E_i\).
\item
For \(i = 1, \dots, n\) two maps \(l_i \colon E_i \rightarrow V_i\)
and \(r_{i-1} \colon E_{i-1} \rightarrow V_i\).
\end{itemize}
\end{itemize}
Thinking of such sets \(V_i\) as vertices and the sets \(E_i\) as edges,
\(G\) can (almost) be seen as a
\href{https://en.wikipedia.org/wiki/Multigraph}{multigraph}.
\begin{itemize}
\tightlist
\item
\textbf{Definition.} Let
\(S = \{a_1 < a_2 < \dots < a_n\} \subset \R\) for some non-negative
integer \(n\) and let \(X\) be an \(S\)-skeleton for an
\(\overline{\R}\)-space, then we obtain an \(S\)-graph
\(\mathcal{C} X\) by applying the path-connected components functor
\(\pi_0\) to all spaces and maps defining \(X\). Moreover we may apply
\(\pi_0\) to all the individual maps \(\varphi^v_i\) and
\(\varphi^e_i\) describing a homomorphism \(\varphi\) of
\(S\)-skeletons, to obtain a functor \(\mathcal{C}\) from the category
of \(S\)-skeletons to the category of \(S\)-graphs.
\end{itemize}
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{28}
\item
\emph{Example.} If \(X\) is the \(\{a_1, a_2, a_3\}\)-skeleton
depicted in example 27, then the following image shows
\(\mathcal{C} X\).
\includegraphics{img/mpl/pi0-of-constructible-example}~
\end{enumerate}
Now let \(S = \{a_1 < a_2 < \dots < a_n\} \subset \R\) for some
non-negative integer \(n\). The definition of a homomorphism between
\(S\)-graphs is completely analogous to definition 28, homomorphisms
between \(S\)-skeletons for \(\overline{\R}\)-spaces. More precisely the
full subcategory of the category of \(S\)-skeletons for
\(\overline{\R}\)-spaces with all \(V_i\) and \(E_i\) discrete is
isomorphic to the category of \(S\)-graphs. For convenience we spell out
the details nevertheless.
\begin{itemize}
\tightlist
\item
\textbf{Definition.} Let \(G\) and \(G'\) be two \(S\)-graphs and
suppose we have the following data:
\begin{itemize}
\tightlist
\item
For \(i = 1, \dots, n\) a map
\(\varphi^v_i \colon V_i \rightarrow V'_i\).
\item
For \(i = 0, \dots, n\) a map
\(\varphi^e_i \colon E_i \rightarrow E'_i\).
\end{itemize}
This data describes \emph{a homomorphism of \(S\)-graphs}
\(\varphi \colon G \rightarrow G'\), if the two diagrams \[
\xymatrix{
V_i
\ar[d]_{\varphi^v_i}
&
E_i
\ar[d]^{\varphi^e_i}
\ar[l]_{l_i}
\\
V'_i
&
E'_i
\ar[l]^{l'_i}
}
\] and \[
\xymatrix{
E_{i-1}
\ar[r]^{r_{i-1}}
\ar[d]_{\varphi^e_{i-1}}
&
V_i
\ar[d]^{\varphi^v_i}
\\
E'_{i-1}
\ar[r]_{r'_{i-1}}
&
V'_i
}
\] commute for \(i = 1, \dots, n\).
The composition of two homomorphisms of \(S\)-graphs is defined by
composing the individual maps \(\varphi^v_i\) and \(\varphi^e_i\).
\end{itemize}
The functor \(|\_|\) defined on the category of \(S\)-skeletons for
\(\overline{\R}\)-spaces from the
\protect\hyperlink{constructible-spaces}{previous section} restricts to
the category of \(S\)-graphs, if we identify the category of
\(S\)-graphs with the full subcategory of the category of
\(S\)-skeletons for \(\overline{\R}\)-spaces with all \(V_i\) and
\(E_i\) discrete.
\begin{itemize}
\tightlist
\item
\textbf{Lemma.} The induced functor \(|\_|\) on \(S\)-graphs as
described above is full and faithful.
\end{itemize}
\hypertarget{skeleton-epigraph}{\subsection{A Skeleton for the
Epigraph}\label{skeleton-epigraph}}
Let \(S = \{a_1 < a_2 < \dots < a_n\} \subset \R\) for some non-negative
integer \(n\) and let \(X\) be an \(S\)-skeleton for a bounded
\(\R\)-space.
\begin{itemize}
\item
\textbf{Definition.} The \emph{epigraph \(\epi X\) of \(X\)} is the
\(S\)-skeleton defined by
\begin{itemize}
\tightlist
\item
\(\tilde{V}_i := f_X^{-1} ((-\infty, a_i])\) for
\(i = 1, \dots, n\),
\item
\(\tilde{E}_0 = \emptyset\),
\(\tilde{E}_i := f_X^{-1} ((-\infty, a_i]) \coprod (E_i \times [a_i, a_{i+1}]) / (l_i(x), a_i) \sim (x, a_i)\)
for \(i = 1, \dots, n-1\), and \(\tilde{E}_n := |X|\), and
\item
\(\tilde{l}_i := \left[\id \coprod l_i \circ \pi^1\right]\) and
\(\tilde{r}_{i-1}\) the canonical quotient map for
\(i = 1, \dots, n\).
\end{itemize}
\item
\emph{Example.} The left graphic in the following picture shows an
\(\{a_1, a_2, a_3\}\)-graph, which we view as an
\(\{a_1, a_2, a_3\}\)-skeleton for a bounded \(\R\)-space, by
augmenting the sets of vertices and edges with the discrete topology.
\includegraphics{img/mpl/example-epigraph}~
We ignore the colors for now. The right graphic shows the
corresponding epigraph.
\end{itemize}
Moreover there is a natural homomorphism from \(X\) to \(\epi X\).
\begin{itemize}
\tightlist
\item
\textbf{Definition.} We define the homomorphism
\(\kappa_X \colon X \rightarrow \epi X\) by the following data:
\begin{itemize}
\tightlist
\item
\(\kappa^v_{X i} \colon V_i \rightarrow \tilde{V}_i, p \mapsto (p, a_i)\)
for \(i = 1, \dots, n\).
\item
\(\kappa^e_{X i} \colon E_i \rightarrow \tilde{E}_i, p \mapsto (p, a_{i+1})\)
for \(i = 1, \dots, n-1\).
\end{itemize}
\item
\emph{Example.} In the previous example each vertex and edge of the
\(\{a_1, a_2, a_3\}\)-graph is depicted in a different color. Now
\(\kappa_X\) maps each vertex or edge to the point of the same color
in the epigraph.
\end{itemize}
Now we show that \(f_{\epi X}\) and \(\mathcal{E} f_X\) are naturally
isomorphic.
\begin{itemize}
\tightlist
\item
\textbf{Definition.} We define a continuous map \(\varphi_X\) from
\(| \epi X |\) to the
\href{https://en.wikipedia.org/wiki/Epigraph_\%28mathematics\%29}{epigraph}
\(\epi f_X\) of the continuous map \(f_X\). In some sense most of
\(| \epi X |\) can already be seen as a subset of \(\epi f_X\) and on
this part we choose \(\varphi_X\) to be the inclusion. The part where
this does not work is
\(\left( V_i \coprod (E_i \times [a_i, a_{i+1}]) / (l_i(x), a_i) \sim (x, a_i) \right) \times [a_i, a_{i+1}] / \sim\)
and on this part we define \(\varphi_X\) to be
\((p, x, y) \mapsto \left(p, a_i + (x-a_i) \frac{y-a_i}{a_{i+1} - a_i}, y\right)\).
\end{itemize}
\begin{enumerate}
\def\labelenumi{(\arabic{enumi})}
\setcounter{enumi}{29}
\tightlist
\item
\textbf{Lemma.} The map \(\varphi_X\) is a homeomorphism and we have
\(f_{|\epi X|} = \pi^2 \circ \varphi_X = \mathcal{E} f_X \circ \varphi_X\).
\end{enumerate}
\section*{References}\label{references}
\addcontentsline{toc}{section}{References}
\hypertarget{refs}{}
\hypertarget{ref-bauer2014}{}
Bauer, Ulrich, Xiaoyin Ge, and Yusu Wang. 2014. ``Measuring Distance
Between Reeb Graphs.'' In \emph{Proceedings of the Thirtieth Annual
Symposium on Computational Geometry}, 464:464--464:473. SOCG'14. New
York, NY, USA: ACM.
doi:\href{https://doi.org/10.1145/2582112.2582169}{10.1145/2582112.2582169}.
\hypertarget{ref-bauer2015}{}
Bauer, Ulrich, Elizabeth Munch, and Yusu Wang. 2015. ``Strong
Equivalence of the Interleaving and Functional Distortion Metrics for
Reeb Graphs.'' In \emph{31st International Symposium on Computational
Geometry (Socg 2015)}, edited by Lars Arge and János Pach, 34:461--75.
Leibniz International Proceedings in Informatics (Lipics). Dagstuhl,
Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik.
doi:\href{https://doi.org/http://dx.doi.org/10.4230/LIPIcs.SOCG.2015.461}{http://dx.doi.org/10.4230/LIPIcs.SOCG.2015.461}.
\hypertarget{ref-bredon1993}{}
Bredon, Glen. 1993. \emph{Topology and Geometry}. \emph{Graduate Texts
in Mathematics}. Springer New York.
doi:\href{https://doi.org/10.1007/978-1-4757-6848-0}{10.1007/978-1-4757-6848-0}.
\hypertarget{ref-BrJae1973}{}
Bröcker, Theodor, and Klaus Jänich. 1973. \emph{Einführung in Die
Differentialtopologie}. Springer-Verlag Berlin Heidelberg.
\hypertarget{ref-bubenik2014}{}
Bubenik, Peter, Vin de Silva, and Jonathan Scott. 2014. ``Metrics for
Generalized Persistence Modules.'' \emph{Foundations of Computational
Mathematics}. Springer US, 1--31.
doi:\href{https://doi.org/10.1007/s10208-014-9229-5}{10.1007/s10208-014-9229-5}.
\hypertarget{ref-MR2460372}{}
Cohen-Steiner, David, Herbert Edelsbrunner, and John Harer. 2005.
``Stability of Persistence Diagrams.'' In \emph{Computational Geometry
(SCG'05)}, 263--71. ACM, New York.
doi:\href{https://doi.org/10.1145/1064092.1064133}{10.1145/1064092.1064133}.
\hypertarget{ref-deSilva2016}{}
de Silva, Vin, Elizabeth Munch, and Amit Patel. 2016. ``Categorified
Reeb Graphs.'' \emph{Discrete \& Computational Geometry} 55.
doi:\href{https://doi.org/10.1007/s00454-016-9763-9}{10.1007/s00454-016-9763-9}.
\hypertarget{ref-deSilva2017b}{}
de Silva, Vin, Elizabeth Munch, and Anastasios Stefanou. 2017. ``Theory
of Interleavings on \([0,\infty)\)-Actegories.''
\emph{arXiv:1706.04095v1}. \url{http://arxiv.org/abs/1706.04095v1}.
\hypertarget{ref-diFabio2014}{}
Di Fabio, Barbara, and Claudia Landi. 2014. ``The Edit Distance for Reeb
Graphs of Surfaces.'' \emph{CoRR} abs/1411.1544.
\url{http://arxiv.org/abs/1411.1544}.
\hypertarget{ref-MR1277847}{}
Erné, M., J. Koslowski, A. Melton, and G. E. Strecker. 1993. ``A Primer
on Galois Connections.'' In \emph{Papers on General Topology and
Applications (Madison, WI, 1991)}, 704:103--25. Ann. New York Acad. Sci.
New York Acad. Sci., New York.
doi:\href{https://doi.org/10.1111/j.1749-6632.1993.tb52513.x}{10.1111/j.1749-6632.1993.tb52513.x}.
\hypertarget{ref-fluhr2017}{}
Fluhr, Benedikt. 2017. ``Generic 1D-Interleavings.'' Poster. Hausdorff
Research Institute for Mathematics; Spring School on Applied and
Computational Algebraic Topology
\url{https://www.him.uni-bonn.de/programs/future-programs/future-trimester-programs/acat-2017/spring-school/schedule/}
April 25th. \url{http://bfluhr.com/bucket/poster-acat01.pdf}.
\hypertarget{ref-MR1322801}{}
Funk, J. 1995. ``The Display Locale of a Cosheaf.'' \emph{Cahiers
Topologie Géom. Différentielle Catég.} 36 (1): 53--93.
\hypertarget{ref-hunter2007}{}
Hunter, J. D. 2007. ``Matplotlib: A 2D Graphics Environment.''
\emph{Computing in Science \& Engineering} 9 (3). IEEE COMPUTER SOC:
90--95.
doi:\href{https://doi.org/10.1109/MCSE.2007.55}{10.1109/MCSE.2007.55}.
\hypertarget{ref-MR0163331}{}
Milnor, J. 1963. \emph{Morse Theory}. Based on Lecture Notes by M.
Spivak and R. Wells. Annals of Mathematics Studies, No. 51. Princeton
University Press, Princeton, N.J.
\hypertarget{ref-morozov2013}{}
Morozov, Dmitriy, Kenes Beketayev, and Gunther Weber. 2013.
``Interleaving Distance Between Merge Trees.'' In \emph{Proceedings of
TopoInVis}.
\url{http://www.mrzv.org/publications/interleaving-distance-merge-trees/}.
\hypertarget{ref-saikia14a}{}
Saikia, H., H.-P. Seidel, and T. Weinkauf. 2014. ``Extended Branch
Decomposition Graphs: Structural Comparison of Scalar Data.''
\emph{Computer Graphics Forum (Proc. EuroVis)} 33 (3): 41--50.
\url{http://tinoweinkauf.net/publications/abssaikia14a.html}.
\hypertarget{ref-stacks-project}{}
Stacks Project Authors, The. 2017. ``\emph{Stacks Project}.''
\url{http://stacks.math.columbia.edu}.
\end{document}