2018/02/22 by Srikanth K. Iyer, Iyer, Srikanth K., D. Yogeshwaran +1 · 1 citation
Computer Science · Mathematics · #05C80 #05E45 #60B99 #60D05 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Probability (math.PR) #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1802.08224
openalex publication_date 2018/02/22 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
We study combinatorial connectivity for two models of random geometric complexes. These two models - Č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 rn. In the former, the k-simplices/faces are formed by subsets of (k+1) Poisson points such that the balls of radius rn 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 k ≥ 1), 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 Čech and Vietoris-Rips complexes asymptically as n → ∞. 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 rn = Θ(((log n)/(n))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 Č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., log n scale) but differs in the log log n scale for the Čech complex with k = 1 in the up-connected case.