JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 12, No 1 (2000)

Louis J. Billera and Niandong Liu

We define a noncommutative algebra of flag-enumeration functionals on graded posets and show it to be isomorphic to the free associative algebra on countably many generators. Restricted to Eulerian posets, this ring has a particularly appealing presentation with kernel generated by Euler relations. A consequence is that even on Eulerian posets, the algebra is free, with generators corresponding to odd jumps in flags. In this context, the coefficients of the cd-index provide a graded basis.

1. R. Adin, “A new cubical h-vector,” Discrete Math. 157 (1996), 3-14.
2. M.M. Bayer and L.J. Billera, “Counting faces and chains in polytopes and posets,” Combinatorics and Algebra, C. Greene (Ed.), Amer. Math. Soc., Providence,
1984. Contemporary Mathematics, Vol. 34.
3. M.M. Bayer and L.J. Billera, “Generalized Dehn-Sommerville relations for polytopes, spheres and Eulerian partially ordered sets,” Inventiones Math. 79 (1985), 143-157.
4. M.M. Bayer and R. Ehrenborg, “The toric h-vector of partially ordered sets,” Trans. Amer. Math. Soc., to appear.
5. M.M. Bayer and G. Hetyei, “Flag vectors of Eulerian partially ordered sets,” Europ. J. Combinatorics, to appear.
6. M.M. Bayer and A. Klapper, “A new index for polytopes,” Discrete Comput. Geometry 6 (1991), 33-47.
7. N. Bergeron, S. Mykytiuk, F. Sottile, and S. Van Willigenburg, “Non-commutative Pieri operators on posets,” J. Comb. Theory Ser. A 91 (2000).
8. L.J. Billera and A. Bj\ddot orner, “Face numbers of polytopes and complexes,” in Handbook of Discrete and Computational Geometry, J.E. Goodman and J. O'Rourke (Eds.), CRC Press, Boca Raton and New York, 1997.
9. L.J. Billera and R. Ehrenborg, “Monotonicity of the cd-index for polytopes,” Math. Z. 233(2000), 421-441.
10. L.J. Billera, R. Ehrenborg, and M. Readdy, “The c-2d-index of oriented matroids,” J. Comb. Theory Ser. A 80 (1997), 79-105.
11. L.J. Billera and G. Hetyei, “Linear inequalities for flags in graded posets,” J. Comb. Theory Ser. A 89 (2000), 77-104.
12. R. Ehrenborg and M. Readdy, “Coproducts and the cd-index,” J. Alg. Combin. 8 (1998), 273-299.
13. B. Gr\ddot unbaum, Convex Polytopes, John Wiley and Sons, London, 1967.
14. G. Kalai, “A new basis of polytopes,” J. Comb. Theory Ser. A 49 (1988), 191-208.
15. N. Liu, Algebraic and Combinatorial Methods for Face Enumeration in Polytopes, Ph.D. Thesis, Cornell University, Ithaca, NY, May 1995.
16. G. Meisinger, Flag Numbers and Quotients of Convex Polytopes, Dissertation, Universit\ddot at Passau, 1993.
17. S. Montgomery, Hopf Algebras and Their Actions on Rings, American Mathematical Society, Providence, RI,
1993. CBMS Regional Conference Series in Mathematics, Vol. 82.
18. R. Stanley, “Balanced Cohen-Macaulay complexes,” Trans. Amer. Math. Soc. 249 (1979), 139-157.
19. R. Stanley, Enumerative Combinatorics, Vol. 1, The Wadsworth & Brooks/Cole Mathematics Series, Monterey, California, 1986.
20. R. Stanley, “Generalized h-vectors, intersection cohomology of toric varieties, and related results,” Adv. Stud. Pure Math. 11 (1987), 187-213.
21. R. Stanley, “Flag f -vectors and the cd-index,” Math. Z. 216 (1994), 483-499.
22. J. Stembridge, “Enriched P-partitions,” Trans. Amer. Math. Soc. 349 (1997), 763-788.
23. M. Sweedler, Hopf Algebras, Benjamin, New York, 1969.
24. V.A. Ufnarovskij, “Combinatorial and asymptotic methods of algebra,” in Algebra VI, A.I. Kostrikin and I.R. Shafarevich (Eds.), Encyclopaedia of Mathematical Sciences, Vol. 57, Springer, Berlin, New York, 1995.