1 Introduction↩︎

Čech complexes are among the most important tools in applied topology for approximating the shape of data. Indeed, whereas a finite dataset has no interesting topology on its own, if one replaces each point in the dataset with a ball of radius \(r\), then the union of the balls serves as a proxy for the shape of the data. Even better, by letting the radius \(r\) vary from small to large, one can use persistent homology to get a multi-resolution summary of the shape of the data [1]. Though the union of balls is difficult to store on a computer, the Čech complex is a combinatorial representation with a vertex for each data point, an edge whenever two balls intersect, a triangle whenever three balls intersect, etc. Since balls in Euclidean space are convex, the nerve lemma implies that this Čech complex is homotopy equivalent to the union of the balls (see [2] or [3]).

The theory of Čech complexes for balls in Euclidean space is well-understood. But what about for balls in other manifolds? In a Riemannian manifold \(M\), a ball of radius \(r\) need only be geodesically convex up to a certain scale \(r\) (called the convexity radius) depending on the curvature of the manifold. For larger scales, the intersection of two balls may be disconnected, meaning that the hypotheses of the nerve lemma may no longer be satisfied. What are the homotopy types of intrinsic Čech complexes of manifolds, where intrinsic means that the Čech complex is the nerve of balls restricted to live in the manifold? In this paper, we initiate the study of this question for the simplest non-contractible manifolds: spheres. We hope our paper inspires follow-up work on the intrinsic Čech complexes of other manifolds. Furthermore, instead of the statistical context of a finite dataset \(X\) sampled from the \(n\)-sphere \(S^n\), we begin with the mathematical context of the Čech complex of the entire \(n\)-sphere. If one’s dataset \(X\) is sampled from a manifold \(M\), then in the limit, as more data points are sampled, the stability of persistent homology [4] implies that the intrinsic Čech persistent homology of the dataset \(X\) converges to the intrinsic Čech persistent homology of the entire manifold \(M\).

What are the homotopy types of intrinsic Čech complexes of spheres? Equip the \(n\)-sphere \(S^n\) with the geodesic metric of diameter \(\pi\). If the scale \(r\) satisfies \(0<r\le\frac{\pi}{2}\), then the open balls \(\{B_{S^n}(x;r)\}_{x\in S^n}\) form a good cover of the sphere \(S^n\), meaning that any intersection of balls is either empty or contractible. Since \(S^n\) is paracompact as it is a metric space, the nerve lemma implies that the intrinsic Čech complex \(\mathrm{\check{C}}(S^n;r)\mathrel{\vcenter{:}}= \mathrm{Nerve}(\{B_{S^n}(x;r)\}_{x\in S^n})\) is homotopy equivalent to \(S^n\) ([3]; see also [5]). But what are the homotopy types of \(\mathrm{\check{C}}(S^n;r)\) when \(\frac{\pi}{2}<r<\pi\)?

The case \(n=1\) is well-understood by [6]: as the scale \(r\) increases, the complexes \(\mathrm{\check{C}}(S^1;r)\) obtain the homotopy types of \(S^1\), \(S^3\), \(S^5\), \(S^7\), …. We also refer the reader to [7] for a description of the homotopy type of \(\mathrm{\check{C}}(X;r)\) for \(X\) an arbitrary finite subset of \(S^1\), and to [8] for a description of the expected Euler characteristic of \(\mathrm{\check{C}}(X;r)\) for \(X\) a finite subset chosen uniformly at random from \(S^1\). However, for \(n\ge 2\), essentially nothing is known about the homotopy types of \(\mathrm{\check{C}}(S^n;r)\) for \(\frac{\pi}{2}<r<\pi\), except that they are simply connected by [9]. In particular, though the first new homotopy type beyond \(S^n\) (i.e., the homotopy type of \(\mathrm{\check{C}}(S^n;\frac{\pi}{2}+\varepsilon)\) for \(\varepsilon>0\) sufficiently small) seems within reach, to our knowledge no conjecture for this homotopy type has appeared in the literature. Can we bound the homotopy connectivity of \(\mathrm{\check{C}}(S^n;r)\) as a function of the scale \(r\)?

We denote the homotopy connectivity of a topological space \(X\) by \(\mathop{\mathrm{conn}}(X)\), so \(\pi_i(X)\) vanishes for all \(i\le \mathop{\mathrm{conn}}(X)\). For a metric space \((X,d)\), the \(k\)-th covering radius, denoted \(\mathop{\mathrm{cov}}_X(k)\), is the infimum \(r\ge 0\) such that there exist \(k\) closed balls of radius \(r\) that cover \(X\). We show in Proposition 3, using Barmak’s Appendix [10], that if \(0<\delta<\mathop{\mathrm{cov}}_{S^n}(2k+2)\), then \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^n;\pi-\delta)) \ge k\). Next, using Lovász’s classical bound on the chromatic number of a graph in terms of the connectivity of its neighborhood complex [11], we upper bound the connectivity of Čech complexes of spheres. The (open) Borsuk graph on \(S^n\) at scale \(\delta>0\), denoted \(\mathrm{Bor}(S^n;\delta)\), is the infinite graph with vertex set \(S^n\) whose edges are the pairs of vertices \(v,w\) which are more than \(\delta\) apart in the geodesic distance, i.e., \(d(v,w)>\delta\). The neighborhood complex of the Borsuk graph \(\mathrm{Bor}(S^n;\delta)\) is the Čech complex \(\mathrm{\check{C}}(S^n;\pi-\delta)\). As a result, in Proposition 6, we show that if \(\delta> 2\mathop{\mathrm{cov}}_{S^n}(k+1)\), then we have that \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^n;\pi-\delta))\leq k-2\).

When combined together, we get strong bounds on the connectivity of Čech complexes of spheres.

See Figure 1 for an illustration of this theorem in the case \(n=2\).

For a metric space \((X,d)\), the \(r\)-covering number, denoted \(\mathop{\mathrm{numCover}}_X(r)\), is the smallest integer \(n\) such that \(X\) can be covered by \(n\) closed balls of radius \(r>0\). Rearranging the inequalities in Theorem 1 gives the following corollary.

From [13], we know that the connectivity of Vietoris–Rips complexes of sphere satisfies \[\tfrac{1}{2}\mathop{\mathrm{numCover}}_{S^n}(\delta) - 2 \le \mathop{\mathrm{conn}}(\mathrm{VR}(S^n;\pi-\delta)) \le \mathop{\mathrm{numCover}}_{{\mathbb{R}}\mathrm{P}^n}\left(\tfrac{\delta}{2}\right)-2\] for each \(n\ge 1\) and \(\delta>0\). So, while the current best bounds on \(\mathop{\mathrm{conn}}(\mathrm{VR}(S^n;r))\) depend on the covering numbers of both \({\mathbb{R}}\mathrm{P}^n\) and \(S^n\), the current best bounds on \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^n;r))\) depend only on the covering numbers of \(S^n\).

It follows as a consequence that the homotopy type of \(\mathrm{\check{C}}(S^n;r)\) changes infinitely many times.

We conjecture that the homotopy type of \(\mathrm{\check{C}}(S^n;r)\) changes only countably many times as \(r\) varies; see Conjecture 13.

How good are our bounds on \(\mathrm{\check{C}}(S^n;\pi-\delta)\)? We are able to test this in the case of \(n=1\). From [6], we know that \(\mathrm{\check{C}}(S^1;r)\) obtains the homotopy types \(S^1, S^3, S^5, S^7, \ldots\) as \(r\) increases. Thus, we compare the scales obtained in Theorem 1 with the actual scales of those connectivities, and it turns out that for \(n=1\), the lower bound on \(\delta\) in the theorem is off by approximately a multiplicative factor of \(4\), whereas the upper bound on \(\delta\) is tight. See Figure 2.

We also study the homological dimension of Čech complexes of (finite subsets) of spheres. The \({\mathbb{Z}}\)-homological dimension of a topological space \(Y\), denoted \(\mathop{\mathrm{h-dim}}_{{\mathbb{Z}}}(Y)\), is the largest integer \(i\) such that \(\widetilde{H}_i(Y; {\mathbb{Z}}) \neq 0\). We give a lower bound on the \({\mathbb{Z}}\)-homological dimension of \(\mathrm{\check{C}}(X;\pi -\delta)\) for all finite subsets \(X\subseteq S^n\) in terms of the packings of \(X\), and we ask if these lower bounds extend to \(\mathrm{\check{C}}(S^n;\pi -\delta)\).

The paper is organized as follows. In Section 2, we survey some related work on Čech complexes of spheres, and in Section 3, we introduce the definitions and notations that we will use in this paper. We give a lower bound on the homotopy connectivity of Čech complexes of spheres using Barmak’s work relating homotopy connectivity to simplicial conicity in Section 4. We upper bound the homotopy connectivity of Čech complexes of spheres using Lovász’s seminal result relating the chromatic number of a graph to the connectivity of its neighborhood complex in Section 5. In Section 6, we describe what our bounds on connectivity give in the case of the circle. In Section 7, we bound the homological dimension of Čech complexes of finite subsets of spheres from below using the theory of box complexes, and we study the problem of extending our lower bounds to Čech complexes of the entire spheres. We conclude this paper in Section 8 with a list of open questions and conjectures.

2 Related work↩︎

In [11], Lovász famously used topological arguments, and in particular, the Borsuk–Ulam theorem, to lower bound the chromatic numbers of Kneser graphs. Though Kneser graphs are finite graphs of a combinatorial flavor, Lovász’s techniques for understanding their chromatic numbers were partially inspired by the infinite and geometrically flavored Borsuk graphs (see [11]), which have \(n\)-spheres as their vertex sets. Lovász proved that the chromatic number of any graph \(G\) satisfies \(\chi(G)\ge\mathop{\mathrm{conn}}(N(G))+3\), where \(N(G)\) is the neighborhood simplicial complex of \(G\). He further showed that this general lower bound turns out to be an equality in the case of Kneser graphs.

The neighborhood complexes of Borsuk graphs are easily identified to be Čech complexes of spheres. Indeed, the Borsuk graph \(\mathrm{Bor}(S^n;\delta)\) has \(S^n\) as its vertex set and an edge between any two vertices at a distance more than \(\delta\). Its neighborhood complex turns out to be the nerve simplicial complex of all open balls in \(S^n\) of radius \(\pi-\delta\), recovering the Čech complex \(\mathrm{\check{C}}(S^n;\pi-\delta)\) on the nose. Hence, by choosing \(G=\mathrm{Bor}(S^n;\delta)\) in Lovász’s bound, we relate the connectivity of Čech complexes of spheres to the chromatic numbers of Borsuk graphs: \[\chi(\mathrm{Bor}(S^n;\delta)) \ge \mathop{\mathrm{conn}}(N(\mathrm{Bor}(S^n;\delta)))+3 = \mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^n;\pi-\delta))+3.\] This recovers the classical result that the chromatic number of the Borsuk graph is at least \(n+2\) for scales \(\delta\) which are only slightly less than \(\pi\) [14]–[16]¹, since in this regime, the nerve lemma [2], [3] applies to give \(\mathrm{\check{C}}(S^n;\pi-\delta)\simeq S^n\), yielding \(\chi(\mathrm{Bor}(S^n;\delta)) \ge \mathop{\mathrm{conn}}(S^n)+3 = n+2\). There is furthermore an equality \(\chi(\mathrm{Bor}(S^n;\delta)) = n+2\) for \(\delta\) sufficiently close to \(\pi\). However, in this paper, we allow the scale \(\delta\) to be far away from \(\pi\). Using known bounds on the chromatic numbers of Borusk graphs in terms of packings and coverings of spheres (see, for example, [18]), we obtain upper bounds on the connectivity of Čech complexes of spheres at all scale parameters.

To lower bound the connectivity of Čech complexes of spheres, we rely on the appendix by Barmak in Farber’s paper [10]. This appendix builds upon prior work [19]–[22] lower bounding the connectivity of clique complexes of graphs. Crucially, Barmak’s appendix generalizes these results to arbitrary simplicial complexes, meaning they can be applied to the non-clique Čech simplicial complexes we study here. We refer the reader to related results on the connectivity of Vietoris–Rips complexes of hypercube graphs [23], on the connectivity of clique complexes of preferential attachment graphs [24], on the connectivity of Vietoris–Rips complexes of spheres [13], and on the connectivity of independence complexes of graphs [25] and hypergraphs [26]. See [8], [27]–[29] for results on the topology of random Čech complexes, [9] for some applications of the fundamental group functor to the Čech filtration of compact geodesic spaces, and [30] for results on the chromatic numbers of random Borsuk graphs.

Researchers in applied topology use Čech and Vietoris–Rips complexes to approximate the shape of a dataset. If one’s dataset is sampled from a manifold, then in the limit, as more and more points are sampled, the persistent homology of the sample converges to the persistent homology of the manifold. For small scales, Hausmann’s theorem [31] implies that the Vietoris–Rips complex of the manifold is homotopy equivalent to the manifold, and the nerve lemma [2] implies that the intrinsic Čech complex of the manifold is homotopy equivalent to the manifold. However, we do not yet have a good mathematical understanding of the behavior of the Vietoris–Rips or Čech complexes of manifolds at larger scales, even though the whole idea of persistent homology is to allow the scale to vary from small to large. The homotopy types of Vietoris–Rips complexes of spheres is a difficult but largely open problem [6], [13], [32], which has important connections to Gromov–Hausdorff distances between unit spheres of different dimensions [33]–[35]. Though the homotopy types of intrinsic Čech complexes of spheres have been studied less, we think this may be an even more natural problem. Indeed, these homotopy types can be viewed as generalizations of the nerve lemma, for one may ask: What are the homotopy types of the nerve of balls in a sphere (or more generally in a manifold) when the radii are now large enough so that the hypotheses of the nerve lemma are no longer satisfied?

We remark that the homotopy types of the intrinsic Čech complexes of the circle are fully understood by [6]. Indeed, we have \(\mathrm{\check{C}}(S^1;r) \simeq S^{2k+1}\) for \(\frac{\pi k}{k+1} < r \le \frac{\pi (k+1)}{k+2}\) for \(k\in {\mathbb{N}}\). The way to interpret these homotopy types is as follows. For \(0<r\le \frac{\pi}{2}\), open balls of radius \(r\) (circular arcs of length \(2r\)) in the circle are geodesically convex, and hence, the nerve lemma applies to give \(\mathrm{\check{C}}(S^1;r)\simeq S^1\). However, once \(r\) exceeds \(\frac{\pi}{2}\), a ball of radius \(r\) is no longer geodesically convex, and indeed, the intersection of two antipodal balls is disconnected. Therefore, the hypotheses of the nerve lemma are not satisfied. So, up to homotopy type, a circle’s worth of disks are attached, giving \(\mathrm{\check{C}}(S^1;r)\simeq S^1*S^1=S^3\) for \(\frac{\pi}{2} < r \le \frac{2\pi}{3}\). Once \(r\) exceeds \(\frac{2\pi}{3}\), the intersection of three evenly spaced balls now has three connected components, and the homotopy type becomes \((S^1*S^1)*S^1=S^3*S^1=S^5\). More generally, for \(\frac{\pi k}{k+1} < r \le \frac{\pi (k+1)}{k+2}\), we have that \(\mathrm{\check{C}}(S^1;r)\) is homotopy equivalent to a \((k+1)\)-fold join of circles \(S^1*\cdots*S^1=S^{2k+1}\).

3 Preliminaries↩︎

In this section, we provide preliminary definitions and notations that we will use for metric spaces, topological spaces, simplicial complexes, and graphs. Important concepts will include covering radii and numbers, connectivity, Čech complexes, Borsuk graphs, and neighborhood complexes.

3.1 Metric spaces↩︎

Let \((X,d)\) be a metric space. Further, let \(B(x,r)\) be the open ball of radius \(r\) centered at \(x\), i.e., \(B(x;r)=\{y\in X \mid d(y,x)<r\}\). Also, let \(B[x,r]=\{y\in X \mid d(y,x)\leq r\}\) be the closed ball of radius \(r\) centered at \(x\).

Our bounds on the connectivity of Čech complexes of spheres will be in terms of the \(k\)-th covering radius or the \(\delta\)-covering number of a metric space \((X,d)\), which we now define.

For \(k\ge 1\), the \(k\)-th covering radius of a metric space \((X,d)\), denoted \(\mathop{\mathrm{cov}}_X(k)\), is defined as \[\mathop{\mathrm{cov}}_X(k) = \inf\left\{r\ge 0\middle|\text{ there exist } x_1,\ldots,x_k \in X \text{ such that } \bigcup_{i=1}^k B[x_i,r] = X \right\}.\] When \(X\) is compact, this infimum is attained (see [13]), in which case \(\mathop{\mathrm{cov}}_X(k)\) is the smallest radius such that \(k\) closed balls of that radius cover \(X\).

We can also ask how many balls of a fixed radius are required to cover a metric space. For \(\delta>0\), the \(\delta\)-covering number of a metric space \((X,d)\), denoted \(\mathop{\mathrm{numCover}}_X(\delta)\), is defined as \[\mathop{\mathrm{numCover}}_X(\delta) = \min\left\{n \ge 1\middle|\text{ there exist } x_1,\ldots,x_n \in X \text{ such that } \bigcup_{i=1}^n B[x_i,\delta] = X \right\}.\] Analogously, we can ask how many points in \(X\) can be chosen such that any two points are more than a specified distance apart. For \(\delta>0\), the \(\delta\)-packing number of a metric space \((X,d)\), denoted \(\mathop{\mathrm{numPack}}_{X}(\delta)\), is defined as \[\mathop{\mathrm{numPack}}_{X}(\delta)=\max\left\{m \ge 1\middle|\text{ there exist } x_1,\ldots,x_m \in X \text{ such that } d(x_i,x_j) > \delta \text{ for all } i,j \right\}.\] We note that if the diameter of \(X\) is infinite, then both \(\mathop{\mathrm{numCover}}_X(\delta)\) and \(\mathop{\mathrm{numPack}}_X(\delta)\) are infinite for any \(\delta> 0\).

The main metric space of interest in this paper is the \(n\)-sphere \(S^n=\{x\in{\mathbb{R}}^{n+1}~|~\|x\|=1\}\), equipped with the geodesic metric. In other words, the distance between two points \(x,y\in S^n\) is given by \(d(x,y)=\arccos(x\cdot y)\in[0,\pi]\). With this metric, the sphere \(S^n\) has diameter \(\pi\).

3.2 Topological spaces↩︎

We write \(Y\simeq Y'\) to denote that the two topological spaces \(Y\) and \(Y'\) are homotopy equivalent. The connectivity of a non-empty topological space \(Y\), denoted \(\mathop{\mathrm{conn}}(Y)\), is the maximal index \(k\) such that the homotopy groups \(\pi_i(Y)\) are trivial for all \(i\le k\).

For a commutative ring \(R\) with unity, the \(R\)-homological dimension of a non-empty topological space \(Y\), denoted \(\mathop{\mathrm{h-dim}}_R(Y)\), is the maximal degree \(i\) such that the \(i\)-th reduced homology group of \(Y\) with coefficients in \(R\) is non-zero, i.e., \(\widetilde{H}_i(Y; R)\neq 0\).

We note that connectivity and \(R\)-homological dimensions are homotopy invariants of topological spaces, i.e., if \(Y\simeq Y'\), then \(\mathop{\mathrm{conn}}(Y)=\mathop{\mathrm{conn}}(Y')\) and \(\mathop{\mathrm{h-dim}}_R(Y)=\mathop{\mathrm{h-dim}}_R(Y')\).

3.3 Simplicial complexes↩︎

A simplicial complex \(K\) on a vertex set \(V\) is a collection of subsets of \(V\), containing all singletons, such that if \(\sigma\in K\) and \(\tau\subseteq \sigma\), then \(\tau \in K\) as well. In this paper, we identify simplicial complexes with their geometric realizations. We will be most interested in simplicial complexes that can be built on top of metric spaces, such as Čech and Vietoris–Rips simplicial complexes.

A Čech complex on a metric space \((X,d)\) for scale \(r > 0\), denoted \(\mathrm{\check{C}}(X;r)\), is the nerve of the collection \(\{B(x,r)\}_{x \in X}\) of open balls of radius \(r\) in \(X\), indexed by the points of \(X\). More explicitly, \[\mathrm{\check{C}}(X;r) = \left\{ \text{finite }\sigma \subseteq X~|~\bigcap_{x \in \sigma}B(x,r) \ne \emptyset \right\}.\] For \(k\ge 0\) and \(x_0,\ldots,x_k\in X\), we have that \(\sigma = [x_0,\ldots,x_k]\) is a simplex in \(\mathrm{\check{C}}(X;r)\) if there exists some \(z_{\sigma} \in X\) such that \(x_i \in B(z_{\sigma},r)\) for all \(0 \le i \le k\), i.e., if the vertex set of \(\sigma\) is contained in an open ball of radius \(r\).

A Vietoris–Rips complex on a metric space \((X,d)\) for scale \(r > 0\), denoted \(\mathrm{VR}(X;r)\), is a simplicial complex having \(X\) as its vertex set and a finite set \(\sigma \subseteq X\) as a simplex if \(\mathop{\mathrm{diam}}(\sigma) < r\); see [36], [37]. It is easy to see that \(\mathrm{\check{C}}(X;r)\) is a subcomplex of \(\mathrm{VR}(X;2r)\).

For the case when \(X = S^n\) is the \(n\)-sphere of diameter \(\pi\) equipped with the geodesic metric, the homotopy equivalence \(\mathrm{\check{C}}(S^n;r) \simeq S^n\) for \(0 < r < \frac{\pi}{2}\) is known by the nerve lemma (for the statement of the nerve lemma, see [10] or [3]).

3.4 Graphs↩︎

All graphs in this paper are simple graphs, meaning there are no loops, and at most a single edge between any two vertices. Formally, a graph \(G=(V,E)\) consists of a set of vertices \(V\) and a set \(E\) of edges, where each edge is a subset of \(V\) of size two. For \(v,v'\in V\), we write \(v\sim v'\) to denote that the edge \(\{v,v'\}\) is in \(E\).

Crucially, we will consider graphs with infinitely many vertices and edges. For example, for \(n\ge 1\) and \(r>0\), the 1-skeleton of the Čech complex \(\mathrm{\check{C}}(S^n;r)\) is an infinite graph.

The chromatic number of a graph \(G=(V,E)\), denoted \(\chi(G)\), is the minimum number of colors needed to label the vertices of \(G\) such that no two adjacent vertices share the same color.

The neighborhood complex of a graph \(G=(V,E)\), denoted \(N(G)\), is the simplicial complex with vertex set \(V\), which contains a finite subset \(\sigma\subseteq V\) as a simplex if there is some vertex \(v\in V\) such that \(w\sim v\) for all \(w\in \sigma\).

The Borsuk graph of \(S^n\) for scale \(\delta>0\), denoted \(\mathrm{Bor}(S^n;\delta)\), is a simple graph whose vertex set is \(S^n\) and whose edges are all pairs of vertices \(x,y\in S^n\) with \(d(x,y)> \delta\).

We will see in Section 5 that the neighborhood complex of the (open) Borsuk graph \(\mathrm{Bor}(S^n;\delta)\) is equal to the Čech complex \(\mathrm{\check{C}}(S^n;\pi-\delta)\); the neighborhood complex of the closed Borsuk graph \(\mathrm{Bor}[S^n;\delta]\) is a nerve complex of closed balls instead of open balls.

4 A lower bound on connectivity↩︎

The goal of this section is to provide a lower bound on \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^n;\pi-\delta))\), the connectivity of the Čech complex of the \(n\)-sphere \(S^n\) at the scale \(\pi-\delta\), where \(0<\delta<\pi\).

Using the results from Barmak’s Appendix in [10], it has been shown in [13] that if \(0<\delta < \mathop{\mathrm{cov}}_{S^n}(2k+2)\), then the connectivity of the Vietoris–Rips complex of \(S^n\) at scale \(\pi-\delta\) is at least \(k\), i.e., \(\mathop{\mathrm{conn}}(\mathrm{VR}(S^n;\pi-\delta)) \ge k\). In the same spirit, here we use Barmak’s technique to get a lower bound on \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^n;\pi-\delta))\).

We recall that the closed star of a vertex \(v\) in a simplicial complex \(K\), denoted \(\mathop{\mathrm{st}}_K(v)\), is the subcomplex \(\mathop{\mathrm{st}}_K(v) = \left\{ \sigma \in K \mid \sigma \cup \{v\} \in K \right\}\). A simplicial complex \(K\) is said to be \(\ell\)-conic if any subcomplex of at most \(\ell\) vertices is contained in a simplicial cone, i.e., in the closed star \(\mathop{\mathrm{st}}_K(v)\) of some vertex \(v\). Barmak’s result [10] states that if \(K\) is \((2k+2)\)-conic, then \(K\) is \(k\)-connected.

We note that \(\mathop{\mathrm{cov}}_{S^n}(2k+2)\) is non-increasing in \(k\), and that \(\mathop{\mathrm{cov}}_{S^n}(2k+2)\to 0\) as \(k\to \infty\).

We can reinterpret the result of Proposition 3 to get an explicit lower bound on \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^n;\pi-\delta))\).

5 An upper bound on connectivity↩︎

We now give an upper bound on the connectivity of Čech complexes of spheres. We begin by noting that the approach used to upper bound the connectivity of Vietoris–Rips complexes of spheres will not work in the Čech case. Indeed, the proof of [13] constructed an odd map from \(\mathrm{VR}(S^n;\pi-\delta)\) into the Euclidean space \({\mathbb{R}}\) that missed the origin. This is possible only since \(\mathrm{VR}(S^n;\pi-\delta)\) contains no edges between antipodal vertices of \(S^n\) for \(\delta>0\). Unfortunately, the Čech complex \(\mathrm{\check{C}}(S^n;\pi-\delta)\) does contain all antipodal edges for \(\delta<\frac{\pi}{2}\), which is the regime of interest.

Therefore, we upper bound the connectivity of Čech complexes of spheres via a different approach, namely by relating this connectivity to the chromatic numbers of Borsuk graphs. Let \(\mathrm{Bor}(S^n;\pi-\delta)\) be the Borsuk graph whose vertex set is \(S^n\) and whose edges are all pairs of vertices at a distance more than \(\pi-\delta\). The basis for our connection is the observation that the neighborhood complex of the Borsuk graph \(\mathrm{Bor}(S^n;\delta)\) is the same as the Čech complex \(\mathrm{\check{C}}(S^n;\pi-\delta)\). Indeed, for \(\sigma\subseteq S^n\) finite, we have that \[\begin{align} \sigma\in N(\mathrm{Bor}(S^n;\delta)) \Longleftrightarrow\;& \existsv\in S^n \text{ with }x\sim v\text{ in }\mathrm{Bor}(S^n;\delta) \text{ for all } x\in\sigma \\ \Longleftrightarrow\;& \exists v\in S^n \text{ with }d(x,v)> \delta \text{ for all } x\in\sigma \\ \Longleftrightarrow\;& \exists -v\in S^n \text{ with }d(x,-v)<\pi-\delta \text{ for all } x\in\sigma \\ \Longleftrightarrow\;& \sigma \in \mathrm{\check{C}}(S^n;\pi-\delta). \end{align}\] So, \(N(\mathrm{Bor}(S^n;\delta))=\mathrm{\check{C}}(S^n;\pi-\delta)\).

Lovász’s famous result [11] says for any graph \(G\), the chromatic number satisfies \(\chi(G)\ge \mathop{\mathrm{conn}}(N(G))+3\), where \(N(G)\) is the neighborhood complex of \(G\).

Using Lovász’s result and the fact that \(N(\mathrm{Bor}(S^n;\delta))=\mathrm{\check{C}}(S^n;\pi-\delta)\) for each \(n\ge 1\) and \(\delta \in (0,\pi)\), we obtain the following bound.

The problem of bounding \(\chi(\mathrm{Bor}(S^n;\delta))\) for \(0<\delta<\pi\) close to \(\pi\) is classical. One version of the Borsuk–Ulam theorem (the Lyusternik–Schnirel’man–Borsuk covering theorem) gives, and is in fact equivalent to, the statement that \(\chi(\mathrm{Bor}[S^n;\delta])\ge n+2\) for all \(\delta<\pi\); see, for example, [14], [39], [40] and [41]. Taking \(\varepsilon > 0\) such that \(\delta + \varepsilon < \pi\), the left inclusion in 1 gives that \(\chi(\mathrm{Bor}(S^n;\delta))\ge n+2\), as well. Furthermore, Raigorodskii shows that \(\chi(\mathrm{Bor}[S^n;\delta])=n+2\) for all \(s_n<\delta<\pi\), where \(s_n\) is the diameter of the radial projection of a single \(n\)-dimensional face of a regular \((n+1)\)-dimensional simplex inscribed in \(S^n\) [15], [16]. Once again, 1 implies that \(\chi(\mathrm{Bor}(S^n;\delta))=n+2\) for all \(s_n<\delta<\pi\); see Figure 3 for the case \(n=2\). From [42] (after plugging \(\cos \ell=-\frac{1}{n+1}\) into (2.17) and (2.18) of [42]), we have that \[s_n=\begin{cases} \arccos{\left(-\frac{n+1}{n+3}\right)} & \text{if }n \text{ is odd} \\ \arccos{\left(-\sqrt{\frac{n}{n+4}}\right)} & \text{if }n \text{ is even}. \end{cases}\]

The asymptotics of the chromatic numbers of Borsuk graphs of \(S^n\) (though not the exact values) may be reasonably well controlled by covering and packing numbers on spheres. See, for example, [18]², which states that when \(\delta > 2\mathop{\mathrm{cov}}_{S^n}(m)\) for some \(m \ge 2\), then \(\chi(\mathrm{Bor}[S^n;\delta]) \le m\). Since \(\mathrm{Bor}(S^n;\delta)\subseteq \mathrm{Bor}[S^n;\delta]\), we have that \(\chi(\mathrm{Bor}(S^n;\delta)) \le m\).

We note that \(2\mathop{\mathrm{cov}}_{S^n}(k+1)\) is non-increasing in \(k\), and that \(2\mathop{\mathrm{cov}}_{S^n}(k+1)\to 0\) as \(k\to \infty\). So, for \(\delta>0\), there always exists some integer \(k\) such that \(\delta>2\mathop{\mathrm{cov}}_{S^n}(k+1)\).

Propositions 3 and 6 together prove Theorem 1.

We can reinterpret the result of Proposition 6 to get an explicit upper bound on \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^n;\pi-\delta))\).

Corollaries 3 and 4 together prove Corollary 1.

6 The case of the circle↩︎

In the case of the circle, we know the homotopy types of \(\mathrm{\check{C}}(S^1;r)\) for all \(r\); see [6]. This gives us one “data point” (\(n=1\)) that any more general results for \(\mathrm{\check{C}}(S^n;r)\) with \(n\ge 1\) will need to generalize. See Figure 2.

By [6], the homotopy types of \(\mathrm{\check{C}}(S^1;r)\) are all odd spheres. It turns out that \[\label{eq:S1cech} \mathrm{\check{C}}(S^1;r) \simeq S^{2k+1}\text{if}r \in \left(\frac{\pi k}{k+1},\frac{\pi (k+1)}{k+2}\right],\tag{2}\] with \(\mathrm{\check{C}}(S^1;r)\) contractible for all \(r\ge \pi\). From this, we get that \[\label{eq:S1conn} \mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^1;\pi-\delta)) = 2k\text{if}\delta \in \left[\frac{\pi}{k+2},\frac{\pi}{k+1}\right).\tag{3}\]

6.1 Comparing the lower bound↩︎

We check the lower bound to \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^n;\pi-\delta))\) obtained in Section 4 in the case \(n=1\).

From Proposition 3, we have that if \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^1;\pi-\delta)) \le k-1\), then \(\delta\ge\mathop{\mathrm{cov}}_{S^1}(2k+2)\). Via the substitution \(k\mapsto 2k+1\), this means that if \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^1;\pi-\delta)) \le 2k\), then \(\delta \ge \mathop{\mathrm{cov}}_{S^1}(4k+4) = \frac{\pi}{4k+4}\). Using the exact connectivity values of \(\mathrm{\check{C}}(S^1;\pi-\delta)\) in 3 , we compare the lower bounds to \(\delta\), namely \(\frac{\pi}{4k+4}\) and \(\frac{\pi}{k+2}\), and see that the bound on \(\delta\) given by Proposition 3 is off by a multiplicative factor of nearly \(4\) for even connectivity when \(n=1\). Hence, the lower bound to \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^n;\pi-\delta))\) from Corollary 3 is not sharp for \(n=1\).

6.2 Comparing the upper bound↩︎

We now check the upper bound to \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^n;\pi-\delta))\) obtained in Section 5 in the case \(n=1\). To do that, we first note the following.

Let us compare both Lovász’s bound (Lemma 1) and Proposition 6, which give upper bounds on \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^n;\pi-\delta))\), to the exact connectivity values when \(n=1\).

• Plugging \(n=1\) into Lovász’s bound \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^n;\pi-\delta)) \le \chi(\mathrm{Bor}(S^n;\delta)) - 3\), and using the exact chromatic numbers of the Borsuk graphs \(\mathrm{Bor}(S^1;\delta)\) from Lemma 2, together give \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^1;\pi-\delta)) \le \lceil\frac{2\pi}{\delta}\rceil - 3\). If \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^1;\pi-\delta)) = 2k\), then \(2k+3 \le \lceil\frac{2\pi}{\delta}\rceil\), which implies that \(\delta < \frac{2\pi}{2k+2} = \frac{\pi}{k+1}\).

• Proposition 6 states if \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^n;\pi-\delta)) \ge k-1\), then \(\delta\le 2\mathop{\mathrm{cov}}_{S^n}(k+1)\). For \(n=1\), if \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^1;\pi-\delta)) \ge k-1\), then \(\delta\le 2\mathop{\mathrm{cov}}_{S^1}(k+1) = \frac{2\pi}{k+1}\). Via the substitution \(k\mapsto 2k+1\), we get that if \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^1;\pi-\delta)) \ge 2k\), then \(\delta\le \frac{2\pi}{2k+2} = \frac{\pi}{k+1}\).

• By 3 , \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^1;\pi-\delta) = 2k\) if and only if \(\delta \in [\frac{\pi}{k+2},\frac{\pi}{k+1})\).

Lovász’s bound \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^n;\pi-\delta)) \le \chi(\mathrm{Bor}(S^n;\delta)) - 3\) and Proposition 6 both give the optimal upper bound of \(\frac{\pi}{k+1}\) on \(\delta\), for even connectivity, when \(n=1\). The former excludes the possibility \(\delta=\frac{\pi}{k+1}\), whereas the latter does not, and hence, the former upper bound is slightly better. This makes sense since our Proposition 6 is derived from Lovász’s bound but does not use exact chromatic numbers of Borsuk graphs.

7 Homological dimension↩︎

In this section, we explore the largest dimension in which the homology of \(\mathrm{\check{C}}(S^n;r)\) is non-zero. For a topological space \(Y\) and a commutative ring \(R\) with unity, the \(R\)-homological dimension of \(Y\) is defined as \[\mathop{\mathrm{h-dim}}_R(Y) \mathrel{\vcenter{:}}= \max\{i\in{\mathbb{Z}}\mid \widetilde{H}_i(Y;R) \ne 0\}.\]

The \({\mathbb{Z}}\)-homological dimension of a space is informative of its topology: a space that is homotopy equivalent to a CW complex of dimension \(k\) has \({\mathbb{Z}}\)-homological dimension at most \(k\). The \({\mathbb{Z}}\)-homological dimension of a space is often connected to its homotopy connectivity. Indeed, if \(Y\) is simply connected, then by the Hurewicz theorem [3], we have \(\mathop{\mathrm{conn}}(Y) \le \mathop{\mathrm{h-dim}}_{{\mathbb{Z}}}(Y)-1\). Note that \(\mathop{\mathrm{conn}}(Y)\) need not³ be a lower bound to \(\mathop{\mathrm{h-dim}}_R(Y)-1\) for a general ring \(R\).

We know that \(\mathrm{\check{C}}(S^n;\pi-\delta)\simeq S^n\) for all \(\delta\in[\pi/2,\pi)\) due to the nerve lemma. We also know that \(\mathrm{\check{C}}(S^1;\pi-\delta)\) is homotopic to some odd-dimensional sphere for each \(\delta>0\). Hence, the \({\mathbb{Z}}\)-homological dimension of \(\mathrm{\check{C}}(S^n;\pi-\delta)\) is known in all these cases. So, let us restrict our attention to the case when \(n\ge 2\) and \(\delta\in(0,\pi/2)\).

In Proposition 3, we gave a lower bound on the connectivity \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^n;\pi-\delta))\). In particular, if \(0<\delta<\mathop{\mathrm{cov}}_{S^n}(2k+2)\), then \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^n;\pi-\delta)) \ge k\). For \(n\ge 2\), it follows from [9] that the Čech complex \(\mathrm{\check{C}}(S^n;\pi-\delta)\) is simply connected for each \(\delta\in (0,\pi/2)\). Hence, using the relation between connectivity and \({\mathbb{Z}}\)-homological dimension stated in the previous paragraph, we get a lower bound to \(\mathop{\mathrm{h-dim}}_{{\mathbb{Z}}}(\mathrm{\check{C}}(S^n;\pi-\delta))\): if \(0<\delta<\mathop{\mathrm{cov}}_{S^n}(2k+2)\), then \(\mathop{\mathrm{h-dim}}_{{\mathbb{Z}}}(\mathrm{\check{C}}(S^n;\pi-\delta))\geq k+1\). In other words, for any \(\delta \in (0,\pi/2)\) and \(n\ge 2\), Corollary 3 gives that \[\label{eq:h-dimBarmak} \mathop{\mathrm{h-dim}}_{{\mathbb{Z}}}(\mathrm{\check{C}}(S^n;\pi-\delta))\ge \tfrac{1}{2}\mathop{\mathrm{numCover}}_{S^n}(\delta) - 1.\tag{4}\]

Next, we try to use ideas from [43] to get a lower bound to \(\mathop{\mathrm{h-dim}}_{{\mathbb{Z}}}(\mathrm{\check{C}}(S^n;\pi-\delta))\) better than that provided in 4 . We consider the \({\mathbb{Z}}_2\)-homological dimension. Using the universal coefficient theorem for homology [3], one can see that for any space \(Y\), we have \(\mathop{\mathrm{h-dim}}_{{\mathbb{Z}}}(Y)\ge \mathop{\mathrm{h-dim}}_{{\mathbb{Z}}_2}(Y)-1\). In fact, if \(H_*(Y;{\mathbb{Z}})\) is torsion-free, then \(\mathop{\mathrm{h-dim}}_{{\mathbb{Z}}}(Y)\ge \mathop{\mathrm{h-dim}}_{{\mathbb{Z}}_2}(Y)\). So, a lower bound to \(\mathop{\mathrm{h-dim}}_{{\mathbb{Z}}_2}(\mathrm{\check{C}}(S^n;\pi-\delta))\) will give us a lower bound to \(\mathop{\mathrm{h-dim}}_{{\mathbb{Z}}}(\mathrm{\check{C}}(S^n;\pi-\delta))\).

To potentially lower bound \(\mathop{\mathrm{h-dim}}_{{\mathbb{Z}}_2}(\mathrm{\check{C}}(S^n;\pi-\delta))\), the theory of box complexes will be relevant. Box complexes of finite graphs have been well-studied; we refer the reader to [41], [43], [44].

There are several related definitions of box complexes, which all share similar properties. For a finite graph \(G\), the box complex \({\mathcal{B}}(G)\) is a free \({\mathbb{Z}}_2\)-simplicial complex satisfying the following properties:

1. The box complex \({\mathcal{B}}(G)\) and the neighborhood complex \(N(G)\) are homotopy equivalent.

2. The box complex \({\mathcal{B}}(K_m)\) of the complete graph \(K_m\) is \({\mathbb{Z}}_2\)-homotopy equivalent to the sphere \(S^{m-2}\).

3. If \(H\) is a subcomplex of \(G\), then \({\mathcal{B}}(H)\) is a \({\mathbb{Z}}_2\)-subcomplex of \({\mathcal{B}}(G)\).

Since box complexes have been studied on finite graphs, we restrict ourselves to finite subsets \(X\) of \(S^n\) and work with them, in the hope that the behavior of Čech complexes of finite subsets governs the behavior of Čech complexes of the entire sphere as the finite subset grows denser and denser. Instead of the (intrinsic) Čech complex \(\mathrm{\check{C}}(X;r)\mathrel{\vcenter{:}}= \mathrm{Nerve}(\{B_{X}(x;r)\}_{x\in X})\) defined using balls in \(X\), we emphasize that moving forward, we will instead work with the ambient Čech complex \(\mathrm{\check{C}}(X,S^n;r)\mathrel{\vcenter{:}}= \mathrm{Nerve}(\{B_{S^n}(x;r)\}_{x\in X})\) defined using balls in \(S^n\). That is, \(\sigma \subseteq X\) is a simplex in \(\mathrm{\check{C}}(X,S^n;r)\) if the intersection \(\cap_{x\in \sigma}B_{S^n}(x,r)\) of balls in \(S^n\) is nonempty.

We define the (open) Borsuk graph of \(X\subseteq S^n\) for scale \(\delta>0\) similarly, i.e., the vertices of \(\mathrm{Bor}(X;\delta)\) are the points in \(X\) and there is an edge between \(v, w\in X\) if \(d(v, w)> \delta\). Here, the metric \(d\) is the geodesic distance, derived from \(S^n\). We use \(\mathrm{\check{C}}(X,S^n;r)\) instead of \(\mathrm{\check{C}}(X;r)\) since \(N(\mathrm{Bor}(X;\delta)) = \mathrm{\check{C}}(X,S^n;\pi-\delta)\).

To bound \(\mathop{\mathrm{h-dim}}_{{\mathbb{Z}}_2}(\mathrm{\check{C}}(X,S^n;r))\) from below for finite \(X\subseteq S^n\), we will also use the fact that if \(Y\) is a finite free \({\mathbb{Z}}_2\)-simplicial complex and if there is a \({\mathbb{Z}}_2\)-map from \(S^k\) to \(Y\), then \(\mathop{\mathrm{h-dim}}_{{\mathbb{Z}}_2}(Y)\ge k\); see [45] or [43]. We also use the packing number from Section 3.1.

Using Proposition 8 and the relationship between \(\mathop{\mathrm{h-dim}}_{{\mathbb{Z}}}(Y)\) and \(\mathop{\mathrm{h-dim}}_{{\mathbb{Z}}_2}(Y)\) stated above, we get the following.

What about the case when \(X=S^n\) is infinite? Given an infinite graph \(G\), while we can define its box complex \({\mathcal{B}}(G)\), we do not know if \({\mathcal{B}}(G)\) satisfies the same properties as those mentioned above for the box complexes of finite graphs.

We note that if 5 is true and, additionally, if the integral homology of \(\mathrm{\check{C}}(S^n;\pi-\delta)\) is torsion-free for some \(n\ge 1\) and \(\delta>0\), then we have that \[\label{eq:h-dimMatsushita2} \mathop{\mathrm{h-dim}}_{{\mathbb{Z}}}(\mathrm{\check{C}}(S^n;\pi-\delta)) \ge \mathop{\mathrm{numPack}}_{S^n}(\delta)-2.\tag{6}\]

It seems that the proof technique of [45] might offer tools towards proving 5 (and consequently 6 ). Indeed, proceeding as in the proof of [45], we get that for an infinite \({\mathbb{Z}}_2\)-complex \(Y\) equipped with a \({\mathbb{Z}}_2\)-map \(S^k \to Y\), either \(\mathop{\mathrm{h-dim}}_{{\mathbb{Z}}_2}(Y) \ge k\) or \(\mathop{\mathrm{h-dim}}_{{\mathbb{Z}}_2}(\tfrac{Y}{{\mathbb{Z}}_2})\) is infinite.

8 Conclusion↩︎

We conclude with a list of open questions and conjectures, that, we hope, will stimulate further interest and research.

Conjecture 12 is true for \(n=1\) [6], and for \(n\ge 2\), it is known that \(\mathrm{\check{C}}(S^n;r)\) is simply connected for all \(r\). For \(n\ge 3\), even though though \(\mathrm{\check{C}}(S^n;r)\simeq S^n\) has connectivity \(n-1\) for \(0<r<\frac{\pi}{2}\), it is not known if \(\mathop{\mathrm{conn}}(\mathrm{\check{C}}(S^n;r))\ge n-1\) for all \(\frac{\pi}{2}\le r<\pi\).

If so, Conjecture 13, which is true in the case of the circle \((n=1)\), could be proven by showing that in such a Morse theory, there are only countably many critical events for \(\mathrm{\check{C}}(S^n;r)\) as \(r\) increases.

We know that this conjecture is true for \(n=1\) and all \(r>0\), and for all \(n\ge 1\) when \(r<\frac{\pi}{2}\).

We note that Conjecture 15 is false if one defines the Čech complexes using closed balls instead of open balls; see [6].

If \(\mathrm{\check{C}}(S^n;r)\) were homotopy equivalent to a \(k\)-dimensional CW complex, then \(\mathop{\mathrm{h-dim}}_{{\mathbb{Z}}}(\mathrm{\check{C}}(S^n;r))\le k\). Dually, if \(\mathop{\mathrm{h-dim}}_{{\mathbb{Z}}}(\mathrm{\check{C}}(S^n;r)) > k\) (see Question 9), then \(\mathrm{\check{C}}(S^n;r)\) could only be homotopy equivalent to a CW complex of dimension larger than \(k\).

References↩︎