2019/03/12 by Greg Malen, Malen, Greg · 1 citation
Computer Science · Mathematics · #Topological and Geometric Data Analysis #Geometric and Algebraic Topology #Homotopy and Cohomology in Algebraic Topology
paper · pdf · doi:10.48550/arxiv.1903.05055
We prove a sufficient condition for a finite clique complex to collapse to a k-dimensional complex, and use this to exhibit thresholds for (k+1)-collapsibility in a sparse random clique complex. In particular, if every strongly connected, pure (k+1)-dimensional subcomplex of a clique complex X has a vertex of degree at most 2k+1, then X is (k+1)-collapsible. In the random model X(n,p) of clique complexes of an Erdős--Rényi random graph G(n,p), we then show that for any fixed k≥ 0, if p=n-α for fixed 1/(k+1) < α< 1/k, then a clique complex X\oversetdist= X(n,p) is (k+1)-collapsible with high probability.