On Edge Collapse of Random Simplicial Complexes

Description

We consider the edge collapse (introduced in [Boissonnat, Pritam. SoCG 2020]) process on the Erdős-Rényi random clique complex X(n,c/√n) on n vertices with edge probability c/√n such that c > √η₂ where η₂ = inf{η | x = e^{-η(1-x)²} has a solution in (0,1)}. For a given c > √η₂, we show that after t iterations of maximal edge collapsing phases, the remaining subcomplex, or t-core, has at most (1+o(1))binom(n,2)p(1-(c²/3)(1-(1-γ_t)³)) and at least (1+o(1)) binom(n,2) p(1-γ_{t+1}-c²γ_t(1-γ_t)²) edges asymptotically almost surely (a.a.s.), where {γ_t}_{t ≥ 0} is recursively determined by γ_{t+1} = e^{-c²(1-γ_t)²} and γ_0 = 0. We also determine the upper and lower bound on the final core with explicit formulas. If c < √{η₂} then we show that the final core contains o(n√n) edges. On the other hand, if, instead of c being a constant with respect to n, c > √{2log n} then the edge collapse process is no more effective in reducing the size of the complex. Our proof is based on the notion of local weak convergence [Aldous, Steele. In Probability on discrete structures. Springer, 2004] together with two new components. Firstly, we identify the critical combinatorial structures that control the outcome of the edge collapse process. By controlling the expected number of these structures during the edge collapse process we establish a.a.s. bounds on the size of the core. We also give a new concentration inequality for typically Lipschitz functions on random graphs which improves on the bound of [Warnke. Combinatorics, Probability and Computing, 2016] and is, therefore, of independent interest. The proof of our lower bound is via the recursive technique of [Linial and Peled. A Journey Through Discrete Mathematics. 2017] to simulate cycles in infinite trees. These are the first theoretical results proved for edge collapses on random (or non-random) simplicial complexes.

Abstract

International audience

Additional details