On Edge Collapse of Random Simplicial Complexes

Edge collapse, introduced in [Boissonnat, Pritam. SoCG 2020], is a process to reduce the size of a simplicial complex while preserving its homology. We study the effect of edge collapse on the Erdos-Renyi random clique complex and provide upper and lower bounds on the size of the resulting complex that hold asymptotically almost surely.

Our proof employs the notion of local weak convergence to establish the expected size of the bounds. For the concentration part, we identify the critical combinatorial structures that control the outcome of the edge collapse process. To this end, we give a new concentration inequality for typically Lipschitz functions on random graphs which improves on the bound of Warnke, 2016. We use the martingale method to prove the inequality.