The Möbius function of a composition poset
With Bruce Sagan.
Journal of Algebraic Combinatorics, 24 (2006), 117—136.
We determine the Möbius function of the 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. The composition poset turns out to be intimately connected with subword order, whose Möbius function was determined by Anders 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.
Download the paper:
- download from the journal website (subscription required)
- ps
- source: tex and bbl
Related links:
- Masaya Tomie established one of our conjectures in her paper A generalization of Chebyshev polynomials and nonrooted posets.
- Anders Björner and Bruce Sagan rederived this Möbius function using formal power series in noncommuting variables in their paper Rationality of the Möbius function of a composition poset, Theoretical Computer Science 359 (2006), 282–298.
- Slides (pdf) for a talk Bruce gave about this work at FPSAC 2006, and slides (pdf) for an earlier talk Bruce gave at the Third International Conference on Permutation Patterns (another link, and yet another).