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
    Commented 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
    Commented 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.
    Commented 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
    Commented 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
    Commented 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
    Commented 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.
    Commented 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
    Commented Jun 14, 2018 at 19:26
  • $\begingroup$ @LucGuyot You're right of course. I will edit... $\endgroup$
    – j.c.
    Commented 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
    Commented 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
    Commented 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$

You must log in to answer this question.

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