Thresholds for vanishing of `isolated' faces in random Čech and Vietoris-Rips complexes

DOI10.1214/19-AIHP1020zbMATH Open1469.60057arXiv1802.08224OpenAlexW3037960583MaRDI QIDQ2227469FDOQ2227469

Authors: Srikanth K. Iyer, D. Yogeshwaran 

Publication date: 15 February 2021

Published in: Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Abstract: We study combinatorial connectivity for two models of random geometric complexes. These two models - v{C}ech and Vietoris-Rips complexes - are built on a homogeneous Poisson point process of intensity $n$ on a $d$-dimensional torus using balls of radius $r_n$. In the former, the $k$-simplices/faces are formed by subsets of $(k+1)$ Poisson points such that the balls of radius $r_n$ centred at these points have a mutual interesection and in the latter, we require only a pairwise intersection of the balls. Given a (simplicial) complex (i.e., a collection of $k$-simplices for all $kgeq1$), we can connect $k$-simplices via $(k+1)$-simplices (`up-connectivity') or via $(k-1)$-simplices (`down-connectivity). Our interest is to understand these two combinatorial notions of connectivity for the random v{C}ech and Vietoris-Rips complexes asymptically as $noinfty$. In particular, we analyse in detail the threshold radius for vanishing of isolated $k$-faces for up and down connectivity of both types of random geometric complexes. Though it is expected that the threshold radius $r_n=Theta((fraclognn{)}^{1/d})$ in coarse scale, our results give tighter bounds on the constants in the logarithmic scale as well as shed light on the possible second-order correction factors. Further, they also reveal interesting differences between the phase transition in the v{C}ech and Vietoris-Rips cases. The analysis is interesting due to the non-monotonicity of the number of isolated $k$-faces (as a function of the radius) and leads one to consider `monotonic' vanishing of isolated $k$-faces. The latter coincides with the vanishing threshold mentioned above at a coarse scale (i.e., $logn$ scale) but differs in the $loglogn$ scale for the v{C}ech complex with $k=1$ in the up-connected case.

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

Recommendations

• The threshold for \(d\)-collapsibility in random complexes
• Integer Programming and Combinatorial Optimization
• The complexity of the outer face in arrangements of random segments
• scientific article; zbMATH DE number 516161
• Threshold phenomena for high-dimensional random polytopes
• scientific article; zbMATH DE number 3864182
• On the vanishing of homology in random Čech complexes
• Minimal complexes of faces of a random Boolean function.
• Recurrence relationships for the mean number of faces and vertices for random convex hulls

zbMATH Keywords

phase transitionconnectivityrandom hypergraphsmaximal facesPoisson convergencerandom geometric complexes

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Geometric probability and stochastic geometry (60D05) Probability theory on algebraic and topological structures (60B99) Combinatorial aspects of simplicial complexes (05E45)

Cites Work

• Topology of random clique complexes
• Finding the homology of submanifolds with high confidence from random samples
• Computational topology. An introduction
• Random Geometric Graphs
• Random geometric complexes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Stochastic and Integral Geometry
• Homological connectivity of random k -dimensional complexes
• Random Plane Networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Homological connectivity of random 2-complexes
• Random coverings
• Sharp vanishing thresholds for cohomology of random flag complexes
• The longest edge of the random minimal spanning tree
• Topological pattern recognition for point cloud data
• Perspectives on \(A\)-homotopy theory and its applications
• Criticality of the exponential rate of decay for the largest nearest-neighbor link in random geometric graphs
• Topology of random simplicial complexes: a survey
• The connectivity of a graph on uniform points on [0,\,1]\(^{d}\).
• Clustering and percolation of point processes
• Inhomogeneous random graphs, isolated vertices, and Poisson approximation
• Simplicial complexes: spectrum, homology and random walks
• Spectra of combinatorial Laplace operators on simplicial complexes
• Normal approximation for coverage models over binomial point processes
• Topology of random geometric complexes: a survey
• Distance functions, critical points, and the topology of random Čech complexes
• The topology of probability distributions on manifolds
• Topics of Stochastic Algebraic Topology
• Random Čech complexes on Riemannian manifolds
• On the topology of random complexes built over stationary point processes
• A central limit theorem for exchangeable variates with geometric applications
• Clique percolation
• An Intermediate Course in Probability
• Nonuniform random geometric graphs with location-dependent radii
• Limit theorems for Betti numbers of extreme sample clouds with application to persistence barcodes
• Limit theorems for point processes under geometric constraints (and topological crackle)
• Random walks on simplicial complexes and harmonics
• Inside the critical window for cohomology of random \(k\)-complexes
• The critical point of \(k\)-clique percolation in the Erdős-Rényi graph
• Foundations of a connectivity theory for simplicial complexes
• On the vanishing of homology in random Čech complexes
• Minimum spanning acycle and lifetime of persistent homology in the Linial-Meshulam process
• Randomly weighted \(d\)-complexes: minimal spanning acycles and persistence diagrams

Cited In (6)

• On the contractibility of random Vietoris-Rips complexes
• Homological connectivity in random Čech complexes
• Phase transitions and noise sensitivity on the Poisson space via stopping sets and decision trees
• Poisson process approximation under stabilization and Palm coupling
• Random geometric complexes
• On the vanishing of homology in random Čech complexes

This page was built for publication: Thresholds for vanishing of `isolated' faces in random Čech and Vietoris-Rips complexes

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