The Möbius function of the consecutive pattern poset

A. Bernini, L. Ferrari, E. Steingrimsson

Research output: Contribution to journalArticle

10 Citations (Scopus)
45 Downloads (Pure)

Abstract

An occurrence of a consecutive permutation pattern p in a permutation π is a segment of consecutive letters of π whose values appear in the same order of size as the letters in p. The set of all permutations forms a poset with respect to such pattern containment. We compute the Möbius function of intervals in this poset. For most intervals our results give an immediate answer to the question. In the remaining cases, we give a polynomial time algorithm to compute the Möbius function. In particular, we show that the Möbius function only takes the values −1, 0 and 1.
Original languageEnglish
Article numberP146
Number of pages12
JournalThe Electronic Journal of Combinatorics
Volume18
Issue number1
Publication statusPublished - 2011

Keywords

  • consecutive pattern poset
  • Möbius function

Fingerprint Dive into the research topics of 'The Möbius function of the consecutive pattern poset'. Together they form a unique fingerprint.

  • Cite this