On the contractibility of random Vietoris-Rips complexes

DOI10.1007/S00454-022-00378-9MaRDI QIDQ6045788zbMATH OpenOpenAlexFDO

Authors Tobias Müller, Matěj Stehlík

Publication date 12 May 2023

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.05120

zbMATH Keywords

contractibilityrandom simplicial complexVietoris-Rips complex

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial aspects of simplicial complexes (05E45) Simplicial sets and complexes in algebraic topology (55U10) Probability measures on topological spaces (60B05)

Abstract: We show that the Vietoris-Rips complex $mathcalR(n,r)$ built over $n$ points sampled at random from a uniformly positive probability measure on a convex body $Ksubseteqmathbb{R}^d$ is a.a.s. contractible when $rgeqcleft(fraclnnnight{)}^{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 $mathcalR(n,r)$ is a.a.s. homotopy equivalent to $K$ when $c_{1}left(fraclnnnight{)}^{1/d}leqrleq{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.

Recommendations

• Random geometric complexes
• Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes
• The Vietoris-Rips complexes of a circle
• Testing contractibility in planar rips complexes
• Vietoris-Rips complexes also provide topologically correct reconstructions of sampled shapes

Cites work

• A game of cops and robbers
• A topological view of unsupervised learning from noisy data
• Chasing robbers on random geometric graphs-an alternative approach
• Combinatorial algebraic topology
• Cops and robbers on geometric graphs
• Crackle: the homology of noise
• Elementary Differential Topology. (AM-54)
• Finding the homology of submanifolds with high confidence from random samples
• Hamilton cycles in random geometric graphs
• Homological connectivity of random 2-complexes
• Homological connectivity of random k -dimensional complexes
• scientific article; zbMATH DE number 3539473 (Why is no real title available?)
• scientific article; zbMATH DE number 1340281 (Why is no real title available?)
• scientific article; zbMATH DE number 863503 (Why is no real title available?)
• Random geometric complexes
• Random Čech complexes on Riemannian manifolds
• Sharp vanishing thresholds for cohomology of random flag complexes
• The longest edge of the random minimal spanning tree
• Thresholds for vanishing of `isolated' faces in random Čech and Vietoris-Rips complexes
• Topological consistency via kernel estimation
• Topology of random clique complexes
• Topology of random geometric complexes: a survey

Cited in

(3)

• Random cyclic dynamical systems
• Testing contractibility in planar rips complexes
• Universality in random persistent homology and scale-invariant functionals

This page was built for publication: On the contractibility of random Vietoris-Rips complexes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6045788)