On the Contractibility of Random Vietoris–Rips Complexes

We show that the Vietoris–Rips complex R(n, r) built over n points sampled at random from a uniformly positive probability measure on a convex body K⊆ R^d is a.a.s. contractible when r≥ c(ln n/ n) ^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(3), 553–573 (2011)). We also extend the proof to show that if K is a compact, smooth d-manifold with boundary—but not necessarily convex—then R(n, r) is a.a.s. homotopy equivalent to K when c₁(ln n/ n) ^1/d≤ r≤ c₂ for constants c₁= c₁(K) , c₂= c₂(K). Our proofs expose a connection with the game of cops and robbers.