The Möbius function of generalized subword order

DOI10.1016/J.AIM.2012.01.019zbMATH Open1286.06006arXiv1107.5070OpenAlexW3022569470MaRDI QIDQ409623FDOQ409623

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

Publication date: 13 April 2012

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Morse theory for cell complexes
• Title not available (Why is that?)
• The patterns of permutations
• The theory of well-quasi-ordering: a frequently discovered concept
• A user's guide to discrete Morse theory
• Discrete Morse functions from lexicographic orders
• Discrete Morse theory and the consecutive pattern poset
• Title not available (Why is that?)
• The Möbius function of generalized factor order
• The Möbius function of a composition poset
• A generalization of the Chebyshev polynomials and nonrooted posets
• The Möbius function of the consecutive pattern poset
• Title not available (Why is that?)
• The Möbius function of separable and decomposable permutations
• The Möbius function of factor order
• The Möbius function of the permutation pattern poset

Cited In (14)

• Title not available (Why is that?)
• On the growth of the Möbius function of permutations
• The Möbius function of generalized subword order
• On the topology of the permutation pattern poset
• Pattern posets
• Rationality of the Möbius function of a composition poset
• The Möbius function of generalized factor order
• The Möbius function of a composition poset
• The Möbius function of factor order
• On the Möbius function and topology of general pattern posets
• Discrete Morse theory for weighted simplicial complexes
• Intervals of permutations with a fixed number of descents are shellable
• On the dimension of downsets of integer partitions and compositions
• Title not available (Why is that?)

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)