18
$\begingroup$

Assuming we have a set of points $X=\{x_1,..,x_n\}$, all in $\mathbb{R}^d$, and construct the Vietoris-Rips-Complex $V_\epsilon (X)$ for some distance parameter $\epsilon > 0$. Is it possible to have non-trivial (simplicial) homology groups $H_k(V_\epsilon (X))$ in degree $k\geq d$?

If no, is there a proof? If yes, are there examples, e.g. for $d=2$ with the Euclidean distance?

Update: j.c.'s answer shows that the answer is no for $d=2$ and the $\mathcal{l}_1$- or $\mathcal{l}_\infty$-distances.

Improve this question
$\endgroup$
2
  • $\begingroup$ You may confirm, or object: the distance you are alluding to is the Euclidean distance on $\mathbb{R}^d$. $\endgroup$
    – Luc Guyot
    Jun 14, 2018 at 19:33
  • $\begingroup$ Good point. I was assuming Euclidean distance and j.c.'s answer gives interesting insighs, that it actually does matter what distance we take. $\endgroup$
    – Arkadi
    Jun 18, 2018 at 8:17

3 Answers 3

Reset to default
19
$\begingroup$

I have examples for $\ell_2$ distance in $\mathbb{R}^2$.

In particular, take $2n+2$ points at the vertices of a regular polygon of unit radius, and set the distance parameter to be slightly less than $2$ (so that two points are joined by an edge if and only if they are not antipodal).

Here's an image for $n=2$, from this page:

octahedron

The corresponding simplicial complex is the boundary of the $(n+1)$-dimensional orthoplex (hyper-octahedron), which is homeomorphic to $S^n$ and therefore has a non-trivial $H_n$.

Fun fact: you can take connected sums of these regular polygon examples to realise finite Vietoris-Rips complexes in $\mathbb{R}^2$ with any finitely-supported finite sequence of Betti numbers.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Very nice - I added an image from Wikipedia. $\endgroup$
    – j.c.
    Jun 18, 2018 at 16:59
  • $\begingroup$ Nice example! Is there any other example of finite sets $X\subset \mathbb{R}^2$ (equipped with the $l_2$ metric) that yields $S^n$ as its Vietoris-Rips complex for some $n$? $\endgroup$
    – Mustafa
    Apr 13, 2019 at 3:50
  • $\begingroup$ @Mustafa I can't immediately find any larger examples which are homeomorphic to $S^n$. The main obstruction is that once you have $n + 1$ vertices forming an $n$-simplex, you're not allowed to add any other vertices within its convex hull. But if you want $S^n$, then any point in general position in $\mathbb{R}^2$ must lie within the convex hull of an even number of $n$-simplices. $\endgroup$
    – Adam P. Goucher
    Apr 13, 2019 at 12:07
  • $\begingroup$ @AdamP.Goucher I would conjecture that your example with $2n+2$ points is the only one that yields $S^n$. $\endgroup$
    – Mustafa
    Apr 13, 2019 at 14:47
7
$\begingroup$

I hope to see a nicer proof which works for all $d$ or with the Euclidean distance which is surely of much more interest, but in the meantime, here's something ham-handed showing that the answer is no when $d=2$ and the distance makes $\mathbb{R}^2$ into an injective / hyperconvex metric space; the $\ell_1,\ell_\infty$ distances are examples.

The Vietoris-Rips complex at scale $\epsilon$ for a point set $X$ in $\mathbb{R}^d$ equipped with an injective metric coincides with the Čech complex for a set of balls of radius $\epsilon/2$ centered at the points of $X$. This is homotopy equivalent to the union of those balls, by the nerve lemma. That union of balls is a subspace of $\mathbb{R}^d$, so if we can show that such subspaces cannot have any higher homology, then we win. Unfortunately, there are counterexamples when $d\geq3$ due to Barratt and Milnor.

However, subspaces of $\mathbb{R}^2$ do not have $k$-homology for $k\geq 2$ by the results of Zastrow cited in this question. [Note that the topology induced on $\mathbb{R}^d$ is the same for any metric arising from a norm].

Most likely there are easier ways to show this for unions of $\epsilon/2$-balls in $\mathbb{R}^2$. For instance, if they are all homotopy equivalent to separable 1D metric spaces, then work of Curtis and Fort applies. Or, there could be something hands-on that I'm missing.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Ian Agol updated the link in his answer to a revised version of Zastrow's paper available here: mat.ug.edu.pl/~zastrow/Nnonano.htm $\endgroup$
    – j.c.
    Jun 14, 2018 at 17:45
  • 2
    $\begingroup$ About "The Vietoris-Rips complex at scale $\epsilon$ for a point set $X$ in $\mathbb{R}^d$ coincides with the Čech complex for a set of balls of radius $\epsilon/2$ centered at the points of $X$." This holds only for the points and edges of the two complexes in general. If the distance is $\ell_{\infty}$, the two complexes coincide. $\endgroup$
    – Luc Guyot
    Jun 14, 2018 at 19:26
  • $\begingroup$ @LucGuyot You're right of course. I will edit... $\endgroup$
    – j.c.
    Jun 14, 2018 at 19:39
  • $\begingroup$ Thanks for that insightful answer. I leave the answer unaccepted, though, to hope someone might have an idea about Euclidean distances or $d>2$. $\endgroup$
    – Arkadi
    Jun 18, 2018 at 8:28
  • 2
    $\begingroup$ Also note, that the example by Barratt and Milnor uses a countable wedge of spheres, whereas I tried to keep it simpler by considering only finite complexes. $\endgroup$
    – Arkadi
    Jun 18, 2018 at 8:40
1
$\begingroup$

Adamaszek and Adams have studied the Vietoris-Rips complexes of $S^1$ with different radii, and proved that the resulting Vietoris-Rips complex can be of arbitrary dimension. A number of examples with finite points are treated on the way, with the same result. See https://msp.org/pjm/2017/290-1/p01.xhtml as well as subsequent papers.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.