On the contractibility of random Vietoris-Rips complexes

Abstract

We show that the Vietoris-Rips complex $\mathcal{R}(n,r)$ built over $n$ points sampled at random from a uniformly positive probability measure on a convex body $K\subseteq {\mathbb{R}}^d$ is a.a.s. contractible when $r\ge c{\left(\frac{\ln n}{n}\right)}^{1/d}$ for a certain constant that depends on $K$ and the probability measure used. This answers a question of Kahle [Discrete Comput. Geom. 45 (2011), 553-573]. We also extend the proof to show that if $K$ is a compact, smooth $d$-manifold with boundary - but not necessarily convex - then $\mathcal{R}(n,r)$ is a.a.s. homotopy equivalent to $K$ when $c_1{\left(\frac{\ln n}{n}\right)}^{1/d}\le r\le c_2$ for constants $c_1=c_1(K),c_2=c_2(K)$. Our proofs expose a connection with the game of cops and robbers.

15 pages

References in corpus (2)

• Topological consistency via kernel estimation
• Random Čech Complexes on Manifolds with Boundary