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

DOI10.1214/19-AIHP1020MaRDI QIDQ2227469zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1802.08224, https://projecteuclid.org/euclid.aihp/1593137312

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)

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.

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

Cites work

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

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)