Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



André permutations, lexicographic shellability and the $ cd$-index of a convex polytope

Author: Mark Purtill
Journal: Trans. Amer. Math. Soc. 338 (1993), 77-104
MSC: Primary 52B05; Secondary 05E15, 06A08
MathSciNet review: 1094560
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The $ cd$-index of a polytope was introduced by Fine; it is an integer valued noncommutative polynomial obtained from the flag-vector. A result of Bayer and Fine states that for any integer "flag-vector," the existence of the $ cd$-index is equivalent to the holding of the generalized Dehn-Sommerville equations of Bayer and Billera for the flag-vector. The coefficients of the $ cd$-index are conjectured to be nonnegative.

We show a connection between the $ cd$-index of a polytope $ \mathcal{P}$ and any $ CL$-shelling of the lattice of faces of $ \mathcal{P}$ ; this enables us to prove that each André polynomial of Foata and Schützenberger is the $ cd$-index of a simplex. The combinatorial interpretation of this $ cd$-index can be extended to cubes, simplicial polytopes, and some other classes (which implies that the $ cd$-index has nonnegative coefficients for these polytopes). In particular, we show that any polytope of dimension five or less has a positive $ cd$-index.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 52B05, 05E15, 06A08

Retrieve articles in all journals with MSC: 52B05, 05E15, 06A08

Additional Information

Keywords: André permutations, lexicographic shellability, $ cd$-index, convex polytopes, Eulerian lattices
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society