The Möbius function of a composition poset
Bruce E. Sagan1
and Vincent Vatter2
1Michigan State University Department of Mathematics East Lansing MI USA 48824-1027
2University of St Andrews School of Mathematics and Statistics St Andrews Fife Scotland KY16 9SS
2University of St Andrews School of Mathematics and Statistics St Andrews Fife Scotland KY16 9SS
DOI: 10.1007/s10801-006-0017-4
Abstract
We determine the Möbius function of a poset of compositions of an integer. In fact, we give two proofs of this formula, one using an involution and one involving discrete Morse theory. This composition poset turns out to be intimately connected with subword order, whose Möbius function was determined by Björner. We show that, using a generalization of subword order, we can obtain both Björner's results and our own as special cases.
Pages: 117–136
Keywords: keywords composition; discrete Morse function; Möbius function; permutation pattern; subword order
Full Text: PDF
References
1. E. Babson and P. Hersh, “Discrete Morse functions from lexicographic orders,” Trans. Amer. Math. Soc. 357(2) (2005), 509-534 (electronic).
2. F. Bergeron, M., Bousquet-Mélou, and S. Dulucq, “Standard paths in the composition poset,” Ann. Sci. Math. Québec 19(2) (1995), 139-151.
3. A. Bj\ddot orner, “Shellable and Cohen-Macaulay partially ordered sets,” Trans. Amer. Math. Soc. 260(1) (1980), 159-183.
4. A. Bj\ddot orner, “The M\ddot obius function of subword order,” in Invariant Theory and Tableaux (Minneapolis, MN, 1988), vol. 19 of IMA Vol. Math. Appl. Springer, New York, 1990, pp. 118-124.
5. A. Bj\ddot orner, “The M\ddot obius function of factor order,” Theoret. Comput. Sci. 117(1-2) (1993), 91-98.
6. A. Bj\ddot orner and C. Reutenauer, “Rationality of the M\ddot obius function of subword order,” Theoret. Comput. Sci. 98(1) (1992), 53-63.
7. A. Bj\ddot orner and B.E. Sagan, “Rationality of the M\ddot obius function of the composition poset,” Theoret. Comput. Sci., to appear.
8. A. Bj\ddot orner and R.P. Stanley, “An analogue of Young's lattice for compositions,” arXiv:math. CO/0508043.
9. A. Bj\ddot orner and M. Wachs, “Bruhat order of Coxeter groups and shellability,” Adv. in Math. 43(1) (1982), 87-100.
10. M. Bóna, Combinatorics of Permutations, Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton, FL, 2004.
11. T. Chow and J. West, “Forbidden subsequences and Chebyshev polynomials,” Discrete Math. 204(1-3) (1999), 119-128.
12. R. Ehrenborg and M. Readdy, “The Tchebyshev transforms of the first and second kinds,” arXiv:math.CO/0412124.
13. F.D. Farmer, “Cellular homology for posets,” Math. Japon. 23(6) (1978/79), 607-613.
14. R. Forman, “A discrete Morse theory for cell complexes,” in Geometry, Topology, & Physics, Conf. Proc. Lecture Notes Geom. Topology, IV. Internat. Press, Cambridge, MA, 1995, pp. 112-125.
15. R. Forman, “Morse theory for cell complexes,” Adv. Math. 134(1) (1998), 90-145.
16. P. Hersh, “On optimizing discrete Morse functions,” Advances in Appl. Math. 35 (2005), 294-322.
17. G. Hetyei, “Tchebyshev posets,” Discrete Comput. Geom. 32(4) (2004), 493-520.
18. J.B. Kruskal, “The theory of well-quasi-ordering: A frequently discovered concept,” J. Combinatorial Theory Ser. A 13 (1972), 297-305.
19. T. Mansour and A. Vainshtein, “Restricted permutations, continued fractions, and Chebyshev polynomials,” Electron. J. Combin. 7 (2000), Research Paper 17, 9 pp. (electronic).
20. G.-C. Rota, “On the foundations of combinatorial theory. I. Theory of M\ddot obius functions,” Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964), 340-368.
21. J. Snellman, “Saturated chains in composition posets,” arXiv:math.CO/0505262.
22. J. Snellman, “Standard paths in another composition poset,” Electron. J. Combin. 11(1) (2004), Research Paper 76, 8 pp. (electronic).
23. R.P. Stanley, Enumerative Combinatorics, Vol. 1, vol. 49 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1997.
24. G. Viennot, “Maximal chains of subwords and up-down sequences of permutations,” J. Combin. Theory Ser. A 34(1) (1983), 1-14.
25. T.M. Wang and X.R. Ma, “A generalization of the Cohen-Macaulay property of the M\ddot obius function of a word poset,” Acta Math. Appl. Sinica 20(3) (1997), 431-437.
26. I. Warnke, “The M\ddot obius-function of subword orders,” Rostock. Math. Kolloq . 46 (1993), 25-31.
27. H.S. Wilf, “The patterns of permutations,” Discrete Math. 257(2-3) (2002), 575-583.
2. F. Bergeron, M., Bousquet-Mélou, and S. Dulucq, “Standard paths in the composition poset,” Ann. Sci. Math. Québec 19(2) (1995), 139-151.
3. A. Bj\ddot orner, “Shellable and Cohen-Macaulay partially ordered sets,” Trans. Amer. Math. Soc. 260(1) (1980), 159-183.
4. A. Bj\ddot orner, “The M\ddot obius function of subword order,” in Invariant Theory and Tableaux (Minneapolis, MN, 1988), vol. 19 of IMA Vol. Math. Appl. Springer, New York, 1990, pp. 118-124.
5. A. Bj\ddot orner, “The M\ddot obius function of factor order,” Theoret. Comput. Sci. 117(1-2) (1993), 91-98.
6. A. Bj\ddot orner and C. Reutenauer, “Rationality of the M\ddot obius function of subword order,” Theoret. Comput. Sci. 98(1) (1992), 53-63.
7. A. Bj\ddot orner and B.E. Sagan, “Rationality of the M\ddot obius function of the composition poset,” Theoret. Comput. Sci., to appear.
8. A. Bj\ddot orner and R.P. Stanley, “An analogue of Young's lattice for compositions,” arXiv:math. CO/0508043.
9. A. Bj\ddot orner and M. Wachs, “Bruhat order of Coxeter groups and shellability,” Adv. in Math. 43(1) (1982), 87-100.
10. M. Bóna, Combinatorics of Permutations, Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton, FL, 2004.
11. T. Chow and J. West, “Forbidden subsequences and Chebyshev polynomials,” Discrete Math. 204(1-3) (1999), 119-128.
12. R. Ehrenborg and M. Readdy, “The Tchebyshev transforms of the first and second kinds,” arXiv:math.CO/0412124.
13. F.D. Farmer, “Cellular homology for posets,” Math. Japon. 23(6) (1978/79), 607-613.
14. R. Forman, “A discrete Morse theory for cell complexes,” in Geometry, Topology, & Physics, Conf. Proc. Lecture Notes Geom. Topology, IV. Internat. Press, Cambridge, MA, 1995, pp. 112-125.
15. R. Forman, “Morse theory for cell complexes,” Adv. Math. 134(1) (1998), 90-145.
16. P. Hersh, “On optimizing discrete Morse functions,” Advances in Appl. Math. 35 (2005), 294-322.
17. G. Hetyei, “Tchebyshev posets,” Discrete Comput. Geom. 32(4) (2004), 493-520.
18. J.B. Kruskal, “The theory of well-quasi-ordering: A frequently discovered concept,” J. Combinatorial Theory Ser. A 13 (1972), 297-305.
19. T. Mansour and A. Vainshtein, “Restricted permutations, continued fractions, and Chebyshev polynomials,” Electron. J. Combin. 7 (2000), Research Paper 17, 9 pp. (electronic).
20. G.-C. Rota, “On the foundations of combinatorial theory. I. Theory of M\ddot obius functions,” Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964), 340-368.
21. J. Snellman, “Saturated chains in composition posets,” arXiv:math.CO/0505262.
22. J. Snellman, “Standard paths in another composition poset,” Electron. J. Combin. 11(1) (2004), Research Paper 76, 8 pp. (electronic).
23. R.P. Stanley, Enumerative Combinatorics, Vol. 1, vol. 49 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1997.
24. G. Viennot, “Maximal chains of subwords and up-down sequences of permutations,” J. Combin. Theory Ser. A 34(1) (1983), 1-14.
25. T.M. Wang and X.R. Ma, “A generalization of the Cohen-Macaulay property of the M\ddot obius function of a word poset,” Acta Math. Appl. Sinica 20(3) (1997), 431-437.
26. I. Warnke, “The M\ddot obius-function of subword orders,” Rostock. Math. Kolloq . 46 (1993), 25-31.
27. H.S. Wilf, “The patterns of permutations,” Discrete Math. 257(2-3) (2002), 575-583.