2
$\begingroup$

Wikipedia states: The Čech complex is a subcomplex of the Vietoris–Rips complex.

And they reference Ghrist which essentially makes the definitions:

Given a finite point cloud $X$ and $\epsilon >0$, we construct the Čech complex $C_\epsilon(X)$ as follows: Take the elements of $X$ as the vertex set of $C_\epsilon(X)$. Then, for each $\sigma\subset X$, let $\sigma\in C_\epsilon(X)$ if the set of $\epsilon$-balls centered at points of $\sigma$ has a nonempty intersection.

Similarly,

The Vietoris Rips Complex of scale $\epsilon$ on $X$ is an abstract simplicial complex whose simplices are all finite collections of points in $X$ of pairwise distance $\leq\epsilon$.

Ghrist also makes the claim that the Cech complex is a subcomplex of the Vietoris Rips complex $VR_\epsilon$, and sometimes a proper subcomplex (p.30), but does not state any scale for the Cech complex in that statement. I then take it as implicit that this means that $C_\epsilon(X)\leq VR_\epsilon(X)$, i.e. for the same $\epsilon$. But, I do not see how this can be:

Just simply take $X$ to be two points $x_1,x_2$ at distance $1$ from eachother. Then clearly $C_{0.6}(X)$ is two vertices and an edge, but $VR_{0.6}(X)$ is just two vertices.

Question: Either it seems it would be the other way round ($V\leq C$), or we have that $C_\epsilon\leq VR_{2\epsilon}$ or something. What is the relation, and/or what am I misunderstanding?

And, if it is, for example, $C_\epsilon\leq VR_{2\epsilon}$, what motivates a statement of the form 'The Čech complex is a subcomplex of the Vietoris–Rips complex' without any reference to scale?

$\endgroup$
2
  • $\begingroup$ The motivation probably includes that a good reader can figure out the proper reference to scale, as you have. $\endgroup$
    – Lee Mosher
    Jun 4, 2021 at 19:20
  • 2
    $\begingroup$ @LeeMosher Sure, but the reason I figured there was a misunderstanding lingering somewhere is that: It just seemed a bit arbitrary to say "...is a subcomplex..." if the inequality could equally well be reversed (and even is reversed for the same scale) depending on the scale. I felt there was some other motivation that I'd missed. $\endgroup$
    – ciru_4011
    Jun 4, 2021 at 19:34

1 Answer 1

3
$\begingroup$

As you have shown, in general $C_\epsilon(Q)\leq VR_\epsilon(Q)$ is false. But in fact both

  1. $C_\epsilon(Q)\leq VR_{2\epsilon}(Q)$

  2. $VR_\epsilon(Q)\leq C_\epsilon(Q)$

are true. I am not sure whether 2. is true for an arbitrary metric space $(Q, d)$, but here we have $Q \subset \mathbb R^n$ and $d$ is the usual Euclidean metric. Thus, given $n$ points $q_i \in Q$ such that $\lvert q_i - q_j \rvert < \epsilon$ for all $i,j$, we define the barycenter $b = \sum_{i=1}^n \frac{1}{n}q_i$ of the $q_i$ and easily verify that $b \in \bigcap _{i=1}^n B_\epsilon(q_i)$: We have $$\lvert b - q_j \rvert = \lvert\sum_{i=1}^n \frac{1}{n}q_i - \sum_{i=1}^n \frac{1}{n}q_j \rvert = \lvert\sum_{i=1}^n \frac{1}{n}(q_i - q_j) \rvert = \lvert \frac{1}{n} \sum_{i=1}^n (q_i - q_j) \rvert \le \frac{1}{n} \sum_{i=1}^n \lvert q_i - q_j \rvert\\ < \frac{1}{n} n \epsilon = \epsilon .$$

The statement

The Čech complex is a subcomplex of the Vietoris–Rips complex $VR_\epsilon(Q)$

suggests that $C_\epsilon(Q)\leq VR_{\epsilon}(Q)$, but it needs a more flexible interpretation. This is 1.

The problem with Ghrist's exposition is that is does not become clear what the purpose of the Vietoris–Rips / Čech complex really is.

I think you need to know Čech (co)homology if you want to understand that point. Unfortunately Ghrist does not introduce this properly. He only defines the Čech homology groups of open covers of a space $X$. The Čech (co)homology groups of a space $X$ are defined as follows:

The set $\mathscr C(X)$ of all open covers of $X$ is partially ordered by refinement; this makes $\mathscr C(X)$ an inverse system. The Čech homology groups (cohomology groups) of $X$ are defined as the inverse limit (direct limit) of the Čech homology groups (cohomology groups) of the open covers of $X$.

A similar construction gives us the Vietoris (co)homology groups of $X$.

For the limit processes we do not need the full set $\mathscr C(X)$, any cofinal subsystem will do. If $X$ is compact, the coverings by balls of a fixed diameter form such a cofinal subsystem. Now the above arguments concerning the Čech and Vietoris-Rips complexes show that the Čech and the Vietoris (co)homology groups agree.

This was a very rough explanation, but I hope it gives at least an idea what is going on here.

$\endgroup$
1
  • $\begingroup$ It most certainly do give me a better idea. I expected there to be more to the story basically (and I couldn't have hoped for a better answer). Regardless of what inequalities hold or not, does it also make sense to define these complexes for arbitrary distances? (i.e. non-neg, reflexive and symmetric real functions on $X^2$) Everywhere I find them, I only see them defined for $\mathbb{R}^n$ or possibly a metric space. I thought perhaps there's a reason for this other than that these are just the most common/useful examples. $\endgroup$
    – ciru_4011
    Jun 5, 2021 at 12:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .