The threshold for collapsibility in random complexes

2013/07/10 by Lior Aronshtam, Aronshtam, Lior, Nati Linial +1
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Topological and Geometric Data Analysis #math.CO #math.PR

paper · pdf · doi:10.48550/arxiv.1307.2684

arxiv created 2013/07/10 · openalex publication_date 2013/07/10 · arxiv updated 2013/07/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we determine the threshold for collapsibility in the probabilistic model X_d(n,p) of d-dimensional simplicial complexes. A lower bound for this threshold p=(c_d)/(n) was established in \citeALLM. Here we show that this is indeed the correct threshold. Namely, for every c>c_d, a complex drawn from X_d(n,(c)/(n)) is asymptotically almost surely not collapsible.

Related

• Collapsibility of Random Clique Complexes
• Collapsibility and vanishing of top homology in random simplicial complexes
• d-collapsibility is NP-complete for d greater or equal to 4
• Recognition of collapsible complexes is NP-complete
• Random Simplicial Complexes