Smallest offset so that the Rips complex is always a subcomplex of the Cech complex.

54 Views Asked by At

Let $X$ be a finite set of points in $\mathbb R^n$.

For $\epsilon >0$, let $\mathcal R_\epsilon (X)$ and $\mathcal C_\epsilon (X)$ be the Rips and Cech complexes on $X$, respectively.

It's well-known the Cech complex is always a subcomplex of the Rips complex, but when is the Rips complex a subcomplex of the Cech complex?

In other words, what is the smallest $\delta > 0$ (as a function of $n$) such that $\mathcal C_\delta (X)$ is a subcomplex of $\mathcal R_\epsilon (X)$ for all $\epsilon >0$?

(This appears as a bonus problem in Problem Set 1 of Vidit Nanda's Computational Algebraic Topology course)

Well, for the Rips complex to be a subcomplex we would need that wherever a subset of $k$ points are pairwise at most $\epsilon$ distance apart from each other, the balls of radius $\delta$ around those points have nonempty intersection.

Nanda specifies in the question that $\delta$ is a function of $n$, which I don't quite understand the relevance of.

1

There are 1 best solutions below

0
On BEST ANSWER

De Silva and Ghrist showed in "Coverage in sensor networks via persistent homology" (theorem 2.5) that if $X \subseteq \mathbb{R}^n$, then $$\mathcal{R}_{\epsilon'}(X) \subseteq \mathcal{C}_\epsilon(X) \subseteq \mathcal{R}_\epsilon(X)$$ whenever $\epsilon \geq \epsilon' \sqrt{\frac{2n}{n+1}}$, and that this constant is optimal in general (in fact, attained by points on a regular $n$-simplex).