The threshold for d‐collapsibility in random complexes*. Issue 2 (27th March 2015) - Aronshtam, L.; Linial, N.
Abstract: In this paper we determine the threshold for d ‐collapsibility in the probabilistic model X d ( n, p ) of d ‐dimensional simplicial complexes. A lower bound for this threshold p = η d n was established in (Aronshtam and Linial, Random Struct. Algorithms 46 (2015) 26–35), and here we show that this is indeed the correct threshold. Namely, for every c > η d, a complex drawn from X d ( n, c n ) is asymptotically almost surely not d ‐collapsible. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 260–269, 2016