Extremal Examples of Collapsible Complexes and Random Discrete Morse Theory
Extremal Examples of Collapsible Complexes and Random Discrete Morse Theory
复制标题
DOI：
10.1007/s00454-017-9860-4
复制
发表时间：
2014-04
影响因子：
0.8
通讯作者：
Karim A. Adiprasito;Bruno Benedetti;Frank H. Lutz
中科院分区：
文献类型：
--
作者：
Karim A. Adiprasito;Bruno Benedetti;Frank H. Lutz
我们提出了极值结构与单纯可扩展性的属性。(1)对于每一个，都有可折叠的（和可壳的）单纯-复合体，只有一个自由面。此外，还有只有两个自由面的非渐缩复合体（两个结果在所有维度上都是最佳的）。(2)最佳离散莫尔斯向量不必是唯一的。我们明确地构造了一个可收缩但不可折叠的三维单纯复形，它的面向量允许两个不同的最优离散莫尔斯向量（1，1，1，0）和（1，0，1，1）.事实上，我们表明，在每一个维度有收缩，不可塌陷的单纯形复合物，有和作为不同的最佳离散莫尔斯向量。(3)我们给出了一个（非PL）5-流形的第一个显式例子，面向量为495912，383136，110880），它是可塌缩的，但不是同胚的球。此外，我们讨论了随机方法的可扩展性和离散莫尔斯理论可能的改进和缺点。我们将分别介绍Benedetti和Lutz的ex-first和lex-lastdiscrete莫尔斯策略的随机化版本random-lex-firstandrandom-lex-laststrategy（Exp Math 23（1）：66-94，2014），我们将看到在许多情况下，random-lex-laststrategy的效果明显优于Benedetti-Lutz的（均匀）随机策略。在理论方面，我们证明，经过反复的重心细分，离散的莫尔斯向量随机算法发现，平均而言，指数（在重心细分的数量）的临界细胞数量渐近几乎肯定。
We present extremal constructions connected with the property of simplicial collapsibility. (1) For each, there are collapsible (and shellable) simpliciald-complexes with only one free face. Also, there are non-evasived-complexes with only two free faces (both results are optimal in all dimensions). (2) Optimal discrete Morse vectors need not be unique. We explicitly construct a contractible, but non-collapsible 3-dimensional simplicial complex with face vectorthat admits two distinct optimal discrete Morse vectors, (1, 1, 1, 0) and (1, 0, 1, 1). Indeed, we show that in every dimensionthere are contractible, non-collapsible simpliciald-complexes that haveandas distinct optimal discrete Morse vectors. (3) We give a first explicit example of a (non-PL) 5-manifold, with face vector495912, 383136, 110880), that is collapsible but not homeomorphic to a ball. Furthermore, we discuss possible improvements and drawbacks of random approaches to collapsibility and discrete Morse theory. We will introduce randomized versionsrandom-lex-firstandrandom-lex-lastof thelex-firstandlex-lastdiscrete Morse strategies of Benedetti and Lutz (Exp Math 23(1):66–94, 2014), respectively—and we will see that in many instances therandom-lex-laststrategy works significantly better than Benedetti–Lutz’s (uniform)randomstrategy. On the theoretical side, we prove that after repeated barycentric subdivisions, the discrete Morse vectors found by randomized algorithms have, on average, an exponential (in the number of barycentric subdivisions) number of critical cells asymptotically almost surely.