<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
The Tchebyshev Transforms of the First and Second Kind
Richard Ehrenborg and Margaret Readdy
Department of Mathematics, University of Kentucky, Lexington, KY 40506, USA
{jrge, readdy}@ms.uky.edu
Annals of Combinatorics 14 (2) pp.211-244 Summer, 2010
AMS Subject Classification: 16W30, 06A11, 06A07, 05E99
An in-depth study of the Tchebyshev transforms of the first and second kind of a poset is taken. The Tchebyshev transform of the first kind is shown to preserve desirable combinatorial properties, including EL-shellability and nonnegativity of the cd-index. When restricted to Eulerian posets, it corresponds to the Billera, Ehrenborg, and Readdy omega map of oriented matroids. The Tchebyshev transform of the second kind U is a Hopf algebra endomorphism on the space of quasisymmetric functions which, when restricted to Eulerian posets, coincides with Stembridge's peak enumerator. The complete spectrum of U is determined, generalizing the work of Billera, Hsiao, and van Willigenburg. The type B quasisymmetric function of a poset is introduced and, like Ehrenborg's classical quasisymmetric function of a poset, it is a comodule morphism with respect to the quasisymmetric functions QSym. Finally, similarities among the omega map, Ehrenborg's r-signed Birkhoff transform, and the Tchebyshev transforms motivate a general study of chain maps which occur naturally in the setting of combinatorial Hopf algebras.
Keywords: poset transforms, Eulerian posets, cd-index, quasisymmetric functions, Hopf algebra


1. Aguiar, M., Bergeron, N., Sottile, F.: Combinatorial Hopf algebras and generalized Dehn- Sommerville relations. Compos. Math. 142, 1––30 (2006)

2. Aguiar, M., Hsiao, S.: Canonical characters on quasi-symmetric functions and bivariate Catalan numbers. Electron. J. Combin. 11, #R15 (2005)

3. Bayer, M., Billera, L.: Generalized Dehn-Sommerville relations for polytopes, spheres and Eulerian partially ordered sets. Invent. Math. 79, 143––157 (1985)

4. Bayer, M., Klapper, A.: A new index for polytopes. Discrete Comput. Geom. 6, 33––47 (1991)

5. Bayer, M., Sturmfels, B.: Lawrence polytopes. Canad. J. Math. 42, 62––79 (1990)

6. Billera, L.J., Ehrenborg, R.: Monotonicity of the cd-index for polytopes. Math. Z. 233, 421––441 (2000)

7. Billera, L.J., Ehrenborg, R., Readdy, M.: The c-2d-index of oriented matroids. J. Combin. Theory Ser. A 80, 79––105 (1997)

8. Billera, L.J., Ehrenborg, R., Readdy, M.: Flag f -vectors of geometric lattices. preprint (1996)

9. Billera, L.J., Hsiao, S.K., vanWilligenburg, S.: Peak quasisymmetric functions and Eulerian enumeration. Adv. Math. 176, 248––276 (2003)

10. Björner, A.: Shellable and Cohen-Macaulay partially ordered sets. Trans. Amer. Math. Soc. 260, 159––183 (1980)

11. Björner, A., Las Vergnas, M., Sturmfels, B., White, N., Ziegler G.: Oriented Matroids. Cambridge University Press, Cambridge (1993)

12. Björner, A., Wachs, M.: On lexicographically shellable posets. Trans. Amer. Math. Soc. 277, 323––341 (1983)

13. Chow, C.-O., Noncommutative Symmetric Functions of type B. PhD Thesis, MIT (2001)

14. Ehrenborg, R.: On posets and Hopf algebras. Adv. Math. 119, 1––25 (1996)

15. Ehrenborg, R.: Lifting inequalities for polytopes. Adv. Math. 193, 205––222 (2005)

16. Ehrenborg, R.: The r-signed Birkhoff transform. (2004)

17. Ehrenborg, R.: Inequalities for zonotopes. In: Goodman, J.E., Pach, J., Welzl, E. (eds.) Mathematical Sciences Research Institute Publication on Combinatorial and Computational Geometry, pp. 277––286. Cambridge University Press, Cambridge (2005)

18. Ehrenborg, R., Fox, H.: Inequalities for cd-indices of joins and products of polytopes. Combinatorica 23, 427––452 (2003)

19. Ehrenborg, R., Johnston, D., Rajagopalan, R., Readdy, M.: Cutting polytopes and flag f -vectors. Discrete Comput. Geom. 23, 261––271 (2000)

20. Ehrenborg, R., Karu, K.: Decomposition theorem for the cd-index of Gorenstein* posets. J. Algebraic Combin. 26, 225––251 (2007)

21. Ehrenborg, R., Readdy, M.: Coproducts and the cd-index. J. Algebraic Combin. 8, 273––299 (1998)

22. Hetyei, G.: Tchebyshev posets. Discrete Comput. Geom. 32, 493––520 (2004)

23. Hetyei, G.: Matrices of formal power series associated to binomial posets. J. Algebraic Combin. 22, 65––104 (2005)

24. Hsiao, S.K.: A signed analog of the Birkhoff transform. J. Combin. Theory Ser. A 113, 251––272 (2006)

25. Stanley, R.P.: Enumerative Combinatorics, Vol. I.Wadsworth and Brooks/Cole, Monterey (1986)

26. Stanley, R.P.: A survey of Eulerian posets. In: Bisztriczky, T., McMullen, P., Schneider, R., Weiss, A.I. (eds.) Polytopes: Abstract, Convex, and Computational, pp. 301––333 Kluwer Academic Publishers, Dordrecht (1994)

27. Stanley, R.P.: Flag-symmetric and locally rank-symmetric partially ordered sets. Electron. J. Combin. 3(2), #R6 (1996)

28. Stanley, R.P.: Combinatorics and Commutative Algebra, 2nd Ed. Birkhäuser Boston, Inc., Boston (1996)

29. Stembridge, J.: Enriched P-partitions. Trans. Amer. Math. Soc. 349, 763––788 (1997)

30. Sweedler, M.: Hopf Algebras. W. A. Benjamin, Inc., New York (1969)

31. Zaslavsky, T.: Facing up to arrangements: face count formulas for partitions of space by hyperplanes. Mem. Amer. Math. Soc. 154, vii+102 pp (1975)