The worst way to collapse a simplex

DOI10.1007/S11856-021-2184-3MaRDI QIDQ2055286zbMATH OpenOpenAlexFDO

Publication date 1 December 2021

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.07329

collapsible complex contractible complex simplex simplicial complex

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Simple homotopy type, Whitehead torsion, Reidemeister-Franz torsion, etc. (57Q10)

Abstract: In general a contractible complex need not be collapsible. Moreover, there exist complexes which are collapsible but even so admit a collapsing sequence where one "gets stuck", that is one can choose the collapses in such a way that one arrives at a nontrivial complex which admits no collapsing moves. Here we examine this phenomenon in the case of a simplex. In particular we characterize all values of

n

and

d

so that the n-simplex may collapse to a d-complex from which no further collapses are possible. Equivalently and in the language of high-dimensional generalizations of trees, we construct hypertrees that are anticollapsible, but not collapsible. Furthermore we examine anticollapsibility in random simplicial complexes.

Review text

Let \(X\) be a simplicial complex. A nonempty face \(f\) of \(X\) is said to be a free face if \(f\) is a proper subset of exactly one other face of \(X\). An elementary collapse of \(X\) is the operation of removing a free face together with the unique face properly containing that free face. \(X\) is said to be a collapsible complex if there exists a sequence of elementary collapses (collapsing sequence) which reduces \(X\) to a single vertex. Furthermore, \(X\) is said to be a contractible complex if it is homotopy-equivalent to a single point. This paper deals with the case in which \(X\) is an \((n-1)\)-simplex. The main result states that if \(n \geqslant 8\) and \(d \notin \{ 1, n-3, n-2, n-1 \}\), then there exists a collapsing sequence which reduces the \((n-1)\)-simplex to a \(d\)-complex with \(n\) vertices but without free faces. Similar sufficient conditions are obtained for the nonexistence of such a sequence. As a corollary it is obtained that for each \(n \geqslant 8\), there exists a contractible \(d\)-complex with \(n\) vertices but without free faces whenever \(d \notin \{1, n- 3, n - 2, n-1 \}\). This result is best possible due to the following statement also established in the paper under review: If \(n \leqslant 7\) or \(d \in \{ 1, n - 3, n - 2, n-1 \}\), then every contractible \(d\)-complex with \(n\) vertices has a free face; in case \(n \leqslant 7\), this statement was established earlier by \textit{B. Bagchi} and \textit{B. Datta} [Discrete Math. 305, No. 1--3, 1--17 (2005; Zbl 1085.57019); corrigendum ibid. 338, No. 4, 569--570 (2015; Zbl 1304.57037)]. (The paper has a flaw which was corrected, after a decade since its publication, in a later paper by the same authors.) In the paper under review, contractibility is established by checking anticollapsibility. An anticollapsible complex is simple-homotopy equivalent to a simplex. Any simplex is collapsible to a vertex and thus is contractible.

Recommendations

Cites work

Cited in

(15)

Describes a project that uses

Uses Software

This page was built for publication: The worst way to collapse a simplex

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2055286)