The threshold for d‐collapsibility in random complexes*. Issue 2 (27th March 2015)

• Record Type: Journal Article
• Authors: Aronshtam, L.; Linial, N.
• Is Part Of: Random structures & algorithms. Volume 48:Issue 2(2016)
• Page Start: 260
• Page End: 269
• Publication Date: 2015-03-27
• Subjects: topology -- combinatory -- simplicial complex -- collapsibility; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20585
• Languages: English
• ISSNs: 1042-9832

Abstract

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