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

Chebyshev polynomialdiscrete Morse theoryhomotopy typeminimal skipped intervalMöbius functionposetsubword order

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.

Review text

Given a finite poset \(P\), denote by \(P^*\) the set of all finite-length words on \(P\). The generalized subword order on \(P^*\) is defined by \(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 \(P\). Note that this coincides with the classical subword order when \(P\) is discrete (i.e. an antichain).NEWLINENEWLINEThe authors prove a simple formula for the Möbius function of \(P^*\) in terms of the Möbius function of \(P\). They also derive various applications of this result: they determine the homotopy type of all intervals of \(P^*\) for any finite poset \(P\) of rank at most \(1\) and obtain alternative proofs of previous results of Björner, Sagan and Vatter, and Tomie.

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

• 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
• 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?)
• 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

(15)

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

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)