JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 8, No 3 (1998)

Richard Ehrenborg and Margaret Readdy

The linear span of isomorphism classes of posets, P, has a Newtonian coalgebra structure. We observe that the ab-index is a Newtonian coalgebra map from the vector space P to the algebra of polynomials in the noncommutative variables a and b. This enables us to obtain explicit formulas showing how the cd-index of the face lattice of a convex polytope changes when taking the pyramid and the prism of the polytope and the corresponding operations on posets. As a corollary, we have new recursion formulas for the cd-index of the Boolean algebra and the cubical lattice. Moreover, these operations also have interpretations for certain classes of permutations, including simsun and signed simsun permutations. We prove an identity for the shelling components of the simplex. Lastly, we show how to compute the ab-index of the Cartesian product of two posets given the ab-indexes of each poset.

1. M. Bayer and L. Billera, “Generalized Dehn-Sommerville relations for polytopes, spheres and Eulerian partially ordered sets,” Invent. Math. 79 (1985), 143-157.
2. M. Bayer and A. Klapper, “A new index for polytopes,” Discrete Comput. Geom. 6 (1991), 33-47.
3. L. Billera and N. Liu, “Noncommutative enumeration in ranked posets,” in preparation.
4. A. Bj\ddot orner, “Shellable and Cohen-Macaulay partially ordered sets,” Trans. Amer. Math. Soc. 260 (1980), 159-183.
5. R. Ehrenborg, “On posets and Hopf algebras,” Adv. Math. 119 (1996), 1-25.
6. R. Ehrenborg and G. Hetyei, “Flags and shellings of Eulerian cubical posets,” preprint 1998.
7. R. Ehrenborg and G. Hetyei, “Newtonian coalgebras,” in preparation.
8. R. Ehrenborg and M. Readdy, “The r-cubical lattice and a generalization of the cd-index,” European J. Combin. 17 (1996), 709-725.
9. D. Foata and M.P. Sch\ddot utzenberger, “Nombres d'Euler et permutations alternantes,” Tech. Report, University of Florida, Gainesville, Florida, 1971.
10. D. Foata and M.P. Sch\ddot utzenberger, “Nombres d'Euler et permutations alternantes,” in A Survey of Combinatorial Theory, J.N. Srivastava et al. (Eds.), Amsterdam, North-Holland, 1973, pp. 173-187.
11. G. Hetyei, “On the cd-variation polynomials of André and simsun permutations,” Discrete Comput. Geom. 16 (1996), 259-275.
12. P.S. Hirschhorn and L.A. Raphael, “Coalgebraic foundation of the method of divided differences,” Adv. Math. 91 (1992), 75-135.
13. S.A. Joni and G.-C. Rota, “Coalgebras and bialgebras in combinatorics,” Stud. Appl. Math. 61 (1979), 93-139.
14. G. Kalai, “A new basis of polytopes,” J. Combin. Theory Ser. A 49 (1988), 191-209.
15. J.P.S. Kung (Ed.), “Gian-Carlo Rota on combinatorics,” Introductory Papers and Commentaries, Birkh\ddot auser, Boston, 1995.
16. N. Liu, “Algebraic and combinatorial methods for face enumeration in polytopes,” Doctoral dissertation, Cornell University, Ithaca, New York, 1995.
17. M. Purtill, “André permutations, lexicographic shellability and the cd-index of a convex polytope,” Trans. Amer. Math. Soc. 338 (1993), 77-104.
18. W.R. Schmitt, “Antipodes and incidence coalgebras,” J. Combin. Theory Ser. A 46 (1987), 264-290.
19. R.P. Stanley, Enumerative Combinatorics, Vol. I, Wadsworth and Brooks/Cole, Pacific Grove 1986.
20. R.P. Stanley, “Flag f -vectors and the cd-index,” Math. Z. 216 (1994), 483-499.
21. R.P. Stanley, “A survey of Eulerian posets,” in Polytopes: Abstract, Convex, and Computational, T. Bisztriczky, P. McMullen, R. Schneider, and A.I. Weiss (Eds.), NATO ASI Series C, Vol. 440, Kluwer Academic Publishers, 1994.
22. S. Sundaram, “The homology representation of the symmetric group on Cohen-Macaulay subposets of the partition lattice,” Adv. Math. 104 (1994), 225-296.
23. S. Sundaram, “The homology of partitions with an even number of blocks,” J. Alg. Combin. 4 (1995), 69-92.
24. M. Sweedler, Hopf Algebras, Benjamin, New York 1969.
25. M. Webster, personal communication.
26. G.M. Ziegler, “Lectures on polytopes,” Graduate Texts in Mathematics 152, Springer-Verlag, New York, 1995.