Signable posets and partitionable simplicial complexes (Q1913695)

The authors introduce the notion of a signable partially ordered set which extends the notion of a partitionable simplicial complex. Three classes of posets are shown to be signable: 1. Shellable posets, 2. polyhedral fans, 3. oriented matroid polytopes. In particular the simplicial members of these classes are partitionable. Each of these classes strictly contains the class of convex polytopes for which McMullen's Upper Bound Theorem on the number of faces holds. A condition called total signability is introduced for a simplicial complex and this implies McMullen's Upper Bound Theorem. This condition is shown to hold for the simplicial members of the three classes mentioned above. As the authors point out, the interest of this result is enhanced by the fact that the shellability question is still open for the class of polyhedral fans and oriented matroid polytopes. Finally the computational complexity of face enumeration is discussed, as well as the complexity of deciding shellability and partitionability. It is proved that the face number of polyhedral fans can be computed in polynomial time.