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 Free Access

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?)

  • [1] Margaret M. Bayer and Louis J. Billera, Generalized Dehn-Sommerville relations for polytopes, spheres and Eulerian partially ordered sets, Invent. Math. 79 (1985), 143-157. MR 774533 (86f:52010b)
  • [2] Margaret M. Bayer and Andrew Klapper, A new index for polytopes, Discrete Comput. Geom. 6 (1991), 33-47. MR 1073071 (91k:52024)
  • [3] L. J. Billera and C. W. Lee, A proof of the sufficency of McMullen's conditions for $ f$-vectors of simplicial convex polytopes, J. Combin. Theory Ser. A 31 (1981), 237-255. MR 635368 (82m:52006)
  • [4] G. Birkhoff, Lattice theory, Amer. Math. Soc., Providence, R.I., 1967. MR 0227053 (37:2638)
  • [5] Anders Björner, Shellable and Cohen-Macaulay partially ordered sets, Trans. Amer. Math. Soc. 260 (1980), 159-183. MR 570784 (81i:06001)
  • [6] Anders Björner, Adriano Garcia, and Richard Stanley, An introduction to Cohen-Macaulay partially ordered sets, Ordered Sets (I. Rival, Ed.), Reidel, Dordrecht, 1982, pp. 583-615. MR 661307 (83i:06001)
  • [7] Anders Björner and Michelle Wachs, On lexicographically shellable posets, Trans. Amer. Math. Soc. 277 (1983), 323-341. MR 690055 (84f:06004)
  • [8] Arne Brøndsted, An introduction to convex polytopes, Graduate Texts in Math., vol. 90, Springer-Verlag, 1983. MR 683612 (84d:52009)
  • [9] H. Bruggesser and P. Mani, Shellable decompositions of cells and spheres, Math. Scand. 29 (1971), 197-205. MR 0328944 (48:7286)
  • [10] H. S. M. Coxeter, Regular polytopes, Dover, New York, 1971. MR 0370327 (51:6554)
  • [11] D. Foata and M.-P. Schützenberger, Nombres d'Euler et permutations alternantes, Tech. report, Univ. of Florida, Gainesville, 1971.
  • [12] -, Nombres d'Euler et permutations alternantes, A Survey of Combinatorial Theory (J. N. Srivastava et al., Eds.), North-Holland, Amsterdam, 1973.
  • [13] Branko Grünbaum, Convex polytopes, Pure and Appl. Math., vol. 16, Wiley, 1967. MR 0226496 (37:2085)
  • [14] P. McMullen, G. C. Shephard, et al., Convex polytopes and the upper bound conjecture, London Math. Soc. Lecture Notes Ser., vol. 3, Cambridge Univ. Press, 1971. MR 0301635 (46:791)
  • [15] N. Metropolis and Gian-Carlo Rota, Combinatorial structure of the faces of the $ n$-cube, SIAM J. Appl. Math. 35 (1978), 689-694. MR 512178 (80c:06015)
  • [16] Joseph S. Oliveira, The theory of cubic lattices, Ph.D. thesis, Massachusetts Institute of Technology, February 1993.
  • [17] Mark R. Purtill, André permutations, lexicographic shellability and the $ cd$-index of a convex polytope, Ph.D. thesis, Massachusetts Institute of Technology, April 1990.
  • [18] Daniel Shanks, Generalized Euler and class numbers, Math. Comp. 21 (1967), 689-694. MR 0223295 (36:6343)
  • [19] Richard P. Stanley, The number of faces of simplicial polytopes and spheres, Ann. N. Y. Acad. Sci. 440 (1985), 212-223. MR 809209 (87a:52007)
  • [20] -, Enumerative combinatorics, vol. I, Wadsworth & Brooks/Cole Advanced Books and Software, Monterey, Calif., 1986. MR 847717 (87j:05003)

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