Abstract
We propose sparse versions of filtered simplicial complexes used to compute persistent homology of point clouds and of networks. In particular, we extend the Sparse Čech Complex of Cavanna et al. (A geometric perspective on sparse filtrations. CoRR, arXiv:1506.03797, 2015) from point clouds in convex metric spaces to point clouds in arbitrary metric spaces. Along the way we formulate interleaving in terms of strict \(2\)categories, and we introduce the concept of Dowker dissimilarities that can be considered as a common generalization of metric spaces and networks.
Introduction
This paper is the result of an attempt to obtain the interleaving guarantee for the sparse Čech complex of Cavanna et al. (2015) without using the Nerve Theorem. The rationale for this was to generalize the result from convex metric spaces to arbitrary metric spaces. We have not been able to show that the constructions of Sheehy (2013) or Cavanna et al. (2015) are interleaved with the Čech complex in arbitrary metric spaces. However, changing the construction slightly, we obtain a subcomplex of the Čech complex that is interleaved in a similar way. When applied to point clouds in a convex metric space this subcomplex is homotopic to the construction of Cavanna et al. (2015). The above constructions are two examples of general constructions presented in the body of our paper.
The search for a more general version of the sparse Čech complex led us to study both different versions of filtered covers and extended metrics. We discovered that these concepts are instances of filtered relations given by functions of the form
from the product of two sets \(L\) and \(W\) to the interval \([0,\infty ]\). Here we think of \(L\) as a set of landmark points and \(W\) as a set of witness points. Given \(t \in [0,\infty )\), the relation \(\varLambda _t\) at filtration level \(t\) is
Dowker (1952) observed that a relation \(R \subseteq L \times W\) gives a cover \((R(l))_{l \in L}\) of the set
with
The Dowker complex of the relation \(R\) is the Borsuk Nerve of this cover. The Dowker Homology Duality Theorem (Dowker 1952, Theorem 1) states that the Dowker complexes of \(R\) and the transposed relation
have isomorphic homology. In Chowdhury and Mémoli (2018), Chowdhury and Mémoli have sharpened the Dowker Homology Duality Theorem to a Dowker Homotopy Duality Theorem stating that the Dowker complexes of \(R\) and \(R^T\) are homotopy equivalent after geometric realization. That result is a central ingredient in this paper.
In honor of Dowker we name functions \(\varLambda :L \times W \rightarrow [0,\infty ]\)Dowker dissimilarities. Forming the Dowker complexes of the relations \(\varLambda _t\) for \(t \in [0,\infty )\) we obtain a filtered simplicial complex, the Dowker Nerve\(N\varLambda \) of \(\varLambda \), with \(N\varLambda _t\) equal to the Dowker complex of \(\varLambda _t\).
The main result of our work is Theorem 2 on sparsification of Dowker nerves. Here we formulate it in the context of a finite set \(P\) contained in a metric space \((M,d)\). Let \(p_0,\ldots , ,p_n\) be a farthest point sampling of \(P\) with insertion radii \(\lambda _0, \ldots \lambda _n\). That is, \(p_0 \in P\) is arbitrary, \(\lambda _0 = \infty \) and for each \(0 < k \le n\), the point \(p_k \in P\) is of maximal distance to \(p_0,\ldots ,p_{k1}\), and this distance is \(\lambda _{k}\). Let \(\varepsilon > 0\) and let \(\varLambda :P \times M \rightarrow [0,\infty ]\) be the Dowker dissimilarity given by the metric \(d\), that is, \(\varLambda (p,w) = d(p,w)\). Then the Dowker Nerve \(N \varLambda \) is equal to the relative Čech complex \({\check{{\mathcal {C}}}}(P,M)\) of \(P\) in \(M\) given by the Borsuk Nerve of all balls in \(M\) centred at points in \(P\). Let \([n] = \{0, \ldots , n\}\) and let \(\varphi :[n] \rightarrow [n]\) be a function with \(\varphi (0) = 0\) and \(\varphi (k) < k\) for \(k > 0\) and
for \(k = 1,\ldots , n\). The geometric idea behind this formula is that the ball centred at \(p_k\) of radius \(\frac{(\varepsilon + 1) \lambda _k}{\varepsilon }\) is contained in the ball centred at \(p_{\varphi (k)}\) of radius \(\frac{(\varepsilon + 1)\lambda _{\varphi (k)} }{\varepsilon }\), and therefore at filtration levels greater than \(\frac{(\varepsilon + 1)\lambda _{\varphi (k)}}{\varepsilon }\) this ball can be omitted without changing the homotopy type of the nerve of the cover (Fig. 1). The Sparse Dowker Nerve of \(\varLambda \) is the filtered subcomplex \(N(\varLambda , \varphi , (\varepsilon + 1)\lambda /\varepsilon )\) of \(N\varLambda \) filtered by letting \(N(\varLambda , \varphi , (\varepsilon + 1)\lambda /\varepsilon ))_t\) consist of subsets \(\sigma \subseteq P\) such that there exists \(w \in M\) with
for every \(k,l \in \sigma \). The geometric interpretation of this formula is firstly that balls around \(p_k\) are truncated at radius \((\varepsilon + 1)\lambda _k/\varepsilon \), that is, when they reach this radius they stop growing. Secondly, the nerve is restricted in the sense that \(p_k\) is not contributing to simplices of radius greater than \((\varepsilon + 1)\lambda _{\varphi (k)}/\varepsilon \). In the geometric description of Cavanna et al. (2015), cones at \(p_k\) are truncated at width \((\varepsilon + 1)\lambda _{k}/\varepsilon \) and their tops are cut off at height \((\varepsilon + 1)^2\lambda _{k}/\varepsilon \).
Theorem 1
The Sparse Dowker Nerve \(N(\varLambda , \varphi , (\varepsilon + 1)\lambda /\varepsilon )\) is multiplicatively \((1, 1 + \varepsilon )\)interleaved with the relative Čech complex \({\check{{\mathcal {C}}}}(P,M)\) of \(P\) in \(M\).
Explicitly, there are maps \(f_t :N\varLambda _t \rightarrow N(\varLambda , \varphi , (\varepsilon + 1)\lambda /\varepsilon )_{(1+\varepsilon ) t}\) so that for the inclusion maps \(g_t :N(\varLambda , \varphi , (\varepsilon + 1)\lambda /\varepsilon )_{t} \rightarrow N\varLambda _t\), the maps \(f_t g_t\) and \(g_{(1 + \varepsilon )t} f_t\) are homotopic to the inclusion of the space of level \(t\) into the space of level \((1 + \varepsilon ) t\) of the filtered simplicial complexes \(N(\varLambda , \varphi , (\varepsilon + 1)\lambda /\varepsilon )\) and \(N\varLambda \) respectively. For \(M = {\mathbb {R}}^d\) the Sparse Dowker Nerve is closely related to the Sparse Čech Complex of Cavanna et al. (2015). We have implemented both constructions and made them available at GitHub (Brun and Blaser 2018). We also provide a tutorial that can be accessed from the same GitHub repository. It turned out that the two constructions are of similar size.
Chazal et al. (2014) witness complexes and Čech complexes are both instances of Dowker dissimilarities. The weighted Čech complex in (Buchet et al. 2016, Definition \(5.1\)) is also an instance of a Dowker complex. Also the filtered clique complex of a finite weighted undirected simple graph \(G = (V,w)\), where \(w\) is a function \(w :G \times G \rightarrow [0,\infty ]\) is an instance of a Dowker nerve: let \({{\,\mathrm{{\mathcal {P}}}\,}}(V)\) be the set of subsets of \(V\) and define
where \({{\,\mathrm{\mathrm {diam}}\,}}(X) = \max _{x,x'' \in X} w(x,x')\). Then the Dowker Nerve of \(\varLambda \) is equal to the filtered clique complex of \(G\).
For disjoint sets \(L\) and \(W\) a Dowker dissimilarity \(\varLambda :L \times W \rightarrow [0,\infty ]\) is the same thing as a weighted simple bipartite graph. On the other hand, a Dowker dissimilarity of the form \(\varLambda :X \times X \rightarrow [0,\infty ]\) is the same thing as a weighted directed graph with no multiple directed edges. Chowdhury and Mémoli (2018), call Dowker dissimilarities of this form weighted networks, and study their Dowker nerves thoroughly under the name Dowker complexes. In particular, they show that the persistent homology of the Dowker Nerve of a network is sensitive to the direction its edges. For example, for the networks \(A\) and \(B\) in Fig. 2, with selfloops of weight \(0\), the Dowker Nerve of network \(A\) is contractible while the Dowker Nerve of network \(B\) is homotopic to a circle at all filtration levels. Chowdhury and Mémoli also formulate a stability result for homology of Dowker nerves (Chowdhury and Mémoli 2018). We formulate interleaving of Dowker dissimilarities in such a way that their network distance is bounded below by our interleaving distance. Together with functoriality for interleaving distance and the Algebraic Stability Theorem (Chazal et al. 2009) this implies the stability result of Chowdhury and Mémoli (2018). In the context of metric spaces, this Stability Theorem is contained in Chazal et al. (2014).
Imposing conditions on a Dowker dissimilarity of the form
we arrive at concepts of independent interest. Most importantly, \((X,\varLambda )\) is a metric space if and only if \(\varLambda \) satisfies

Finiteness \(\varLambda (x,y) < \infty \) for all \(x,y \in X\).

Triangle inequality \(\varLambda (x,z) \le \varLambda (x,y) + \varLambda (y,z)\) for \(x,y,x \in X\).

Identity of indiscernibles \(d(x,y) = 0\) if and only if \(x = y\).

Symmetry \(d(x,y) = d(y,x)\) for all \(x,y \in X\).
Removing some of the above conditions on \(\varLambda \) leads to various generalizations of metric spaces. In particular, the situation where \(\varLambda \) only is required to satisfy the triangle inequality has been studied by Lawvere (1957). He noticed that \([0,\infty ]\) is a closed symmetric monoidal category and that when the triangle inequality holds, then \(\varLambda \) gives \(X\) the structure of a category enriched over \([0,\infty ]\).
Guided by the Strong Functorial Dowker Theorem (Chowdhury and Mémoli 2018, Theorem 3) we have chosen to work with interleavings in the homotopy category instead of on the level of homology groups. We leave it for further investigation to decide if the Functorial Dowker Theorem can be extended to homotopy interleavings in the sense of Blumberg and Lesnick (2017).
We extend the usual notion of interleaving between \([0,\infty )\)filtered objects in two ways. Firstly, we consider interleavings in \(2\)categories. We were led to do this because Dowker dissimilarities form a \(2\)category, and the proof of the Stability Theorem is streamlined by working in this generality. Secondly, following Bubenik et al. (2015), we allow interleaving with respect to order preserving functions of the form \(\alpha :[0,\infty )\rightarrow [0,\infty )\) satisfying \(t \le \alpha (t)\) for all \(t\). In this context, additive interleaving corresponds to functions of the form \(\alpha (t) = t + a\) and multiplicative interleaving corresponds to functions of the form \(\alpha (t) = ct\).
After setting terminology and notation, the proof of our main result, Theorem 2, is a quite simple application of the functorial Dowker Theorem. It consists of two parts. First, we truncate the Dowker dissimilarity associated to a metric by replacing certain distances by infinity and show that the truncated Dowker dissimilarity is interleaved with the original Dowker dissimilarity. At that point we use the functorial Dowker Theorem. Second, we give conditions that allow us to sparsify the Dowker Nerve of the truncated Dowker dissimilarity without changing the filtered homotopy type.
The paper is organized as follows: Sect. 2 presents our main result, Theorem 2. We also show how Theorem 1 is a consequence of Theorem 2 and how the Sparse Čech complex (Cavanna et al. 2015) fits into this context. Section 3 shows that, under certain conditions, when some of the values \(\varLambda (l,w)\) in a Dowker dissimilarity are set to infinity, the homotopy type of the Dowker Nerve is only changed up to a certain interleaving. This is the first step in our proof of Theorem 2. In Sect. 4, we give a criterion ensuring that a certain subcomplex is homotopy equivalent to the Dowker Nerve of a Dowker dissimilarity. In Sect. 5, we present the homotopy category of simplicial complexes. In Sect. 6, we recollect basic terminology about \(2\)categories. The main motivation for going to this level of generality is that interleaving distance in the \(2\)category \(\mathrm {Dow}\) of Dowker dissimilarities defined in Definition 32 generalizes network distance from Chowdhury and Mémoli (2018). In Sect. 7, we introduce the \(2\)category of sets and relations. Section 8 uses the Dowker Nerve construction to define a \(2\)category with relations as objects. Section 9 introduces interleavings in \(2\)categories. In Sect. 10, we define the \(2\)category of Dowker dissimilarities. In Sect. 11, we relate interleaving distance of Dowker dissimilarities to Gromov–Hausdorff distance of metric spaces. We finish with some concluding remarks in Sect. 12.
Sparse nerves of truncated Dowker dissimilarities
In this section, we state and motivate our main results, postponing proofs to later sections.
Definition 1
A Dowker dissimilarity\(\varLambda \) consists of two sets \(L\) and \(W\) and a function \(\varLambda :L \times W \rightarrow [0,\infty ]\). Given \(t \in [0,\infty )\), we let
The Dowker Nerve of \(\varLambda \) is the filtered simplicial complex \(N\varLambda = (N\varLambda _t)_{t \ge 0}\) with
The zero set of \(\varLambda \) is
The triangle inequality is central in the work of Cavanna et al. (2015), and it will also play a central role for us. For Dowker dissimilarities we need extra structure in order to formulate the triangle inequality.
Definition 2
A Dowker dissimilarity \(\varLambda :L \times W \rightarrow [0,\infty ]\) satisfies the triangle inequality if the following holds:

1.
For every \(w \in W\) there exists \(l \in L\) with \(\varLambda (l,w) = 0\).

2.
For all \((l,w) \in L \times W\) with \(\varLambda (l,w) = 0\) and all \((l',w') \in L \times W\), the triangle inequality
$$\begin{aligned} \varLambda (l',w') \le \varLambda (l',w) + \varLambda (l,w') \end{aligned}$$holds.
Note that if \(\varLambda \) satisfies the triangle inequality and if both \(\varLambda (l,w) = 0\) and \(\varLambda (l',w) = 0\), then for every \(w' \in W\) the triangle inequality implies that
and thus by symmetry \(\varLambda (l',w') = \varLambda (l,w')\). Also note that if \(\varLambda \) is actually a metric \(\varLambda :L \times L \rightarrow [0,\infty ]\), then it satisfies the triangle inequality in the above sense.
Unfortunately the Sparse Dowker Nerve presented in this paper needs a Dowker dissimilarity satisfying the triangle inequality as input. There are many interesting examples of Dowker dissimilarities where it is not satisfied. For example the triangle inequality is rarely satisfied for weighted networks or Bregman divergences. Typical examples of Dowker dissimilarities satisfying the triangle inequality are quasimetrics and pseudometrics.
The following concept of insertion pairs is the crucial ingredient in Sect. 3 where we treat interleaving of truncated Dowker Nerves.
Definition 3
An insertion pair for\(\varLambda \) consists of a pair \((f, \lambda )\) of functions \(f :W \times [0,\infty ]\rightarrow W\) and \(\lambda :W \rightarrow [0,\infty ]\) with the property that for every \((l,w) \in L \times W\) with \(\varLambda (l,w) = 0\) and every \(t \ge 0\) the inequalities
are satisfied.
Insertion pairs generalize farthest point samples. Let \(d :W \times W \rightarrow [0,\infty ]\) be a metric and \(w_0, \ldots , w_n\) be a farthest point sample with insertion times \(\lambda _0, \ldots , \lambda _n\). Then the functions \(\lambda (w_i) = \lambda _i\) and \(f(w, t) = {{\,\mathrm{\mathrm {argmin}}\,}}_{w_i \in W}\{d(w, w_i) \mid \lambda _i > t\}\) are an insertion pair.
For Dowker dissimilarities of the form \(\varLambda :L \times [n] \rightarrow [0,\infty ]\) satisfying the triangle inequality the following definition gives an example of an insertion pair for \(\varLambda \). Here and throughout this paper we will use the notation \([n] = \{0,\ldots ,n\}\).
Definition 4
Let \(\varLambda :L \times [n] \rightarrow [0,\infty ]\) be a Dowker dissimilarity satisfying the triangle inequality. The canonical insertion function for\(\varLambda :L \times [n] \rightarrow [0,\infty ]\) is the function \(\lambda _\varLambda :[n] \rightarrow [0,\infty ]\) defined as
The canonical insertion pair for\(\varLambda \) is the pair \((f_\varLambda ,\lambda _{\varLambda })\) where the function
is defined as follows: Given \(w \in [n]\) and \(t \ge 0\), pick \(l \in L\) with \(\varLambda (l,w) =0\) and define
The definition of \(f_{\varLambda }(w,t)\) is independent of the choise of \(l\) and the set
is nonempty because
Also, by construction \(\varLambda (l,w) = 0\) implies that
The following lemma summarizes this discussion.
Lemma 1
Let \(\varLambda :L \times [n] \rightarrow [0,\infty ]\) be a Dowker dissimilarity satisfying the triangle inequality. Then the canonical insertion pair \((f_\varLambda ,\lambda _{\varLambda })\) is an insertion pair for \(\varLambda \).
The Sparse Čech Nerve of Cavanna et al. (2015) is constructed with a positive number \(\varepsilon \) as a parameter controlling its quality in the sense that the Sparse Čech Nerve is multiplicatively \((1, 1 + \varepsilon )\)interleaved with the Čech Nerve. The following definition allows us to construct Sparse Dowker Nerves that are \(({{\,\mathrm{\mathrm {id}}\,}}, \alpha )\)interleaved with the Dowker Nerve for a large class of translation functions \(\alpha :[0,\infty )\rightarrow [0,\infty )\). Here a translation function is an orderpreserving function \(\alpha :[0,\infty )\rightarrow [0,\infty )\) with the property that \(\alpha (t) \ge t\) for every \(t \in [0,\infty )\). In the following definition, we use the generalized inverse of order preserving functions (see e.g. Embrechts and Hofert 2013 for more details).
Definition 5
Let \(\alpha :[0,\infty ]\rightarrow [0,\infty ]\) be order preserving with
The generalized inverse function \(\alpha ^{\leftarrow } :[0,\infty ]\rightarrow [0,\infty ]\) is the order preserving function
The above definition can be summarized as follows:
Definition 6
Let \(\beta :[0,\infty ]\rightarrow [0,\infty ]\) be an order preserving function. The translation function associated to\(\beta \) is the function \(\alpha :[0,\infty ]\rightarrow [0,\infty ]\) defined by
The first step in the construction of a Sparse Dowker Nerve of a Dowker dissimilarity \(\varLambda \), is to truncate \(\varLambda \) by replacing some of the values \(\varLambda (l,w)\) by \(\infty \). In the Euclidean case, this means that we truncate cones by only allowing them to grow to a certain width, as illustrated in Fig. 1. With the objective of the Sparse Dowker Nerve being \((\alpha , {{\,\mathrm{\mathrm {id}}\,}})\)interleaved with the Dowker Nerve in the sense of Definition 28. We do this as follows:
Definition 7
Let \(\varLambda :L \times W \rightarrow [0,\infty ]\) be a Dowker dissimilarity satisfying the triangle inequality and let \((f, \lambda )\) be an insertion pair for \(\varLambda \). Let \(\beta :[0,\infty ]\rightarrow [0,\infty ]\) be an order preserving function with \(\lim _{t \rightarrow \infty }\beta (t) = \infty \) and let \(\alpha \) be the translation function associated to \(\beta \). The \(\beta \)truncation function\(\lambda _{\beta } :W \rightarrow W\)associated to\(\lambda \) is the function
The \((\lambda , \beta )\)truncation of \(\varLambda \) is the Dowker dissimilarity \(\varLambda ^{(\lambda ,\beta )} :L \times W \rightarrow [0,\infty ]\) defined by
Example 1
Let \(\varLambda :L \times [n] \rightarrow [0,\infty ]\) be a Dowker dissimilarity satisfying the triangle inequality. Given \(a \ge 0\) and \(\varepsilon > 0\), we define \(\beta (t) = a + \varepsilon t\) for \(t \in [0,\infty ]\). The translation function \(\alpha \) associated to \(\beta \) is the affine function \(\alpha (t) = a + (1+\varepsilon )t\), and the function \(\alpha \beta ^{\leftarrow }\) is given by the formula
In Theorem 2 below we state that persistent homology of the \( (\lambda , \beta ) \)truncation of \(\varLambda \) is \((\alpha , {{\,\mathrm{\mathrm {id}}\,}})\)interleaved with the persistent homolgoy of \(\varLambda \).
The last step in the construction of a Sparse Dowker Nerve of a Dowker dissimilarity \(\varLambda \), is to restrict the Dowker Nerve of its transposed Dowker dissimilarity\(\varLambda ^T :W \times L \rightarrow [0,\infty ]\) given by \(\varLambda ^T(w,l) = \varLambda (l,w)\). By restricting we mean that \(w \in W\) is not contributing to simplices of radius greater than a certain threshold. The purpose of the following definition is to give such a threshold.
Definition 8
Let \(\varLambda :L \times [n] \rightarrow [0,\infty ]\) be a Dowker dissimilarity and let \(\lambda :[n] \rightarrow [0,\infty ]\) be a function with \(\lambda (w) < \infty \) for \(w > 0\) and \(\lambda (0) = \infty \). The parent function for\(\varLambda \)with respect to\(\lambda \) is the function
defined by \(\varphi (0) = 0\) and
for \(w > 0\) in \([n]\).
Note that if \(w > 0\), then \(\lambda (w) < \infty \) and \(\lambda (w) < \lambda (\varphi (w))\). Also note that the parent function is not necessarily uniquely defined because there may be more than one \(w'\) with \(\lambda (w')\) minimal under the condition that both \(\lambda (w') > \lambda (w)\) and \(\varLambda (l,w) < \lambda (w)\) implies \( \varLambda (l, w') < \lambda (w')\). We now give the last ingredient in the construction of the Sparse Dowker Nerve.
Definition 9
Let \(\varGamma :[n] \times W \rightarrow [0,\infty ]\) be a Dowker dissimilarity. Given functions \(\varphi :[n] \rightarrow [n]\) and \(\lambda :[n] \rightarrow [0,\infty ]\), the sparse nerve of\(\varGamma \)with respect to\(\lambda \)and\(\varphi \) is the filtered simplicial complex \(N(\varGamma , \varphi , \lambda )\) with \(N(\varGamma , \varphi , \lambda )(t)\) consisting of all \(\sigma \subseteq [n]\) so that there exists \(w \in W\) with
In abbreviated form the simplicial complex \(N(\varGamma , \varphi , \lambda )(t)\) is
We are ready to state our main result about the Sparse Dowker Nerve:
Theorem 2
Let \(\varLambda :L \times [n] \rightarrow [0,\infty ]\) be a Dowker dissimilarity satisfying the triangle inequality and with \(\varLambda (l,0) < \infty \) for every \(l\in L\). Let \(\beta :[0,\infty ]\rightarrow [0,\infty ]\) be an order preserving function with \(\beta (t) < \infty \) for \(t < \infty \) and \(\lim _{t\rightarrow \infty } \beta (t) = \infty \) and let \(\lambda _\beta \) be the \(\beta \)truncation function associated to the canonical insertion function for \(\varLambda \). If we let \(\varphi \) be the parent function for \(\varLambda \) with respect to \(\lambda _{\beta }\) and write \(\varGamma = (\varLambda ^{(\lambda _{\varLambda }, \beta )})^T\), then the Dowker Nerve \(N\varLambda ^T\) of \(\varLambda ^T\) is \((\alpha , {{\,\mathrm{\mathrm {id}}\,}})\)interleaved with the filtered simplicial complex \(N(\varGamma , \varphi , \lambda _\beta )\).
Proof
We show the interleaving in four steps
where Proposition 2 (P2) gives the interleaving and the homotopy equivalences are given by the Strong Functorial Dowker Theorem (Chowdhury and Mémoli 2018, Theorem 3) (FDT) and Proposition 3 (P3).
More precisely, the functorial Dowker Theorem (Chowdhury and Mémoli 2018, Theorem 3) implies that the filtered simplicial complexes \(N\varLambda \) and \(N\varLambda ^T\) are homotopy equivalent. By construction in Definitions 6 and 7, if \(\varGamma (k, l) < \infty \) then \(\varGamma (k, l) < \lambda _\beta (k)\). Therefore, by Proposition 3 the filtered simplicial complexes \(N(\varGamma , \varphi , \lambda _{\beta })\) and \(N\varGamma \) are homotopy equivalent. The Strong Functorial Dowker Theorem (Chowdhury and Mémoli 2018, Theorem 3) implies that the filtered simplicial complexes \(N\varGamma \) and \(N(\varLambda ^{(\lambda _{\varLambda }, \beta )})\) are homotopy equivalent. By Lemma 1 the pair \((f_\varLambda , \lambda _\varLambda )\) is an insertion pair for \(\varLambda \), so by Proposition 2 the filtered simplicial complexes \(N \varLambda \) and \(N(\varLambda ^{(\lambda _{\varLambda }, \beta )})\) are \((\alpha , {{\,\mathrm{\mathrm {id}}\,}})\)interleaved. \(\square \)
Remark 1
The Dowker Theorem (Dowker 1952, Theorem 1a) implies that the persistent homology of \(N\varLambda \) is isomorphic to the persistent homology of \(N\varLambda ^T\) and that the persistent homology of \(N\varGamma \) is isomorphic to the persistent homology of \(N(\varLambda ^{(\lambda _{\varLambda }, \beta )})\). Thus, if we are only interested in persistent homology, we do not need the Functorial Dowker Theorem.
Corollary 1
Let \(\varLambda :L \times [n] \rightarrow [0,\infty ]\) be a Dowker dissimilarity satisfying the triangle inequality and with \(\varLambda (l,0) < \infty \) for every \(l\in L\) and let \(\beta :[0,\infty ]\rightarrow [0,\infty ]\) be the function
and let \(\alpha :[0,\infty ]\rightarrow [0,\infty ]\) be the translation function
associated to \(\beta \). For \(\lambda _\beta \) the \(\beta \)truncation function associated to the canonical insertion function of \(\varLambda \) and \(\varphi \) the parent function for \(\varLambda \) with respect to \(\lambda _\beta \), the Dowker Nerve \(N\varLambda ^T\) of \(\varLambda ^T\) is \((\alpha , {{\,\mathrm{\mathrm {id}}\,}})\)interleaved with the filtered simplicial complex
Specializing even further, we obtain a variation of the Sparse Čech complex of Cavanna et al. (2015). Recall that the Hausdorff distance of a metric space \(L = (L,d)\) and a subset \(P\) of \(L\) is
In the following result we have in mind the situation where \(L\) is a compact submanifold of Euclidean space \({\mathbb {R}}^d\) with convex hull \(M\) and \(P\) is a sample of points from \(L\). Note that in this situation the relative Čech complexes \(\check{{\mathcal {C}}}(L,M)\) and \(\check{{\mathcal {C}}}(L, {\mathbb {R}}^d)\) are homotopy equivalent.
Corollary 2
Let \((M,d)\) be a metric space, let \(L \subseteq M\) be a compact subset, let \(P\) be a finite subset of \(L\) and let \([n] \xrightarrow p P\) be a bijection. Let \(\varLambda :M \times [n] \rightarrow [0,\infty ]\) be the function
where we write \(p_w = p(w)\). Let \(\varepsilon > 0\) and let \(\beta :[0,\infty ]\rightarrow [0,\infty ]\) be the function \( \beta (t) = \varepsilon t\) with associated translation function \(\alpha (t)=(\varepsilon + 1)t\). For \(\lambda _\beta \) the \(\beta \)truncation function associated to the canonical insertion function of \(\varLambda \) and \(\varphi \) the parent function for \(\varLambda \) with respect to \(\lambda _\beta \), the Dowker Nerve \(N\varLambda ^T\) of \(\varLambda ^T\) is \((\alpha , {{\,\mathrm{\mathrm {id}}\,}})\)interleaved with the filtered simplicial complex
Moreover, the Dowker Nerve of \(N\varLambda ^T\) is additively \((0, d_{H}(L,P))\)interleaved with the relative Čech complex \(\check{{\mathcal {C}}}(L,M)\) consisting of all balls in \(M\) with centers in \(L\).
Sometimes we refer to the relative Čech complex \(\check{{\mathcal {C}}}(L,M)\) as the ambient Čech complex and to the relative Čech complex \(\check{{\mathcal {C}}}(L,L)\) as the intrinsic Čech complex of \(L\).
Proof
Corollary 1 gives that \(N\varLambda \) is \((\alpha , {{\,\mathrm{\mathrm {id}}\,}})\)interleaved with
For the second statement, first note that \(N\varLambda ^T\) is homotopy equivalent to the relative Čech complex \(\check{{\mathcal {C}}}(P,M)\). Thus it suffices to show that the Čech complexes \(\check{{\mathcal {C}}}(P,M)\) and \(\check{{\mathcal {C}}}(L,M)\) are additively \((0, d_{H}(L,P))\)interleaved. Since \(P \subseteq L\), for every \(t \in [0,\infty )\), there is an inclusion \(\iota _t :\check{{\mathcal {C}}}_t(P,M) \rightarrow \check{{\mathcal {C}}}_t(L,M)\). Let \(f :L \rightarrow P\) be a function with \(d(l,f(l)) \le d_{H}(L,P)\) for every \(l \in L\). The triangle inequality implies that \(f\) induces a morphism \(f_t :\check{{\mathcal {C}}}_t(L,M) \subseteq \check{{\mathcal {C}}}_{t+d_{H}(L,P)}(L,M)\). By construction the composites \(f_t \iota _t\) and \(\iota _{t+d_{H}(L,P)} f_t\) are contiguous to the respective identity maps, and thus their geometric realizations are homotopic Spanier (1966). \(\square \)
Finally, we show that the Sparse Čech complex of Cavanna et al. (2015) is an instance of a Sparse Dowker Nerve. We suspect that Cavanna et al.’s construction performed to Dowker dissimilarities is homotopy equivalent to the Sparse Dowker Nerve but we have not been able to prove this. However, the following result, together with the first part of the proof of (Cavanna et al. 2015, Theorem 5) implies that the Cavanna et al.’s Sparse Čech Nerve is homotopy equivalent to the Sparse Dowker Nerve for the Dowker dissimilarities in the following proposition.
Proposition 1
Let \(d\) be a convex metric on \({\mathbb {R}}^d\) and let \(P\) be a finite subset of \({\mathbb {R}}^d\) together with a greedy order \([n] \xrightarrow p P\). Let the function \(\varLambda :{\mathbb {R}}^d \times [n] \rightarrow [0,\infty ]\) be given by
where we write \(p_w = p(w)\). Let \(\varepsilon > 0\) and let \(\beta :[0,\infty ]\rightarrow [0,\infty ]\) and \(\alpha :[0,\infty ]\rightarrow [0,\infty ]\) be the functions \(\beta (t) = \varepsilon t\) and \(\alpha (t) = (1 + \varepsilon )t\). Let \(\lambda _\varLambda \) be the canonical insertion function for \(\varLambda \) and let \(\lambda = ((1+\varepsilon )^2/\varepsilon ) \lambda _{\varLambda }\). Then the filtered simplicial complex
is isomorphic to the filtered simplicial complex \(\bigcap _{\varepsilon ' > \varepsilon } C(\varepsilon ')\) where
and \(S(\varepsilon ') = \{S^t(\varepsilon ')\}_{t \ge 0}\) is the sparse Čech complex constructed in (Cavanna et al. 2015, Sect. 4) for the parameter \(\varepsilon '\).
Proof
A subset \(\sigma \subseteq [n]\) is in
if and only if there exists \(w \in {\mathbb {R}}^d\) so that for all \(l \in \sigma \) we have
Moreover
if and only if there exists \(w \in {\mathbb {R}}^d\) so that for all \(k,l \in \sigma \) we have \(d(p_k,w) < t\) and
On the other hand, \(\sigma \in \bigcup _{s < t}S^s(\varepsilon ')\) if and only if there exists \(s < t\) and \(w \in {\mathbb {R}}^d\) so that \(w \in b_l(s)\) for all \(l \in \sigma \). By the definition of \(b_l(s)\) in Cavanna et al. (2015), Sect. 3, this is the case if and only if \(s < t\) and
for every \(l \in \sigma \). We conclude that \(\sigma \in S^t\) if and only if there exists \(w \in {\mathbb {R}}^d\) satisfying \(d(p_l,w) < t\) and
for all \(k,l \in \sigma \). \(\square \)
We have not performed any complexity analysis of Sparse Dowker Nerves. Instead we have made proofofconcept implementations of both the Sparse Čech Complex of Cavanna et al. (2015) described in Proposition 1 and the Sparse Dowker Nerve described in Corollary 2. These implementations come with the same interleaving guarantees, but for practical reasons concerning the miniball algorithm we consider complexes that are slightly bigger than the ones described above. More specifically, we compute filtration values using the miniball algorithm instead of computing radius of simplices in the truncated Dowker nerve. This gives us a filtered simplicial complex that lies between the truncated Dowker nerve and the full Dowker nerve, so it has the same interleaving guarantee as the truncated Dowker nerve.
We have tested these implementations on the following data: the optical patch data sets called \(X(300,30)\) and \(X(15,30)\) in Carlsson et al. (2008), \(6040\) points from the cyclooctane conformation space as analysed in Zomorodian (2012), the Clifford data set consisting of \(2000\) points on a curve on a torus considered in Oudot (2015), Chapter 5, and the double torus from Dey et al. (2016) (Table 1). Computing the Sparse Čech complexes and the Sparse Dowker Nerves on these data sets with the same interleaving constant \(\varepsilon \) the resulting simplicial complexes are almost of the same size, with the size of the Sparse Dowker Nerve slightly smaller than the size of the Sparse Čech Complex. Our implementations, the data sets mentioned above and the scripts used to run compute persistent homology are available (Brun and Blaser 2018).
Truncated Dowker dissimilarities
In this section, we provide the interleaving guarantee for the truncated Dowker dissimilarity used in the first step of the construction of the Sparse Dowker Nerve.
Lemma 2
Let \(\varLambda :L \times W \rightarrow [0,\infty ]\) be a Dowker dissimilarity satisfying the triangle inequality and let \((f, \lambda )\) be an insertion pair for \(\varLambda \). If \(\beta :[0,\infty ]\rightarrow [0,\infty ]\) is an order preserving function satisfying \(\beta (t) < \infty \) for \(t < \infty \) and \(\lim _{t \rightarrow \infty } \beta (t) = \infty \) with associated translation function \(\alpha :[0,\infty ]\rightarrow [0,\infty ]\), then for every \(t \in [0,\infty )\), the simplicial complex \(N\varLambda _t\) is contained in the simplicial complex \(N\varLambda ^{(\lambda ,\beta )}_{\alpha (t)}\).
Proof
Let \(t \in [0, \infty )\) and \(\sigma \in N\varLambda _t\). We need to show that \(\sigma \in N\varLambda ^{(\lambda ,\beta )}_{\alpha t}\). Pick \(w \in W\) with \(\varLambda (l,w) < t\) for all \(l \in \sigma \). Since \(\varLambda \) satisfies the triangle inequality we can pick \(l_0 \in L\) so that \(\varLambda (l_0,w) = 0\). Let \(w_0 = f(w,\beta (t))\). Since \((f, \lambda )\) is an insertion pair for \(\varLambda \) we have
The triangle inequality for \(\varLambda \) now gives
Let \(l \in \sigma \). Since \(\varLambda (l, w) < t\) and \(\varLambda (l_0, w_0) \le \beta (t)\), we get that
The inequality \(\beta (t) < \lambda (w_0)\) implies that the set \(A = \{s \, \mid \, \lambda (w_0) \le \beta (s)\}\) is contained in \((t,\infty )\). By definition \(\beta ^{\leftarrow }(\lambda (w_0)) = \inf A\), so we get \(t \le \beta ^{\leftarrow }(\lambda (w_0))\). Since \(\alpha \) is order preserving this gives \(\alpha (t) \le \alpha \beta ^{\leftarrow }(\lambda (w_0))\) and thus \(\varLambda (l,w_0) < \alpha \beta ^{\leftarrow } (\lambda (w_0))\). We conclude that \(\sigma \in N\varLambda ^{(\lambda , \beta )}_{\alpha (t)}\). \(\square \)
Proposition 2
Let \(\varLambda :L \times W \rightarrow [0,\infty ]\) be a Dowker dissimilarity satisfying the triangle inequality and let \((f, \lambda )\) be an insertion pair for \(\varLambda \). If \(\beta :[0,\infty ]\rightarrow [0,\infty ]\) is an order preserving function satisfying \(\beta (t) < \infty \) for \(t < \infty \) and \(\lim _{t \rightarrow \infty } \beta (t) = \infty \) with associated translation function \(\alpha :[0,\infty ]\rightarrow [0,\infty ]\), then the filtered simplicial complexes \(N\varLambda \) and \(N\varLambda ^{(\lambda ,\beta )}\) are \((\alpha , {{\,\mathrm{\mathrm {id}}\,}})\)interleaved.
Proof
By Lemma 2, for every \(t \in [0,\infty )\), the simplicial complex \(N\varLambda _t\) is contained in the simplicial complex \(N\varLambda ^{(\lambda ,\beta )}_{\alpha (t)}\). Since \(\varLambda (l,w) \le \varLambda ^{(\lambda ,\beta )}(l,w)\) for all \((l,w) \in L \times W\), the simplicial complex \(N\varLambda ^{(\lambda ,\beta )}_{t}\) is contained in the simplicial complex \(N\varLambda _t\) for every \(t \in [0,\infty )\). \(\square \)
Sparse Dowker nerves
In this section, we provide the technical result ensuring that the Dowker Nerve of the truncated Dowker dissimilarity can be further sparsified without changing its homotopy type.
Proposition 3
Let \(\varLambda :[n] \times W \rightarrow [0,\infty ]\) be a Dowker dissimilarity and let \(\varphi :[n] \rightarrow [n]\) be a parent function for \(\varLambda ^T\) with respect to \(\lambda :[n] \rightarrow [0,\infty ]\). If \(\varLambda (l,w) < \infty \) implies \(\varLambda (l,w) < \lambda (l)\), then for every \(t \in [0,\infty )\) the inclusion
is a homotopy equivalence.
Proof
By permuting the elements of \([n]\) we can, without loss of generality, assume that
Note that if \(\varphi (l) > 0\), then \(\lambda (\varphi (l)) < \lambda (\varphi (\varphi (l))\), and deduce that \(l > \varphi (l)\) for every \(l > 0\).
Let \(t \in [0,\infty )\). We will prove the assertion by induction on \(n\). The statement obviously holds when \(\lambda (\varphi (n)) \ge t\). In particular, it holds for \(n = 0\). Let \(n \ge 1\) and suppose by induction that the statement holds for \(n1\). We assume that \(\lambda (\varphi (n)) < t\) since otherwise the statement obviously holds for \(n\). Let \(\varLambda ' :[n1] \times W \rightarrow [0,\infty ]\) be the restriction of \(\varLambda \) to \([n1] \times W \subseteq [n] \times W\) and let \(\lambda '\) and \(\varphi '\) the restrictions of \(\lambda \) and \(\varphi \) to \([n1]\). Then \(\varphi '\) is the parent function for \(\varLambda '\) with respect to \(\lambda '\) so the induction hypothesis is satisfied for \(\varLambda ', \varphi '\) and \( \lambda '\).
We define \(f_t :[n] \rightarrow [n1]\) by
Given \(\sigma \in N\varLambda _t\) we claim that \(\sigma \cup f_t(\sigma ) \in N\varLambda _t\). If \(n \notin \sigma \), then this claim is trivial. In order to justify the claim when \(n \in \sigma \), we pick \(w \in W\) with \(\varLambda (l,w) < t\) for every \(l \in \sigma \). By our assumption on \(\varLambda \) we then also have \(\varLambda (l,w) < \lambda (l)\) for every \(l \in \sigma \). By definition of the parent function, \(\varLambda (n,w) < \lambda (n)\) implies \(\varLambda (\varphi (n),w)< \lambda (\varphi (n)) < t\). We conclude that \(\sigma \cup f_t(\sigma ) \in N\varLambda _t\).
Our next claim is that if \(\sigma \in N(\varLambda , \varphi , \lambda )(t)\), then \(\sigma \cup f_t(\sigma ) \in N(\varLambda , \varphi , \lambda )(t)\). Again, we only need to consider the case \(n \in \sigma \). We have already shown that \(\sigma \cup f_t(\sigma ) \in N \varLambda _t\). Since \(n\) is maximal in \([n]\) we have \(\lambda (\varphi (l)) \ge \lambda (\varphi (n))\) for every \(l \in [n]\), so this claim follows since \(\varLambda (n,w) < \lambda (n)\) implies \(\varLambda (\varphi (n),w) < \lambda (\varphi (n))\).
In particular, we can now conclude that the function \(f_t :[n] \rightarrow [n1]\) and defines simplicial maps
and
On the other hand, the inclusion \(\iota :[n1] \rightarrow [n]\) defines simplicial maps (see Sect. 5)
and
Moreover the above claims imply that the compositions
and
are contiguous to the identity maps. Since \(f_t \iota \) is the identity this implies that geometric realizations of the inclusions
and
are homotopy equivalences. Since we have assumed by induction that the geometric realization of the inclusion
is a homotopy equivalence, we can conclude that the geometric realization of the inclusion
is a homotopy equivalence. \(\square \)
The homotopy category of simplicial complexes
The rest of the paper is aimed at stability results for Dowker Nerves. First we need some prerequisites on the homotopy category.
Recall that a simplicial complex \(K = (V,K)\) consists of a vertex set \(V\) and a set \(K\) of finite subsets of \(V\) with the property that if \(\sigma \) is a member of \(K\), then every subset of \(\sigma \) is a member of \(K\). Given a subset \(V' \subseteq V\) and a simplicial complex \(K = (V,K)\), we write \(K_{V'}\) for the simplicial complex \(K_{V'} = (V',K_{V'})\) consisting of subsets of \(V'\) of the form \(\sigma \cap V'\) for \(\sigma \in K\). The geometric realization of a simplicial complex \(K = (V,K)\) is the space \(K\) consisting of all functions \(f :V \rightarrow [0,1]\) satisfying:

1.
The support \(\{v \in V \, \mid \, f(v) \ne 0\}\) of \(f\) is a member of \(K\)

2.
\(\sum _{v \in V} f(v) = 1\).
If \(V\) is finite, then \(K\) is given the subspace topology of the Euclidean space \({\mathbb {R}}^V\). Otherwise \(U \subseteq K\) is open if and only if for every finite \(V' \subseteq V\), the set \(U \cap K_{V'}\) is open in \(K_{V'}\).
The order complex of a partially ordered set \((X, \le )\) is the simplicial complex with vertex set \(X\) consisting of totally ordered finite subsets of \(X\), that is, subsets of the form \(\sigma = \{x_0,x_1,\ldots , x_k\}\) with \(x_0< x_1 < \cdots x_k\).
A simplicial map\(f :K \rightarrow L\) of simplicial complexes \(K = (V,K)\) and \(L = (W,L)\) consists of a function \(f :V \rightarrow W\) such that
is in \(L\) for every \(\sigma \in K\). Observe that a simplicial map \(f :K \rightarrow L\) induces a continuous map \(f :K \rightarrow L\) of geometric realizations and that this promotes the geometric realization to a functor \(\, \cdot \,  :\mathrm {Cx}\rightarrow \mathrm {Top}\) from the category \(\mathrm {Cx}\) of simplicial complexes and simplicial maps to the category \(\mathrm {Top}\) of topological spaces and continuous maps.
Definition 10
The homotopy category\(\mathrm {hCx}\)of simplicial complexes has the class of simplicial complexes as objects. Given simplicial complexes \(K\) and \(L\), the morphism set \(\mathrm {hCx}(K,L)\) is the set of homotopy classes of continuous maps from the geometric realization of \(K\) to the geometric realization of \(L\). Composition in \(\mathrm {hCx}\) is given by composition of functions representing homotopy classes.
We remark in passing that the homotopy category of simplicial complexes is equivalent to the weak homotopy category of topological spaces.
Background on \(2\)categories
We have chosen to reason about stability in the context of \(2\)categories. The payoff from this high level of abstraction is that the proofs get relatively easy. In this section, we present some terminology on \(2\)categories. Most of this material is taken from Leinster (1998).
Recall that a \(2\)category \({\mathcal {C}}\) consists of

1.
A class of objects \(A,B,\ldots \)

2.
For all objects \(A, B\) a category \({\mathcal {C}}(A,B)\). The objects of \({\mathcal {C}}(A,B)\) are the morphisms in \({\mathcal {C}}\) and the morphisms \(\alpha :f \Rightarrow g\) of \({\mathcal {C}}(A,B)\) are the \(2\)cells in \({\mathcal {C}}\).

3.
For every object \(A\) of \({\mathcal {C}}\) there is an identity morphism \({{\,\mathrm{\mathrm {id}}\,}}_A :A \rightarrow A\) and an identity \(2\)cell \({{\,\mathrm{\mathrm {id}}\,}}_{{{\,\mathrm{\mathrm {id}}\,}}_A} :{{\,\mathrm{\mathrm {id}}\,}}_A \Rightarrow {{\,\mathrm{\mathrm {id}}\,}}_A\).

4.
For all objects \(A\), \(B\) and \(C\) of \({\mathcal {C}}\) there is a functor
$$\begin{aligned} {\mathcal {C}}(A,B) \times {\mathcal {C}}(B,C)&\rightarrow {\mathcal {C}}(A,C) \\ (f,g)&\mapsto g \cdot f, \end{aligned}$$which is associative and admits the identity morphisms and identity \(2\)cells of \({\mathcal {C}}\) as identities.
Definition 11
Given \(2\)categories \({\mathcal {C}}\) and \({\mathcal {D}}\), a functor\(F :{\mathcal {C}}\rightarrow {\mathcal {D}}\) consists of

1.
A function \(F :{{\,\mathrm{\mathrm {ob}}\,}}{\mathcal {C}}\rightarrow {{\,\mathrm{\mathrm {ob}}\,}}{\mathcal {D}}\)

2.
Functors \(F :{\mathcal {C}}(A,B) \rightarrow {\mathcal {D}}(FA,FB)\)
such that \(F({{\,\mathrm{\mathrm {id}}\,}}_A) = {{\,\mathrm{\mathrm {id}}\,}}_{FA}\) and \(Fg \circ Ff = F(g \circ f)\) for \(A\) an object of \({\mathcal {C}}\) and \(f :A \rightarrow B\) and \(g :B \rightarrow C\) morphisms of \({\mathcal {C}}\).
Definition 12
Given two functors \(F,G :{\mathcal {C}}\rightarrow {\mathcal {D}}\) of \(2\)categories, a transformation\(\alpha :F \rightarrow G\) consists of

1.
A morphism \(\alpha _A :FA \rightarrow GA\) in \({\mathcal {D}}\) for every \(A \in {{\,\mathrm{\mathrm {ob}}\,}}{\mathcal {C}}\)

2.
A \(2\)cell \(\alpha _f :Gf \circ \alpha _A \rightarrow \alpha _B \circ Ff\) for every morphism \(f :A \rightarrow B\) in \({\mathcal {C}}\).
This structure is subject to the axioms given by commutativity of the following two diagrams:
Definition 13
Given two functors \(F,G :{\mathcal {C}}\rightarrow {\mathcal {D}}\) of \(2\)categories, and transformations \(\alpha , \beta :F \rightarrow G\), a modification\(M :\alpha \rightarrow \beta \) consists of a \(2\)cell
for every object \(A\) of \({\mathcal {C}}\) such that for every morphism \(f :A \rightarrow B\) of \({\mathcal {C}}\) the following diagram commutes:
Definition 14
Given \(2\)categories \({\mathcal {C}}\) and \({\mathcal {D}}\), the functor\(2\)category\([{\mathcal {C}}, {\mathcal {D}}]\) is the \(2\)category with functors \(F :{\mathcal {C}}\rightarrow {\mathcal {D}}\) as objects, transformations of such functors as morphisms and with \(2\)cells given by modifications.
Given a category \({\mathcal {C}}\) we will consider it as a \(2\)category with only identity \(2\)cells. Thus, if \({\mathcal {C}}\) is a category and \({\mathcal {D}}\) is a \(2\)category we have defined the functor \(2\)categories \([{\mathcal {C}},{\mathcal {D}}]\) and \([{\mathcal {D}},{\mathcal {C}}]\).
Definition 15
The opposite of a \(2\)category \({\mathcal {C}}\) is the \(2\)category \({\mathcal {C}}^{\mathrm {op}}\) with the same objects as \({\mathcal {C}}\), with
and with composition obtained from composition in \({\mathcal {C}}\).
Relations
Dowker dissimilarities can be considered as filtered relations. In order to formulate this precisely, we need some background information on relations.
Definition 16
Let \(X\) and \(Y\) be sets. A relation\(R :X \leftrightarrows Y\) is a subset \(R \subseteq X \times Y\).
Definition 17
We define a partial order on the set of relations between \(X\) and \(Y\) by set inclusion. That is, for relations \(R :X \leftrightarrows Y\) and \(R' :X \leftrightarrows Y\), we have \(R \le R'\) if and only if \(R\) is contained in the subset \(R'\) of \(X \times Y\).
Definition 18
Given two relations \(R :X \leftrightarrows Y\) and \(S :Y \leftrightarrows Z\), their composition
is
Definition 19
The \(2\)category \({\mathcal {S}}\) of sets and relations has as objects the class of sets and as morphisms the class of relations. The \(2\)cells are given by the inclusion partial order on the class of relations. Composition of morphisms is composition of relations and composition of \(2\)cells is given by composition of inclusions. The identity morphism on the set \(X\) is the diagonal
The identity \(2\)cell on a relation \(R\) is the identity inclusion \(R \le R\).
Definition 20
The transposition functor \(T :{\mathcal {S}}\rightarrow {\mathcal {S}}^{\mathrm {op}}\) is defined by \(T(X) = X\),
and \(T(i) = i^T\), where \(i^T :R^T \rightarrow S^T\) takes \((y,x)\) to \((z,w)\) when \((w,z) = i(x,y)\).
Definition 21
A correspondence\(C :X \leftrightarrows Y\) is a relation such that:

1.
For every \(x \in X\) there exists \(y \in Y\) so that \((x,y) \in C\) and

2.
For every \(y \in Y\) there exists \(x \in X\) so that \((x,y) \in C\).
Lemma 3
A relation \(C :X \leftrightarrows Y\) is a correspondence if and only if there exists a relation \(D :Y \leftrightarrows X\) so that \(\varDelta _X \le D \circ C\) and \(\varDelta _Y \le C \circ D\).
Proof
By definition of a correspondence, for every \(x \in X\), there exists \(y \in Y\) so that \((x,y) \in C\). This means that \(\varDelta _X \subseteq C^T \circ C\), where
Reversing the roles of \(C\) and \(C^T\) we get the inclusion \(\varDelta _Y \subseteq C \circ C^T\). Conversely, if \(C\) and \(D\) are relations with \(\varDelta _Y \subseteq C \circ D\), then for every \(y \in Y\), the element \((y,y)\) is contained in \(C \circ D\). This means that there exists \(x \in X\) so that \((x,y) \in C\), and \((y,x) \in D\). In particular for every \(y \in Y\), there exists \(x \in X\) so that \((x,y) \in C\). Reversing the roles of \(C\) and \(D\) we get that for every \(x \in X\) there exists \(y \in Y\) so that \((x,y) \in C\). \(\square \)
The category of relations
In this section, we introduce a novel \(2\)category of relations. We start by recalling Dowker’s definition of the nerve of a relation (called the complex \(K\) in Dowker 1952, Sect. 1).
Definition 22
Let \(R \subseteq X \times Y\) be a relation. The nerve of \(R\) is the simplicial complex
Example 2
Let \(X\) be a space, and let \(Y\) be a cover of \(X\). In particular every element \(y \in Y\) is a subset of \(X\). Let \(R\) be the relation \(R \subseteq X \times Y\) consisting of pairs \((x,y)\) with \(x \in y\). A direct inspection reveals that the nerve of \(R\) is equal to the Borsuk Nerve of the cover \(Y\).
Definition 23
The \(2\)category \({\mathcal {R}}\) of relations has as objects the class of relations. A morphism \(C :R \rightarrow R'\) in \({\mathcal {R}}\) between relations \(R \subseteq X \times Y\) and \(R' \subseteq X' \times Y'\) consists of a relation \(C \subseteq X \times X'\) such that for every \(\sigma \in NR\), the set
is an element \((NC) (\sigma ) \in NR'\) of the nerve of \(R'\). In particular, \((NC) (\sigma )\) is finite and nonempty. The class of \(2\)cells in \({\mathcal {R}}\) is the class of inclusions \(C_1 \subseteq C_2\) for morphisms \(C_1, C_2 \subseteq X \times X'\). Composition in \({\mathcal {R}}\) is given by composition of relations.
Note that if \(C :R \rightarrow R'\) is a morphism in \({\mathcal {R}}\), then \(NC\) is an order preserving function \(NC :NR \rightarrow NR'\), and thus it induces a simplicial map \(NC :\varDelta (NR) \rightarrow \varDelta (NR')\) of order complexes. Given a simplicial complex \(K\), the simplicial complex \(\varDelta (K)\) is the barycentric subdivision of \(K\). The geometric realizations of \(K\) and \(\varDelta (K)\) are homeomorphic. In particular, they represent isomorphic objects in the homotopy category of simplicial complexes.
Lemma 4
Let \(C_0, C_1 :R \rightarrow R'\) be morphisms in \({\mathcal {R}}\). If there exists a \(2\)cell \(\alpha :C_0 \rightarrow C_1\), then the geometric realizations of the simplicial maps
are homotopic.
Proof
Let \(I\) be the partially ordered set
Since \(C_0 \subseteq C_1\), we can define an order preserving map
by
On order complexes \(C\) induces a simplicial map
As a consequence of Milnor (1981), Theorem 1 and Milnor (1981), Theorem 2 the geometric realization of \(\varDelta (I \times NR)\) is homeomorphic to the product of the geometric realizations of \(\varDelta (I)\) and \(\varDelta (NR)\). The geometric realization of \(\varDelta (I)\) is homeomorphic to the closed unit interval. Thus we have constructed a homotopy between the geoemtric realizations of \(NC_1\) and \(NC_2\). \(\square \)
Definition 24
The nerve functor\(N :{\mathcal {R}}\rightarrow \mathrm {hCx}\) is the functor taking a relation \(R\) the order complex \(\varDelta (NR)\) of its nerve and taking a morphism \(C :R \rightarrow R'\) in \({\mathcal {R}}\) to the morphism \(NC :\varDelta (NR) \rightarrow \varDelta (NR')\) in \(\mathrm {hCx}\).
Let us emphasize that if \(\alpha :C_1 \rightarrow C_2\) is a \(2\)cell in \({\mathcal {R}}\), then \(NC_1 = NC_2\) in \(\mathrm {hCx}\).
Interleavings
In this section, we set the concept of interleaving into the context of \(2\)categories. This material is wellknown in the applied topology community.
We write \([0,\infty )\) for the set of nonnegative real numbers and consider it as a partially ordered set. We also consider \([0,\infty )\) as a category with object set \([0,\infty )\) and with a unique morphism \(s \rightarrow t\) if and only if \(s \le t\).
Definition 25
Let \({\mathcal {C}}\) be a \(2\)category. The category of filtered objects in \({\mathcal {C}}\) is the functor \(2\)category \([[0,\infty ), {\mathcal {C}}]\). A filtered object in \({\mathcal {C}}\) is an object \(C :[0,\infty )\rightarrow {\mathcal {C}}\) of \([[0,\infty ), {\mathcal {C}}]\), that is, \(C\) is a functor from \([0,\infty )\) to \({\mathcal {C}}\). A morphism\(f :C \rightarrow C'\) of filtered objects in \({\mathcal {C}}\) is a transformation.
We will be so interested in the category of filtered objects in the \(2\)category of relations that we give a name to this particular \(2\)category.
Definition 26
A filtered relation is a functor from \([0,\infty )\) to \({\mathcal {R}}\). We define the \(2\)category of filtered relations to be the \(2\)category \([[0,\infty ), {\mathcal {R}}]\) of functors from \([0,\infty )\) to \({\mathcal {R}}\).
Definition 27
Let \({\mathcal {C}}\) be a \(2\)category and let \(\alpha :[0,\infty )\rightarrow [0,\infty )\) be a translation function, that is, an order preserving function satisfying \(t \le \alpha (t)\) for all \(t \in [0,\infty )\).

1.
The pullback functor \(\alpha ^* :[[0,\infty ),{\mathcal {C}}] \rightarrow [[0,\infty ),{\mathcal {C}}]\) is the functor taking a filtered object \(C :[0,\infty )\rightarrow {\mathcal {C}}\) in \({\mathcal {C}}\) to the filtered object \(\alpha ^* C = C \circ \alpha \).

2.
The unit of the functor\(\alpha ^* :[[0,\infty ),{\mathcal {C}}] \rightarrow [[0,\infty ),{\mathcal {C}}]\) is the natural transformation \(\alpha _* :{{\,\mathrm{\mathrm {id}}\,}}\rightarrow \alpha ^*\) defined by
$$\begin{aligned} \alpha _{*C}(t) = C(t \le \alpha (t)) :C(t) \rightarrow \alpha ^*(C)(t) . \end{aligned}$$
Definition 28
Let \(C\) and \(C'\) be filtered objects in a \(2\)category \({\mathcal {C}}\) and let \(\alpha , \alpha ' :[0,\infty )\rightarrow [0,\infty )\) be functors under the identity.

1.
An \((\alpha ,\alpha ')\)interleaving between \(C\) and \(C'\) is a pair \((F,F')\) of morphisms \(F :C \rightarrow \alpha ^*C'\) and \(F' :C' \rightarrow \alpha '^* C\) in \([[0,\infty ),{\mathcal {C}}]\) such that there exist \(2\)cells
$$\begin{aligned} (\alpha ' \circ \alpha )_* \rightarrow (\alpha ^* F') \circ F \quad \text {and} \quad (\alpha \circ \alpha ')_* \rightarrow (\alpha '^* F) \circ F'. \end{aligned}$$ 
2.
We say that \(C\) and \(C'\) are \((\alpha ,\alpha ')\)interleaved if there exists an \((\alpha ,\alpha ')\)interleaving between \(C\) and \(C'\).
The following results appear in Bubenik et al. (2015), Propositions 2.2.11 and 2.2.13.
Lemma 5
(Functoriality) Let \(C\) and \(C'\) be filtered objects in a \(2\)category \({\mathcal {C}}\), let \(\alpha , \alpha ' :[0,\infty )\rightarrow [0,\infty )\) be functors under the identity and let \(H :{\mathcal {C}}\rightarrow {\mathcal {D}}\) be a functor of \(2\)categories. If \(C\) and \(C'\) are \((\alpha ,\alpha ')\)interleaved, then the filtered objects \(H C\) and \(H C'\) in \({\mathcal {D}}\) are \((\alpha ,\alpha ')\)interleaved.
Lemma 6
(Triangle inequality) Let \(C\), \(C'\) and \(C''\) be filtered objects in a \(2\)category \({\mathcal {C}}\). If \(C\) and \(C'\) are \((\alpha ,\alpha ')\)interleaved and \(C'\) and \(C''\) are \((\beta ,\beta ')\)interleaved, then \(C\) and \(C''\) are \((\beta \alpha , \alpha ' \beta ')\)interleaved.
Filtered relations and Dowker dissimilarities
In this section, we introduce a novel \(2\)category of Dowker dissimilarities as a certain sub\(2\)category of the category of filtered relations.
Definition 29
The filtered nerve functor is the functor
from the \(2\)category of filtered relations to the category of homotopy filtered spaces taking \(X :[0,\infty )\rightarrow {\mathcal {R}}\) to the composition
From Lemma 5 we get:
Corollary 3
If \(R\) and \(R'\) are \((\alpha ,\alpha ')\)interleaved filtered relations, then \(NR\) and \(NR'\) are \((\alpha ,\alpha ')\)interleaved filtered simplicial complexes.
Given a Dowker dissimilarity \(\varLambda :L \times W \rightarrow [0,\infty ]\) and \(t \in [0,\infty )\) we consider
as an object of the category \({\mathcal {R}}\) of relations. Given \(s \le t\) in \([0,\infty )\) we let
considered as a morphism \(\varLambda _{s \le t} :\varLambda _s \rightarrow \varLambda _t\) in \({\mathcal {R}}\).
Definition 30
The filtered relation associated to a Dowker dissimilarity \(\varLambda :L \times W \rightarrow [0,\infty ]\) is the functor
taking \(t \in [0,\infty )\) to the relation \(\varLambda _t\) and taking \(s \le t\) in \([0,\infty )\) to the morphism \(\varLambda _{s \le t}\) in \({\mathcal {R}}\).
Definition 31
Let \(\varLambda :L \times W \rightarrow [0,\infty ]\) and \(\varLambda ' :L' \times W' \rightarrow [0,\infty ]\) be Dowker dissimilarities. A morphism \(C :\varLambda \rightarrow \varLambda '\) of filtered relations is a morphism of Dowker dissimilarities if there exists a relation \(C \subseteq L \times L'\) so that \(C_t = C :\varLambda _t \rightarrow \varLambda '_t\) for every \(t \in [0,\infty )\).
Definition 32
The \(2\)category\(\mathrm {Dow}\)of Dowker dissimilarities is the \(2\)category with Dowker dissimilarities as objects and morphisms of Dowker dissimilarities as morphisms. Given morphisms \(C_1, C_2 :\varLambda \rightarrow \varLambda '\) of Dowker dissimilarities, we define the set of \(2\)cells \(\alpha :C_1 \rightarrow C_2\) in \(\mathrm {Dow}\) by letting \(\mathrm {Dow}(C_1,C_2) = [[0,\infty ), {\mathcal {R}}](C_1,C_2)\).
Definition 33
Let \(\varLambda :L \times W \rightarrow [0,\infty ]\) be a Dowker dissimilarity. The Dowker Nerve\(N \varLambda \) of \(\varLambda \) is the filtered nerve of the underlying filtered relation.
Note that the Dowker Nerve is filtered by inclusion of subcomplexes, that is, if \(s \le t\), then \(N\varLambda _{s \le t} :N\varLambda _s \rightarrow N\varLambda _t\) is an inclusion of simplicial complexes.
Definition 34
Let \(\varLambda :L \times W \rightarrow [0,\infty ]\) be a Dowker dissimilarity. Given \(l \in L\) and \(t > 0\), the \(\varLambda \)ball of radius\(t\)centred at\(l\) is
Example 3
Let \((M, d)\) be a metric space and \(L\) and \(W\) be subsets of \(M\). Then the restriction \(\varLambda :L \times W \rightarrow [0,\infty ]\) of \(d\) to \(L \times W\) is a Dowker dissimilarity. The Dowker Nerve of \(\varLambda \) is the composite
taking \(t \in [0,\infty )\) to
If \(L = W = M\), then the \(\varLambda \)ball of radius \(t\) centred at \(l\) is the usual open ball in \(M\) of radius \(t\) centred at \(l\) and the Dowker Nerve of \(\varLambda \) is equal to the Čech complex \(\check{{\mathcal {C}}}(M)\).
Lemma 7
Let \(\varLambda :L \times W \rightarrow [0,\infty ]\) be a Dowker dissimilarity. Given \(t > 0\), the nerve \(N\varLambda _t\) is isomorphic to the Borsuk Nerve of the cover of the set
by balls \(B_{\varLambda }(l,s)\) of radius \(s \le t\) centred at points in \(L\).
It is wellknown that, in the above situation, the geometric realization of \(N\varLambda _t\) is homotopic to the geometric realization of the Borsuk Nerve of the cover of the set
by balls \(B_{\varLambda }(l,t)\) of radius \(t\) centred at points in \(L\). See e.g. Blaser and Brun (2018), Lemma 2.3. Corollary 3 gives:
Corollary 4
If \(\varLambda :L \times W \rightarrow [0,\infty ]\) and \(\varLambda ' :L' \times W' \rightarrow [0,\infty ]\) are \((\alpha ,\alpha ')\)interleaved Dowker dissimilarities, then \(N\varLambda \) and \(N\varLambda '\) are \((\alpha ,\alpha ')\)interleaved filtered simplicial complexes.
Definition 35
Let \(\varLambda :L \times W \rightarrow [0,\infty ]\) be a Dowker dissimilarity. The Rips complex of \(\varLambda \) is the filtered simplicial complex \(R\varLambda \) defined by
Corollary 5
If \(\varLambda :L \times W \rightarrow [0,\infty ]\) and \(\varLambda ' :L' \times W' \rightarrow [0,\infty ]\) are \((\alpha ,\alpha ')\)interleaved Dowker dissimilarities, then \(R\varLambda \) and \(R\varLambda '\) are \((\alpha ,\alpha ')\)interleaved filtered simplicial complexes.
Proof
Use Corollary 4 and the fact that the Rips complex depends functorially on the one skeleton of the Dowker Nerve. \(\square \)
Stability and interleaving distance
The functoriality of interleaving implies that all functorial constructions are stable with respect to interleaving. In this section we relate interleaving distance of Dowker dissimilarities to Gromov–Hausdorff distance of Edwards (1975), Gromov (1981) and to the network distance defined in Chowdhury and Mémoli (2018).
Definition 36
Let \(C\) and \(C'\) be filtered objects in a \(2\)category \({\mathcal {C}}\).

1.
Given \(a,a' \in [0,\infty ]\) we say that the filtered objects \(C\) and \(C'\) are additively\((a,a')\)interleaved if they are \((\alpha ,\alpha ')\)interleaved for the functions \(\alpha (t) = a + t\) and \(\alpha '(t) = a' + t\).

2.
The interleaving distance of \(C\) and \(C'\) is
$$\begin{aligned} {{\,\mathrm{d_{\mathrm {int}}}\,}}(C,C') = \inf \{a \in [0,\infty ]\, \mid \,&C\text { and }C'\text { are additively} \\&(a,a)\text {interleaved}\}, \end{aligned}$$with the convention that \(\inf \emptyset = \infty \).
Definition 37
A nonnegatively weighted network is a pair \((X, \omega _X)\) of a set \(X\) and a weight function \(\omega _X :X \times X \rightarrow [0,\infty )\).
Definition 38
Let \(\omega _X :X \times X \rightarrow [0,\infty )\) and \(\omega _{X'} :X' \times X' \rightarrow [0,\infty )\) be nonnegatively weighted networks and let \(C \subseteq X \times X'\). The distortion of\(C\) is
Recall from Definition 21 that \(C \subseteq X \times X'\) is a correspondence if the projections of \(C\) on both \(X\) and \(X'\) are surjective.
Definition 39
Let \(\omega _X :X \times X \rightarrow [0,\infty )\) and \(\omega _{X'} :X' \times X' \rightarrow [0,\infty )\) be nonnegatively weighted networks and let \({\mathcal {R}}\) be the set of correspondences \(C \subseteq X \times X'\). The network distance between \(X\) and \(X'\) is
The Stability Theorem (Chowdhury and Mémoli 2018, Proposition 15) for networks is a consequence of functoriality of interleaving distance, the Algebraic Stability Theorem for bottleneck distance (Chazal et al. 2009, Theorem 4.4) and the following result:
Proposition 4
Let \(\omega _X :X \times X \rightarrow [0,\infty )\) and \(\omega _{X'} :X' \times X' \rightarrow [0,\infty )\) be networks, and write
for the corresponding Dowker dissimilarities with \(\varLambda (x,y) = {\omega _X(x,y)}\) and \(\varLambda '(x',y') = {\omega _{X'}(x',y')}\). Then
Proof
We have to show that \({{\,\mathrm{d_{\mathrm {int}}}\,}}(\varLambda , \varLambda ') \le {{\,\mathrm{\mathrm {dis}}\,}}(C)\) for every correspondence \(C \subseteq X \times X'\). So let \(C \subseteq X \times X'\) be a correspondence and let \(a > {{\,\mathrm{\mathrm {dis}}\,}}(C)\). By definition of \({{\,\mathrm{\mathrm {dis}}\,}}(C)\), for all \((l,l')\) and \((w, w')\) in \(C\) we have
Defining \(\alpha :[0,\infty )\rightarrow [0,\infty )\) by \(\alpha (t) = t + a\), by symmetry, it suffices to show that \(C\) defines a morphism
That is, we have to show that if \(\sigma \in \varLambda _t\), then \((NC)(\sigma ) \in \varLambda '_{\alpha (t)}\). So suppose that \(w \in X\) satisfies \(\varLambda (l,w) < t\) for all \(l \in \sigma \). Since \(C\) is a correspondence we can pick \(w' \in X'\) so that \((w,w') \in C\). By definition of \(NC\), for every \(l' \in (NC)(\sigma )\), there exists \(l \in \sigma \) so that \((l,l') \in C\). By definition of distortion distance this gives
We conclude that \(\sigma \in N\varLambda _t\) implies \((NC)(\sigma ) \in N\varLambda '_{\alpha (t)}\) as desired. \(\square \)
The Stability Theorem (Chazal et al. 2014, Theorem 5.2) for metric spaces is a consequence of functoriality of interleaving distance, the Algebraic Stability Theorem for bottleneck distance (Chazal et al. 2009, Theorem 4.4) and the following result:
Corollary 6
Let \((M,d)\) and \((M',d')\) be metric spaces, and write
for the corresponding Dowker dissimilarities with \(\varLambda (p,q) {=} d(p,q)\) and \(\varLambda '(p',q') = d'(p',q')\). Then
Proof
By Burago et al. (2001), Theorem 7.3.25 the Gromov–Hausdorff distance of the metric spaces \((M,d)\) and \((M',d')\) agrees with their network distance when we consider them as nonnegatively weighted networks. That is, \(d_{GH}(M,M') = {{\,\mathrm{d_{{\mathcal {N}}}}\,}}(M,M')\). The result now follows from Proposition 4. \(\square \)
Conclusion
We generalize the Sparse Čech construction of Cavanna et al. (2015) to arbitrary metric spaces and to a large class of Dowker dissimilarities. The abstract context of Dowker dissimilarities is wellsuited for sparse nerve constructions. The concepts of filtered relations and strict \(2\)categories enable us to easily formulate and prove basic stability results. An implementation of the Sparse Dowker Nerve most similar to the Sparse Čech complex is available at GitHub Brun and Blaser (2018) together with a user tutorial. This implementation is not practical for analysis of high dimensional data.
Other recent work on sparse complexes has focused on Euclidean space (Choudhary et al. 2018) or the use of general simplicial maps (Dey et al. 2016; Boissonnat et al. 2018). It is possible that these considerations can be combined to obtain even smaller filtered nerves. In further work, we will improve this construction and we will make Sparse Dowker Nerves for Dowker dissimilarities that do not satisfy the triangle inequality.
References
Blumberg, A.J., Lesnick, M.: Universality of the homotopy interleaving distance (2017). https://arxiv.org/abs/1705.01690
Boissonnat, J.D., Pritam, S., Pareek, D. Strong Collapse for Persistence (2018). ArXiv eprints. arXiv:1809.10945
Blaser, N., Brun, M.: Divisive cover. Math. Comput. Sci. (2018). https://doi.org/10.1007/s1178601803526
Brun, M., Blaser, N.: SparseDowkernerves (2018). https://github.com/mbr085/SparseDowkerNerves
Bubenik, P., de Silva, V., Scott, J.: Metrics for generalized persistence modules. Found. Comput. Math. 15(6), 1501–1531 (2015)
Buchet, M., Chazal, F., Oudot, S.Y., Sheehy, D.: Efficient and robust persistent homology for measures. Comput. Geom.: Theory Appl. 58, 70–96 (2016)
Burago, D., Burago, Y., Ivanov, S.: A Course in Metric Geometry. Graduate Studies in Mathematics, vol. 33. American Mathematical Society, Providence (2001)
Carlsson, G., Ishkhanov, T., de Silva, V., Zomorodian, A.: On the local behavior of spaces of natural images. Int. J. Comput. Vis. 76(1), 1–12 (2008)
Cavanna, N.J., Jahanseir, M., Sheehy, D.R.: A geometric perspective on sparse filtrations. CoRR, arXiv:1506.03797 (2015)
Chazal, F., CohenSteiner, D., Glisse, M., Guibas, L., Oudot, S.: Proximity of persistence modules and their diagrams. In: SoCG, pp. 7–246 (2009)
Chazal, F., CohenSteiner, D., Guibas, L.J., Mémoli, F., Oudot, S.Y.: Gromov–hausdorff stable signatures for shapes using persistence. In: Proceedings of the Symposium on Geometry Processing, SGP ’09, pp, 1393–1403. Eurographics Association, AirelaVille (2009)
Chazal, F., de Silva, V., Oudot, S.: Persistence stability for geometric complexes. Geom. Dedicata 173, 193–214 (2014)
Choudhary, A., Kerber, M., Raghvendra, S.: Improved topological approximations by digitization. CoRR, arXiv:1812.04966 (2018)
Chowdhury, S., Mémoli, F.: A functorial Dowker theorem and persistent homology of asymmetric networks (2018). ArXiv eprints. arXiv:1608.05432
Dey, T.K., Shi, D., Wang, Y.: SimBa: an efficient tool for approximating Ripsfiltration persistence via simplicial batchcollapse. In: 24th Annual European Symposium on Algorithms, vol. 57 of LIPIcs. Leibniz Int. Proc. Inform, Art. No. 35, 16 (2016)
Dowker, C.H.: Homology groups of relations. Ann. Math. 2(56), 84–95 (1952)
Edwards, D.A.: The structure of superspace. In: Studies in Topology. Proceeding Conference, University of North Carolina, Charlotte, N. C., 1974; dedicated to Mathematics Section Polish Academy of Sciences, pp. 121–133. Academic Press, New York (1975)
Embrechts, P., Hofert, M.: A note on generalized inverses. Math. Methods Oper. Res. 77(3), 423–432 (2013)
Gromov, M.: Groups of polynomial growth and expanding maps. Inst. Hautes Études Sci. Publ. Math. 53, 53–73 (1981)
Lawvere, F.W.: Metric spaces, generalized logic, and closed categories. Ann. Math. (2) 65, 357–362 (1957)
Leinster, T.: Basic bicategories (1998)
Milnor, J.: The geometric realization of a semisimplicial complex. Inst. Hautes Études Sci. Publ. Math. 53, 53–73 (1981)
Oudot, S.Y.: Persistence Theory: From Quiver Representations to Data Analysis. Mathematical Surveys and Monographs, vol. 209. American Mathematical Society, Providence (2015)
Sheehy, D.R.: Linearsize approximations to the Vietoris–Rips filtration. Discrete Comput. Geom. 49(4), 778–796 (2013)
Spanier, E.H.: Algebraic Topology. Springer, New York (1966). Corrected reprint of the 1966 original
Zomorodian, A.: Topological data analysis. In Advances in Applied and Computational Topology. Proceedings of Symposia in Applied Mathematics, vol. 70, pp. 1–39. American Mathematical Society, Providence (2012)
Acknowledgements
This research was supported by the Research Council of Norway through Grant 248840. The authors have no conflicts of interest. We would like to thank the referees for helpful comments improving this paper.
Author information
Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Brun, M., Blaser, N. Sparse Dowker nerves. J Appl. and Comput. Topology 3, 1–28 (2019). https://doi.org/10.1007/s41468019000289
Received:
Accepted:
Published:
Issue Date:
Keywords
 Sparse nerve
 Dowker theorem
 Persistent homology
 Čech complex
 Rips complex
Mathematics Subject Classification
 55N05
 55N99
 55U10
 55U99