Back to Search
Start Over
The threshold for d-collapsibility in random complexes*
- Source :
- Random Structures & Algorithms. 48:260-269
- Publication Year :
- 2015
- Publisher :
- Wiley, 2015.
-
Abstract
- In this paper we determine the threshold for d-collapsibility in the probabilistic model Xdn,p of d-dimensional simplicial complexes. A lower bound for this threshold p=i¾?dn 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>i¾?d, a complex drawn from Xdn,cn is asymptotically almost surely not d-collapsible. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 260-269, 2016
- Subjects :
- Discrete mathematics
Applied Mathematics
General Mathematics
010102 general mathematics
Statistical model
0102 computer and information sciences
01 natural sciences
Computer Graphics and Computer-Aided Design
Upper and lower bounds
Combinatorics
Simplicial complex
010201 computation theory & mathematics
struct
Almost surely
0101 mathematics
Software
Topology (chemistry)
Mathematics
Subjects
Details
- ISSN :
- 10429832
- Volume :
- 48
- Database :
- OpenAIRE
- Journal :
- Random Structures & Algorithms
- Accession number :
- edsair.doi...........566e68f96c652c681aa60f138394c1e0