Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. The Möbius function ...
Conference paper

The Möbius function of generalized subword order

Peter R. W. Mcnamara, Bruce E. Sagan (1)
(1) Department of Mathematics [Lansing]
Download article
Open on HAL
Imported on
January 31, 2017
Published on
December 31, 2011
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
Proceedings
DOI
10.46298/dmtcs.3016
License
https://about.hal.science/hal-authorisation-v1
Indicators
624
Views
612
Downloads

The Möbius function of generalized subword order

Peter R. W. Mcnamara, Bruce E. Sagan (1)
(1) Department of Mathematics [Lansing]
Abstract
English
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≤ 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 Möbius function of $P^*$ in terms of the Möbius function of $P$. This permits us to rederive in an easy and uniform manner previous results of Björner, 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.
French
Soit $P$ un ensemble partiellement ordonné et soit $P^*$ l'ensemble des mots de longueur finie sur $P$. On définit l'ordre des sous-mots généralisé comme l'ordre partiel sur $P^*$ obtenu en posant $u≤ w$ s'il existe un sous-mot $u'$ de $w$ ayant la même longueur que $u$, tel que chaque élément de $u$ soit plus petit ou égal à l'élément correspondant de $u'$ dans l'ordre partiel sur $P$. L'ordre des sous-mots classique correspond au cas où $P$ est une antichaîne ; tandis que si P est une chaîne, on obtient un ordre sur les compositions. Pour tout ensemble partiellement ordonné fini $P$, nous donnons une formule simple pour la fonction de Möbius de $P^*$ en fonction de celle de $P$. Cela nous permet de retrouver de manière simple et uniforme des résultats de Björner, Sagan et Vatter, et de Tomie. Nous sommes aussi en mesure de déterminer le type d'homotopie de tous les intervalles de $P^*$ pour n'importe quel $P$ fini de rang au plus 1.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • Chebyshev polynomial
  • discrete Morse theory
  • minimal skipped interval
  • Möbius function
  • poset
  • subword order
Cited by

Source: OpenCitations

  • The Möbius function of generalized factor order

    Discrete Mathematics

    Authors : Robert Willenbring

    Journal reference : Volume 313, 2012, pp. 330-347

    DOI : 10.1016/j.disc.2012.11.002
  • The topology of the permutation pattern poset

    Discrete Mathematics & Theoretical Computer Science

    Authors : Peter McNamara ORCID, Einar Steingrımsson ORCID

    Journal reference : Volume DMTCS Proceedings vol. AT,..., 2014, pp.

    DOI : 10.46298/dmtcs.2397
  • Some open problems on permutation patterns

    arXiv (Cornell University)

    Authors : Einar Steingrímsson ORCID

    Journal reference : Volume , 2013, pp. 239-264

    DOI : 10.1017/cbo9781139506748.007
  • On the growth of the Möbius function of permutations

    Journal of Combinatorial Theory Series A

    Authors : Vít Jelínek ORCID, Ida Kantor ORCID, Jan Kynčl ORCID, Martin Tancer ORCID

    Journal reference : Volume 169, 2019, pp. 105121

    DOI : 10.1016/j.jcta.2019.105121
  • Intervals of permutations with a fixed number of descents are shellable

    Discrete Mathematics

    Authors : Jason P. Smith ORCID

    Journal reference : Volume 339, 2015, pp. 118-126

    DOI : 10.1016/j.disc.2015.08.004
  • Discrete Morse theory for weighted simplicial complexes

    arXiv (Cornell University)

    Authors : Chengyuan Wu ORCID, Shiquan Ren ORCID, Jie Wu ORCID, Kelin Xia ORCID

    Journal reference : Volume 270, 2019, pp. 107038

    DOI : 10.1016/j.topol.2019.107038
  • On the topology of the permutation pattern poset

    Journal of Combinatorial Theory Series A

    Authors : Peter R.W. McNamara ORCID, Einar Steingrímsson ORCID

    Journal reference : Volume 134, 2015, pp. 1-35

    DOI : 10.1016/j.jcta.2015.02.009
Preview
Loading PDF preview...