Strong Collapse of Random Simplicial Complexes
share
The strong collapse of a simplicial complex, proposed by Barmak and Minian (Disc. Comp. Geom. 2012), is a combinatorial collapse of a complex onto its sub-complex. Recently, it has received attention from computational topology researchers, owing to its empirically observed usefulness in simplification and size-reduction of the size of simplicial complexes while preserving the homotopy class. We consider the strong collapse process on random simplicial complexes. For the Erdős-Rényi random clique complex X(n,c/n) on n vertices with edge probability c/n with c>1, we show that after any maximal sequence of strong collapses the remaining subcomplex, or core must have (1-γ)(1-cγ) n+o(n) vertices asymptotically almost surely (a.a.s.), where γ is the least non-negative fixed point of the function f(x) = exp(-c(1-x)) in the range (0,1). These are the first theoretical results proved for strong collapses on random (or non-random) simplicial complexes.
READ FULL TEXT