Signable posets and partitionable simplicial complexes

The notion of apartitionable simplicial complex is extended to that of asignable partially ordered set. It is shown in a unified way that face lattices of shellable polytopal complexes, polyhedral cone fans, and oriented matroid polytopes, are all signable. Each of these classes, which are believed to be mutually incomparable, strictly contains the class of convex polytopes. A general sufficient condition, termedtotal signability, for a simplicial complex to satisfy McMullen's Upper Bound Theorem on the numbers of faces, is provided. The simplicial members of each of the three classes above are concluded to be partitionable and to satisfy the upper bound theorem. The computational complexity of face enumeration and of deciding partitionability is discussed. It is shown that under a suitable presentation, the face numbers of a signable simplicial complex can be efficiently computed. In particular, the face numbers of simplicial fans can be computed in polynomial time, extending the analogous statement for convex polytopes. The research of S. Onn was supported by the Alexander von Humboldt Stifnung, by the Fund for the Promotion of Research at the Technion, and by Technion VPR fund 192–198.