The Möbius function of generalized subword order

DOI10.1016/J.AIM.2012.01.019MaRDI QIDQ409623zbMATH OpenOpenAlexFDO

Authors Peter R. W. McNamara, Bruce E. Sagan

Publication date 13 April 2012

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.5070

zbMATH Keywords

discrete Morse theoryChebyshev polynomialhomotopy typeposetminimal skipped intervalsubword orderMöbius function

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics of partially ordered sets (06A07)

Abstract: Let P be a poset and let P* be the set of all finite length words over P. Generalized subword order is the partial order on P* obtained by letting u leq w if and only if there is a subword u' of w having the same length as u such that each element of u is less than or equal to the corresponding element of u' in the partial order on P. Classical subword order arises when P is an antichain, while letting P be a chain gives an order on compositions. For any finite poset P, we give a simple formula for the Mobius function of P* in terms of the Mobius function of P. This permits us to rederive in a easy and uniform manner previous results of Bjorner, Sagan and Vatter, and Tomie. We are also able to determine the homotopy type of all intervals in P* for any finite P of rank at most 1.

Recommendations

• The Möbius function of generalized subword order
• scientific article; zbMATH DE number 468610
• scientific article; zbMATH DE number 1159344
• scientific article; zbMATH DE number 4158687
• The Möbius function of generalized factor order

Cites work

• scientific article; zbMATH DE number 4158687 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 1757341 (Why is no real title available?)
• scientific article; zbMATH DE number 970688 (Why is no real title available?)
• A generalization of the Chebyshev polynomials and nonrooted posets
• A user's guide to discrete Morse theory
• Discrete Morse functions from lexicographic orders
• Discrete Morse theory and the consecutive pattern poset
• Morse theory for cell complexes
• The Möbius function of a composition poset
• The Möbius function of factor order
• The Möbius function of generalized factor order
• The Möbius function of separable and decomposable permutations
• The Möbius function of the consecutive pattern poset
• The Möbius function of the permutation pattern poset
• The patterns of permutations
• The theory of well-quasi-ordering: a frequently discovered concept

Cited in

(14)

• The Möbius function of generalized factor order
• The Möbius function of a composition poset
• scientific article; zbMATH DE number 468610 (Why is no real title available?)
• The Möbius function of factor order
• Rationality of the Möbius function of a composition poset
• The Möbius function of generalized subword order
• scientific article; zbMATH DE number 4158687 (Why is no real title available?)
• Pattern posets
• On the topology of the permutation pattern poset
• Discrete Morse theory for weighted simplicial complexes
• Intervals of permutations with a fixed number of descents are shellable
• On the Möbius function and topology of general pattern posets
• On the growth of the Möbius function of permutations
• On the dimension of downsets of integer partitions and compositions

This page was built for publication: The Möbius function of generalized subword order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q409623)