Theoretical Computer Science Vol.235-2 (2000), 225-237.

Constructible complexes and recursive division of posets

by Masahiro Hachimori


Shellability has been extensively studied by many researchers since McMullen solved the Upper Bound Theorem for convex polytopes. There are also some important notions weaker than shellability, and in this paper we treat constructibility among these and define a notion of recursively dividable posets which corresponds to the notion of constructible complexes when seeing their face posets. Also we define a notion of strongly constructible complexes and, correspondingly, strongly dividable posets by strengthening the conditions, and prove that strongly dividable posets are signable. This result means that strongly constructible simplicial complexes are partitionable.