André permutations, lexicographic shellability and the 𝑐𝑑-index of a convex polytope

Purtill, Mark

doi:10.1090/S0002-9947-1993-1094560-9

André permutations, lexicographic shellability and the $cd$-index of a convex polytope
HTML articles powered by AMS MathViewer

by Mark Purtill PDF

Trans. Amer. Math. Soc. 338 (1993), 77-104 Request permission

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

Margaret M. Bayer and Louis J. Billera, Counting faces and chains in polytopes and posets, Combinatorics and algebra (Boulder, Colo., 1983) Contemp. Math., vol. 34, Amer. Math. Soc., Providence, RI, 1984, pp. 207–252. MR 777703, DOI 10.1090/conm/034/777703
Margaret M. Bayer and Andrew Klapper, A new index for polytopes, Discrete Comput. Geom. 6 (1991), no. 1, 33–47. MR 1073071, DOI 10.1007/BF02574672
Louis J. Billera and Carl W. Lee, A proof of the sufficiency of McMullen’s conditions for $f$-vectors of simplicial convex polytopes, J. Combin. Theory Ser. A 31 (1981), no. 3, 237–255. MR 635368, DOI 10.1016/0097-3165(81)90058-3
Garrett Birkhoff, Lattice theory, 3rd ed., American Mathematical Society Colloquium Publications, Vol. XXV, American Mathematical Society, Providence, R.I., 1967. MR 0227053
Anders Björner, Shellable and Cohen-Macaulay partially ordered sets, Trans. Amer. Math. Soc. 260 (1980), no. 1, 159–183. MR 570784, DOI 10.1090/S0002-9947-1980-0570784-2
A. Björner, A. M. Garsia, and R. P. Stanley, An introduction to Cohen-Macaulay partially ordered sets, Ordered sets (Banff, Alta., 1981) NATO Adv. Study Inst. Ser. C: Math. Phys. Sci., vol. 83, Reidel, Dordrecht-Boston, Mass., 1982, pp. 583–615. MR 661307
Anders Björner and Michelle Wachs, On lexicographically shellable posets, Trans. Amer. Math. Soc. 277 (1983), no. 1, 323–341. MR 690055, DOI 10.1090/S0002-9947-1983-0690055-6
Arne Brøndsted, An introduction to convex polytopes, Graduate Texts in Mathematics, vol. 90, Springer-Verlag, New York-Berlin, 1983. MR 683612, DOI 10.1007/978-1-4612-1148-8
H. Bruggesser and P. Mani, Shellable decompositions of cells and spheres, Math. Scand. 29 (1971), 197–205 (1972). MR 328944, DOI 10.7146/math.scand.a-11045
H. S. M. Coxeter, Regular polytopes, 3rd ed., Dover Publications, Inc., New York, 1973. MR 0370327

Nombres d’Euler et permutations alternantes

Branko Grünbaum, Convex polytopes, Pure and Applied Mathematics, Vol. 16, Interscience Publishers John Wiley & Sons, Inc., New York, 1967. With the cooperation of Victor Klee, M. A. Perles and G. C. Shephard. MR 0226496
P. McMullen and G. C. Shephard, Convex polytopes and the upper bound conjecture, London Mathematical Society Lecture Note Series, vol. 3, Cambridge University Press, London-New York, 1971. Prepared in collaboration with J. E. Reeve and A. A. Ball. MR 0301635
N. Metropolis and Gian-Carlo Rota, Combinatorial structure of the faces of the $n$-cube, SIAM J. Appl. Math. 35 (1978), no. 4, 689–694. MR 512178, DOI 10.1137/0135057

The theory of cubic lattices

André permutations, lexicographic shellability and the

index of a convex polytope

Daniel Shanks, Generalized Euler and class numbers, Math. Comp. 21 (1967), 689–694. MR 223295, DOI 10.1090/S0025-5718-1967-0223295-5
Richard P. Stanley, The number of faces of simplicial polytopes and spheres, Discrete geometry and convexity (New York, 1982) Ann. New York Acad. Sci., vol. 440, New York Acad. Sci., New York, 1985, pp. 212–223. MR 809209, DOI 10.1111/j.1749-6632.1985.tb14556.x
Richard P. Stanley, Enumerative combinatorics. Vol. I, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1986. With a foreword by Gian-Carlo Rota. MR 847717, DOI 10.1007/978-1-4615-9763-6